performance - ¿Es eficiente el operador secreto de Perl Goatse?

operators idioms

Question

El "operador de cabras" o el modismo =()= en Perl hace que una expresión sea evaluada 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";

Cuando interpreto el uso, esto es lo que sucede:

1. $str =~ //d/g coincide con todos los dígitos. El contexto g cambio y lista 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. the =()= 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 $ count de la lista producida en 2. da el recuento de la lista o el resultado de 5.
4. El recuento de referencia de la lista vacía =()= va 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 estas:

1. ¿Me equivoco en cómo estoy analizando 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

En su 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
    },
};

que devuelve:

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

El contexto $str =~ //d/g en la lista captura 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 tiene una función de producción de listas y solo se preocupa por la cantidad de elementos, escribir una función de count breve es más rápida:

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 suposición de por qué el submarino es más rápido se debe a que las llamadas de subrutina están optimizadas para pasar listas sin copiarlas (pasadas como alias).

Answer 2

Perl 5 es inteligente acerca de cómo 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. Entonces, 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 la memoria y el uso de la CPU, pero esto debe sopesarse con la brevedad del operador secreto de cabras. Aquí están los resultados de la evaluación comparativa de varias 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%        --

Aquí está 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 3

Si necesita ejecutar algo en contexto de lista, debe ejecutarlo en contexto de 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 su punto de referencia, 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. :)

Sin embargo, si estás buscando lo último en eficiencia, Perl tiene un nivel demasiado alto. :)