0

perlで非常に迅速なソートを行う方法はありますか? おそらく1億個のキーがある非常に大きなハッシュがあるように。foreach my $x (sort {$a cmp $b} keys %myhash){DO SOMETHING}私がテストするとき、それは非常に非効率的です。最初にすべてのキーを配列にコピーして、クイックソートを使用できるかどうか疑問に思っています。

4

2 に答える 2

3

値をキーでソートしたくないため、ハッシュをリストコンテキストに入れたくありません。代わりに、はい、キーを並べ替えます。

my @ordered_keys = sort { $a cmp $b } keys %hash;

ただし、そのように値を処理したい場合は、次のようにすることができます。

my @ordered_values = @hash{ sort { $a cmp $b } keys %hash };

これは「ハッシュ スライス」を使用します。

しかし、この方法では、次のことができます。

foreach my $value ( @hash{ sort { $a cmp $b } keys %hash } ) { 
    # key? What key?
    do_something_with_hash_value( $value );
}
于 2012-10-18T18:53:16.980 に答える
3

100 個の文字列を並べ替えるのに 10μs (1000 万分の 1 秒) かかるとします。そんなに速いと思いますか？おそらく。それはおおまかに私のマシンが行うことです。

もしそうなら、100,000,000 ストリングに対して 41 秒の高速を考慮する必要があります!

理由は次のとおりです。

100 個の文字列を並べ替えているわけではありません。1,000,000 倍の文字列を並べ替えています。しかし、並べ替えは直線的ではありません。最適な並べ替えアルゴリズムは O(N log N) です。それがしっかりとバインドされていると仮定すると、つまり

  • 100 個の文字列を並べ替えるには、$overhead + 100 * log2(100) * $time_per_operation がかかります。

  • 100,000,000 個のキーを並べ替えるには、$overhead + 1,000,000 * log2(1,000,000) * $time_per_operation がかかります。

ごくわずかなオーバーヒアリングを想定すると、100,000,000 個の文字列を並べ替えるには、100 個の文字列を並べ替えるよりも 4,100,000 倍の時間がかかることになります。

したがって、100 ストリングで 10μs の高速を考慮する場合、1 億ストリングでは 41 秒の高速を考慮する必要があります。

どのような数値を取得していますか？

于 2012-10-18T19:58:36.383 に答える