¿Cómo optimizar el atravesamiento hash bidimensional en Perl?

Question

Tengo un hash de hash %signal_db. Un elemento típico es: $signal_db{$cycle}{$key}. Hay 10.000 de señales y 10.000 de claves.

¿Hay alguna manera de optimizar (en cuanto al tiempo) este pedazo de código:

foreach my $cycle (sort numerically keys %signal_db) { 
    foreach my $key (sort keys %{$signal_db{$cycle}}) { 
     print $signal_db{$cycle}{$key}.$key."\n"; 
    } 
} 

Los elementos tienen que ser impreso en el mismo orden que en mi código.

Answer 1

Dos micro optimizaciones: correlaciona el hash interno en lugar de la desreferenciación constante y el búfer de impresión constante. Es posible deshacerse de la clasificación utilizando formatos de almacenamiento alternativos, probando dos variantes. Resultados:

   Rate  original   try3 alternative alternative2 
original  46.1/s   --   -12%   -21%   -32% 
try3   52.6/s   14%   --   -10%   -22% 
alternative 58.6/s   27%   11%   --   -13% 
alternative2 67.5/s   46%   28%   15%   -- 

Conclusión:

Es mejor utilizar el formato de almacenamiento preclasificado, pero sin C victoria sería probablemente menos de 100% (en mi conjunto de datos de prueba). La información proporcionada acerca de los datos sugiere que las claves en hash externo son números casi secuenciales, por lo que esta demanda de matriz.

Guión:

#!/usr/bin/env perl 

use strict; use warnings; 
use Benchmark qw/timethese cmpthese/; 

my %signal_db = map { $_ => {} } 1..1000; 
%$_ = map { $_ => $_ } 'a'..'z' foreach values %signal_db; 

my @signal_db = map { { cycle => $_ } } 1..1000; 
$_->{'samples'} = { map { $_ => $_ } 'a'..'z' } foreach @signal_db; 

my @signal_db1 = map { $_ => [] } 1..1000; 
@$_ = map { $_ => $_ } 'a'..'z' foreach grep ref $_, @signal_db1; 

use Sort::Key qw(nsort); 

sub numerically { $a <=> $b } 

my $result = cmpthese(-2, { 
    'original' => sub { 
     open my $out, '>', 'tmp.out'; 
     foreach my $cycle (sort numerically keys %signal_db) { 
      foreach my $key (sort keys %{$signal_db{$cycle}}) { 
       print $out $signal_db{$cycle}{$key}.$key."\n"; 
      } 
     } 
    }, 
    'try3' => sub { 
     open my $out, '>', 'tmp.out'; 
     foreach my $cycle (map $signal_db{$_}, sort numerically keys %signal_db) { 
      my $tmp = ''; 
      foreach my $key (sort keys %$cycle) { 
       $tmp .= $cycle->{$key}.$key."\n"; 
      } 
      print $out $tmp; 
     } 
    }, 
    'alternative' => sub { 
     open my $out, '>', 'tmp.out'; 
     foreach my $cycle (map $_->{'samples'}, @signal_db) { 
      my $tmp = ''; 
      foreach my $key (sort keys %$cycle) { 
       $tmp .= $cycle->{$key}.$key."\n"; 
      } 
      print $out $tmp; 
     } 
    }, 
    'alternative2' => sub { 
     open my $out, '>', 'tmp.out'; 
     foreach my $cycle (grep ref $_, @signal_db1) { 
      my $tmp = ''; 
      foreach (my $i = 0; $i < @$cycle; $i+=2) { 
       $tmp .= $cycle->[$i+1].$cycle->[$i]."\n"; 
      } 
      print $out $tmp; 
     } 
    }, 
}); 

Answer 2

Primero probaría con el Sort::Key module porque la ordenación lleva más tiempo que el simple bucle y la impresión. Además, si las claves hashes interiores son (en su mayoría) idénticas, entonces simplemente debe preseleccionarlas, pero supongo que no es el caso o de lo contrario ya estaría haciendo eso.

Debería probar asignando $ signal_db {$ cycle} a una referencia también. Puede encontrar que each es más rápido que keys más recuperación, especialmente si se usa con Sort::Key. Verificaría si el mapa funciona más rápido que foreach también, probablemente el mismo, pero quién sabe. Puede encontrar que print se ejecuta más rápido si le pasa una lista o la llama varias veces.

No he probado este código, pero tirar juntos todas estas ideas, excepto each da:

foreach my $cycle (nsort keys %signal_db) { 
    my $r = $signal_db{$cycle}; 
    map { print ($r->{$_},$_,"\n"); } (nsort keys %$r); 
} 

Hay un artículo sobre la clasificación en perl here, echa un vistazo a la Schwartzian Transform si desea ver cómo uno podría usar each.

Si el código no tiene que ser consciente de la seguridad, entonces se podría concebiblemente desactivar la protección de Perl contra algorithmic complexity attacks estableciendo PERL_HASH_SEED o variables relacionadas y/o recompilar Perl con configuración alterada, por lo keys y values comandos de que Perl devuelven las llaves o de valores de ordenó ya, ahorrándole considerable tiempo clasificándolos. Pero por favor mira this 28C3 talk antes de hacerlo. No sé si esto funcionará tampoco, necesitarías leer esta parte del código fuente de Perl, quizás sea más fácil simplemente implementando tu ciclo en C.

Answer 3

my %signal_db = map {$_ => {1 .. 1000}} 1 .. 1000; 

sub numerically {$a <=> $b} 
sub orig { 
    my $x; 
    foreach my $cycle (sort numerically keys %signal_db) { 
     foreach my $key (sort keys %{$signal_db{$cycle}}) { 
      $x += length $signal_db{$cycle}{$key}.$key."\n"; 
     } 
    } 
} 

sub faster { 
    my $x; 
    our ($cycle, $key, %hash); # move allocation out of the loop 
    local *hash;  # and use package variables which are faster to alias into 

    foreach $cycle (sort {$a <=> $b} # the {$a <=> $b} literal is optimized 
        keys %signal_db) { 
     *hash = $signal_db{$cycle}; # alias into %hash 
     foreach $key (sort keys %hash) { 
      $x += length $hash{$key}.$key."\n"; # simplify the lookup 
     } 
    } 
} 

use Benchmark 'cmpthese'; 
cmpthese -5 => { 
    orig => \&orig, 
    faster => \&faster, 
}; 

el cual obtiene:

 
     Rate orig faster 
orig 2.56/s  -- -15% 
faster 3.03/s 18%  -- 

No hay una gran ganancia, pero es algo. No hay mucho más que pueda optimizar sin cambiar su estructura de datos para usar arreglos preestablecidos.(o escribir todo en XS)

Cambiar los bucles foreach para usar variables de paquete externas ahorra un poco de tiempo ya que perl no tiene que crear léxicos en el bucle. También las variables del paquete parecen ser un poco más rápidas de alias. Reducir la búsqueda interna a un solo nivel también ayuda.

Supongo que está imprimiendo en STDOUT y luego redirige la salida a un archivo? Si es así, el uso de Perl para abrir el archivo de salida directamente y luego imprimir en ese identificador puede permitir mejoras en el rendimiento del IO del archivo. Otra micro-optimización podría ser experimentar con diferentes tamaños de registros. Por ejemplo, ¿ahorra tiempo para construir una matriz en el bucle interno y luego unir/imprimir en la parte inferior del bucle externo? Pero eso es algo bastante dependiente del dispositivo (y posiblemente inútil debido a otras capas de almacenamiento en caché IO), así que te dejaré esa prueba.