¿Es eficiente el "operador secreto" de Perl Goatse?

Question

El "operador de cabras" o la expresión =()= en Perl hace que una expresión se evalúe en el contexto de la lista.

Un ejemplo es:

my $str = "5 and 4 and a 3 and 2 1 BLAST OFF!!!"; 
my $count =()= $str =~ /\d/g; # 5 matches... 
print "There are $count numbers in your countdown...\n\n"; 

Mientras interprete el uso, esto es lo que sucede:

1. $str =~ /\d/g coincide con todos los dígitos. El contexto de cambio y lista g produce una lista de esas coincidencias. Deje que este sea el ejemplo de "List Producer", y en Perl esto podría ser muchas cosas.
2. =()= causa una asignación a una lista vacía, por lo que todas las coincidencias reales se copian en una lista vacía.
3. La asignación en contexto escalar a $ recuento de la lista producida en 2. da cuenta de la lista o el resultado de 5.
4. El cómputo de referencia de la lista vacía =()= tiende a cero después de la asignación escalar. La copia de los elementos de la lista es eliminada por Perl.

Las preguntas sobre la eficiencia son los siguientes:

1. Estoy equivocado en la forma en que estoy de análisis de esto?
2. Si tiene algún Productor de listas y todo lo que le interesa es el recuento, ¿hay alguna forma más eficiente de hacerlo?

Funciona muy bien con esta lista trivial, pero ¿y si la lista fuera cientos de miles de coincidencias? Con este método, estás produciendo una copia completa de cada partida y luego eliminándola solo para contarlas.

Answer 1

Perl 5 es muy listo para copiar listas. Solo copia tantos elementos como están en el lado izquierdo. Funciona porque la asignación de lista en el contexto escalar produce el número de elementos en el lado derecho. Por lo tanto, n elementos serán creados por la expresión regular, pero no serán copiados y descartados, simplemente descartados. Puede ver la diferencia que hace la copia extra en el caso ingenuo en el índice de referencia a continuación.

En cuanto a la eficiencia, una solución iterativa es a menudo más fácil en el uso de memoria y CPU, pero esto debe sopesarse con la brevedad del operador secreto de cabras. Estos son los resultados de la evaluación comparativa de las diferentes soluciones:

naive: 10 
iterative: 10 
goatse: 10 

for 0 items: 
       Rate iterative goatse  naive 
iterative 4365983/s  --  -7%  -12% 
goatse 4711803/s  8%  --  -5% 
naive  4962920/s  14%  5%  -- 

for 1 items: 
       Rate  naive goatse iterative 
naive  749594/s  --  -32%  -69% 
goatse 1103081/s  47%  --  -55% 
iterative 2457599/s  228%  123%  -- 

for 10 items: 
       Rate  naive goatse iterative 
naive  85418/s  --  -33%  -82% 
goatse 127999/s  50%  --  -74% 
iterative 486652/s  470%  280%  -- 

for 100 items: 
      Rate  naive goatse iterative 
naive  9309/s  --  -31%  -83% 
goatse 13524/s  45%  --  -76% 
iterative 55854/s  500%  313%  -- 

for 1000 items: 
      Rate  naive goatse iterative 
naive  1018/s  --  -31%  -82% 
goatse 1478/s  45%  --  -75% 
iterative 5802/s  470%  293%  -- 

for 10000 items: 
      Rate  naive goatse iterative 
naive  101/s  --  -31%  -82% 
goatse 146/s  45%  --  -75% 
iterative 575/s  470%  293%  -- 

Este es el código que lo generó:

#!/usr/bin/perl 

use strict; 
use warnings; 

use Benchmark; 

my $s = "a" x 10; 

my %subs = (
    naive => sub { 
     my @matches = $s =~ /a/g; 
     return scalar @matches; 
    }, 
    goatse => sub { 
     my $count =()= $s =~ /a/g; 
     return $count; 
    }, 
    iterative => sub { 
     my $count = 0; 
     $count++ while $s =~ /a/g; 
     return $count; 
    }, 
); 

for my $sub (keys %subs) { 
    print "$sub: @{[$subs{$sub}()]}\n"; 
} 

for my $n (0, 1, 10, 100, 1_000, 10_000) { 
    $s = "a" x $n; 
    print "\nfor $n items:\n"; 
    Benchmark::cmpthese -1, \%subs; 
} 

Answer 2

En el ejemplo particular, un punto de referencia es útil:

my $str = "5 and 4 and a 3 and 2 1 BLAST OFF!!!"; 

use Benchmark 'cmpthese'; 

cmpthese -2 => { 
    goatse => sub { 
     my $count =()= $str =~ /\d/g; 
     $count == 5 or die 
    }, 
    while => sub { 
     my $count; 
     $count++ while $str =~ /\d/g; 
     $count == 5 or die 
    }, 
}; 

cuales devoluciones:

  Rate goatse while 
goatse 285288/s  -- -57% 
while 661659/s 132%  -- 

El $str =~ /\d/g en contexto de lista está capturando la subcadena coincidente aunque no sea necesaria. El ejemplo while tiene la expresión regular en contexto escalar (booleano), por lo que el motor de expresiones regulares solo tiene que devolver verdadero o falso, y no las coincidencias reales.

Y, en general, si usted tiene una lista de funciones de producción y sólo se preocupan por el número de artículos, escribe una breve función count es más rápido:

sub make_list {map {$_**2} 0 .. 1000} 

sub count {scalar @_} 

use Benchmark 'cmpthese'; 

cmpthese -2 => { 
    goatse => sub {my $count =()= make_list; $count == 1001 or die}, 
    count => sub {my $count = count make_list; $count == 1001 or die}, 
}; 

lo que da:

  Rate goatse count 
goatse 3889/s  -- -26% 
count 5276/s 36%  -- 

Mi adivinar por qué el submarino es más rápido es porque las llamadas de subrutina están optimizadas para pasar listas sin copiarlas (pasadas como alias).

Answer 3

Si necesita ejecutar algo en el contexto de la lista, debe ejecutarlo en contexto de la lista. En algunos casos, como el que presenta, es posible que pueda solucionarlo con otra técnica, pero en la mayoría de los casos no lo hará.

Antes de la evaluación comparativa, sin embargo, la pregunta más importante es "¿Importa incluso?". Haga un perfil previo a su punto de referencia, y solo preocúpese por este tipo de cosas cuando se haya quedado sin problemas reales para resolver. :)

Si está buscando lo último en eficiencia, Perl tiene un nivel demasiado alto. :)