Perlで2次元ハッシュトラバースを最適化する方法は？

Question

私はハッシュのハッシュを持っています%signal_db。典型的な要素は、$signal_db{$cycle}{$key}です。 10,000個の信号と10,000個の鍵があります。

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

要素が自分のコードと同じ順序で印刷されなければならない。

最適化するための任意の方法（時間的な）コードのこの部分があります。

Answer 1

2つのマイクロ最適化：代わりに定数逆参照とバッファ一定の印刷物の。 2つのバリエーションをテストした代替ストレージ形式を使用してソートを取り除くことは可能です。結果：

   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%   -- 

結論：

それは事前ソートストレージ形式を使用することをお勧めしますが、Cの勝利なしで、おそらく（私のテストデータセットで）100％の範囲内であろう。提供されたデータに関する情報は、外側のハッシュのキーがほぼ連続した番号であることを示唆しているため、これは配列を叫ぶものです。

スクリプト：

#!/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

並べ替えには単純なループや印刷よりも時間がかかるため、最初にSort::Key moduleを試してみました。また、内側のハッシュキーが（ほとんど）同一であれば、それらを事前にソートする必要がありますが、これは当てはまらないと思います。

$ signal_db {$ cycle}を参照に割り当てることは間違いありません。 eachがkeysより速く、特にSort::Keyと一緒に使用された場合には、検索も高速です。私はマップがforeachよりも速く走っているかどうかをチェックしたいと思います。おそらく同じですが、誰が知っていますか？リストを渡すか、複数回呼び出すと、より速く実行されるprintが見つかります。

私はこのコードを試していないが、eachを除くこれらすべてのアイデアを投げることはできます：perlのhereでソートに関する記事があり

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

、シュワルツは、あなたがどのようにものを見たい場合はトランスフォームチェックアウトeachを使用することがあります。あなたのコードは、セキュリティを意識する必要がない場合

は、あなたはおそらくPERL_HASH_SEEDを設定することにより、algorithmic complexity attacksに対するPerlの保護を無効にしたり、関連する変数を、および/またはそのperlのkeysとvaluesコマンドがでキーまたは値を返されたので、変更された設定でPerlを再コンパイルすることができソートされた注文はすでに済んでいます。しかし、そうする前にthis 28C3 talkを見てください。もしもこれがうまくいけば、Perlのソースコードのこの部分を読む必要があります。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, 
}; 

取得します：

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

ない巨大な利益を、それは何かです。あらかじめ並べ替えられた配列を使用するようにデータ構造を変更せずに最適化できることはそれ以上ありません。（またはXS全体を書く）

外部パッケージ変数を使用するようにループを切り替えると、少し時間が節約されます。なぜなら、perlはループ内にレキシカルを作成する必要がないからです。また、パッケージ変数は、エイリアスするのが少し速いようです。内部ルックアップを単一のレベルに減らすことも役立ちます。

STDOUTに出力してから出力をファイルにリダイレクトするとしますか？その場合、Perlを使用して出力ファイルを直接開いてから、そのハンドルに印刷すると、ファイルIOのパフォーマンスが向上する可能性があります。別のマイクロ最適化は、異なるレコードサイズで実験することです。例えば、内側のループに配列を作成してから、外側のループの最後に結合/印刷するときはいつでも保存できますか？しかし、それはかなりデバイスに依存している（そして他のI/Oキャッシングレイヤーのために無意味かもしれない）ので、私はそのテストをあなたに任せます。