sintaxis - operadores en perl

¿Qué tan rápido es el operador smartmatch de Perl cuando busca un escalar en una matriz?

Question

Quiero buscar repetidamente valores en una matriz que no cambie.

Hasta ahora, lo he estado haciendo de esta manera: puse los valores en un hash (así que tengo una matriz y un hash con esencialmente el mismo contenido) y busco el hash que exists .

No me gusta tener dos variables diferentes (la matriz y el hash) que ambos almacenan la misma cosa; Sin embargo, el hash es mucho más rápido para la búsqueda.

Descubrí que hay un operador ~~ (smartmatch) en Perl 5.10. ¿Qué tan eficiente es cuando se busca un escalar en una matriz?

Answer 1

Lo "inteligente" en "partido inteligente" no se trata de la búsqueda. Se trata de hacer lo correcto en el momento correcto según el contexto.

La cuestión de si es más rápido pasar por un array o índice en un hash es algo que tendría que comparar, pero en general, tendría que ser un array bastante pequeño para poder hojearlo en lugar de indexar un hash. .

Answer 2

Rápido para pequeños números de coincidencias potenciales, pero no más rápido que el hash. Los hash son realmente la herramienta adecuada para probar la pertenencia a conjuntos. Dado que el acceso hash es O (log n) y smartmatch en una matriz sigue siendo O (n) escaneo lineal (aunque en cortocircuito, a diferencia de grep), con un mayor número de valores en las coincidencias permitidas, smartmatch empeora relativamente.

Código de referencia (que coincida con 3 valores):

#!perl
use 5.12.0;
use Benchmark qw(cmpthese);

my @hits = qw(one two three);
my @candidates = qw(one two three four five six); # 50% hit rate
my %hash;
@hash{@hits} = ();

sub count_hits_hash {
  my $count = 0;
  for (@_) {
    $count++ if exists $hash{$_};
  }
  $count;
}

sub count_hits_smartmatch {
  my $count = 0;
  for (@_) {
    $count++ when @hits;
  }
  $count;
}

say count_hits_hash(@candidates);
say count_hits_smartmatch(@candidates);

cmpthese(-5, {
    hash => sub { count_hits_hash((@candidates) x 1000) },
    smartmatch => sub { count_hits_smartmatch((@candidates) x 1000) },
  }
);

Resultados de referencia:

             Rate smartmatch       hash
smartmatch  404/s         --       -65%
hash       1144/s       183%         --

Answer 3

Si desea buscar un único escalar en una matriz, puede usar la first subrutina List::Util . Se detiene tan pronto como sabe la respuesta. No espero que esto sea más rápido que una búsqueda de hash si ya tienes el hash , pero si consideras crear el hash y tenerlo en la memoria, podría ser más conveniente que solo busques la matriz que ya tienes.

En cuanto a la inteligencia del operador de emparejamiento inteligente, si desea ver qué tan inteligente es, pruébelo. :)

Hay al menos tres casos que desea examinar. El peor de los casos es que todos los elementos que quieres encontrar están al final. El mejor caso es que todos los elementos que quieres encontrar están al principio. El caso probable es que los elementos que desea encontrar promedian estar en el medio.

Ahora, antes de comenzar este punto de referencia, espero que si la coincidencia inteligente puede perlsyn un cortocircuito (y puede estar documentada en perlsyn ), los mejores tiempos de caso se mantendrán iguales a pesar del tamaño de la matriz, mientras que los otros empeorarán cada vez más . Si no puede provocar un cortocircuito y tiene que escanear todo el arreglo cada vez, no debería haber diferencia en los tiempos porque cada caso implica la misma cantidad de trabajo.

Aquí hay un punto de referencia:

#!perl
use 5.12.2;
use strict;
use warnings;

use Benchmark qw(cmpthese);

my @hits = qw(A B C);
my @base = qw(one two three four five six) x ( $ARGV[0] || 1 );

my @at_end       = ( @base, @hits );
my @at_beginning = ( @hits, @base );

my @in_middle = @base;
splice @in_middle, int( @in_middle / 2 ), 0, @hits;

my @random = @base;
foreach my $item ( @hits ) {
    my $index = int rand @random;
    splice @random, $index, 0, $item;
    }

sub count {
    my( $hits, $candidates ) = @_;

    my $count;
    foreach ( @$hits ) { when( $candidates ) { $count++ } }
    $count;
    }

cmpthese(-5, {
    hits_beginning => sub { my $count = count( /@hits, /@at_beginning ) },
    hits_end       => sub { my $count = count( /@hits, /@at_end ) },
    hits_middle    => sub { my $count = count( /@hits, /@in_middle ) },
    hits_random    => sub { my $count = count( /@hits, /@random ) },
    control        => sub { my $count = count( [], [] ) },
  }
);

Así es como lo hicieron las diferentes partes. Tenga en cuenta que esta es una gráfica logarítmica en ambos ejes, por lo que las pendientes de las líneas de hundimiento no son tan cercanas como se ven:

Por lo tanto, parece que el operador de emparejamiento inteligente es un poco inteligente, pero eso realmente no te ayuda porque es posible que aún tengas que escanear toda la matriz. Probablemente no sepa de antemano dónde encontrará sus elementos. Espero que un hash se desempeñe de la misma manera que la mejor combinación inteligente de casos, incluso si tiene que renunciar a algo de memoria para ello.

Bien, entonces la combinación inteligente es inteligente dos veces es genial, pero la pregunta real es "¿Debo usarla?". La alternativa es una búsqueda de hash, y me ha estado molestando que no haya considerado ese caso.

Al igual que con cualquier punto de referencia, empiezo a pensar en cuáles podrían ser los resultados antes de probarlos. Espero que si ya tengo el hash, buscar un valor será muy rápido. Ese caso no es un problema. Estoy más interesado en el caso donde todavía no tengo el hash. ¿Qué tan rápido puedo hacer el hash y buscar una clave? Espero que el rendimiento no sea tan bueno, pero ¿sigue siendo mejor que la coincidencia inteligente del peor caso?

Sin embargo, antes de ver el punto de referencia, recuerde que casi nunca hay suficiente información sobre qué técnica debe usar con solo mirar los números. El contexto del problema selecciona la mejor técnica, no el micro-punto de referencia más rápido y sin contexto. Consideremos un par de casos que seleccionarían diferentes técnicas:

• Tienes una matriz que buscarás repetidamente
• Siempre obtienes una nueva matriz que solo necesitas buscar una vez
• Obtienes arreglos muy grandes pero tienes memoria limitada

Ahora, teniendo esto en cuenta, agrego a mi programa anterior:

my %old_hash = map {$_,1} @in_middle; 

cmpthese(-5, {
    ...,
    new_hash       => sub { 
        my %h = map {$_,1} @in_middle; 
        my $count = 0;
        foreach ( @hits ) { $count++ if exists $h{$_} }
        $count;
        },
    old_hash       => sub { 
        my $count = 0;
        foreach ( @hits ) { $count++ if exists $old_hash{$_} }
        $count;
        },
    control_hash   => sub { 
        my $count = 0;
        foreach ( @hits ) { $count++ }
        $count;
        },
    }
);

Aquí está la trama. Los colores son un poco difíciles de distinguir. La línea más baja allí es el caso en el que tiene que crear el hash cada vez que quiera buscarlo. Eso es bastante pobre. Las dos líneas más altas (verdes) son el control para el hash (no hay hash realmente allí) y la búsqueda de hash existente. Esto es un log / log plot; esos dos casos son más rápidos que incluso el control de coincidencia inteligente (que simplemente llama una subrutina).

Hay algunas otras cosas a tener en cuenta. Las líneas para el caso "aleatorio" son un poco diferentes. Eso es comprensible porque cada punto de referencia (por lo tanto, una vez por cada ejecución de escala de matriz) coloca aleatoriamente los elementos de éxito en la matriz candidata. Algunas ejecuciones las ponen un poco antes y otras un poco más tarde, pero como solo hago la matriz @random una vez por ejecución de todo el programa, se mueven un poco. Eso significa que los baches en la línea no son significativos. Si probé todas las posiciones y promedié, espero que la línea "aleatoria" sea la misma que la línea "media".

Ahora, observando estos resultados, diría que una coincidencia inteligente es mucho más rápida en su peor caso que la búsqueda de hash en su peor caso. Eso tiene sentido. Para crear un hash, tengo que visitar cada elemento de la matriz y también hacer el hash, que es mucho copiar. No hay copia con el partido inteligente.

Aquí hay un caso más que no examinaré sin embargo. ¿Cuándo el hash se vuelve mejor que el partido inteligente? Es decir, ¿cuándo la sobrecarga de crear el hash se extiende lo suficiente en búsquedas repetidas para que el hash sea la mejor opción?