1

1 から 999 までのサイズの 1e8 の数字を含むファイルがあります。各ファイルを読み、各ファイルで見つかった各数字の数のレポートを保存する必要があります。すべてゼロの定数配列を設定し、インデックスとして読み取った数値を使用してインクリメントすると、答えが得られると思いました。これを行うための Perl 構文は、私が期待したものではありません。すべての数が必ず発生するわけではありません。たぶんハッシュは行く方法ですが、配列にはおそらくいくつかの穴しかありません。何か助けはありますか？ありがとう。

4

3 に答える 3

3

Tom Duff (Duff's Device の作成者): 「コードが遅すぎる場合は、高速化する必要があります。より良いアルゴリズムが利用できない場合は、サイクルをトリムする必要があります。」

これがハッシュが最適な状況であることに同意しません。確かに、ハッシュは慣用的な適合です。これは perlfaq4 で言及されている方法であり、カウンター コンテナー内の要素を無駄にしません。しかし、彼は 1 から 999 までの 100_000_000 個の整数について話しているのです。カウンター コンテナーで使用されている要素の数は重要ではありません。カウントを取得するために必要な反復回数は非常に重要です。100,000,000 回の反復には多くの時間がかかります。

代わりに配列を使用する場合は、インデックスがゼロの要素を破棄します。そして、すべての整数が同じ値である場合、さらに 998 個の要素を破棄します。そんなに大したことですか？一方、配列へのインデックス付けと、ハッシュ集約へのインデックス付けの両方が O(1) 操作に出力されたとしても、Big-O 表記法はストーリーの一部しか伝えていません。'n' が整数の総数 (100,000,000) である場合、配列アプローチとハッシュ アプローチはどちらも O(n) 操作です。したがって、どちらのアプローチがより計算効率が高いかということになります。配列ルックアップとハッシュ ルックアップはどちらも O(1) ですが、ハッシュ ルックアップを実行するにはかなり多くのサイクルが必要であることがわかります。

100,000,000 を超える整数の反復とカウンターのインクリメントには時間がかかります。しかし、配列内よりもハッシュ内でそうするのに時間がかかることがわかりました。これが「一般的なイディオム」の観点からは冒涜であることはわかっています。しかし、これは非常に特殊なケースであり、計算効率が慣用的なコードよりも重要であり、配列をカウンターとして使用することによるわずかに大きいメモリ フットプリントよりも重要です。

ここに私が話していることを示すいくつかのコードがあります:

use strict;
use warnings;
use Benchmark  qw/ cmpthese /;
use List::Util qw/ max min  /;
use Test::More;
use Readonly;



Readonly my $datasize => 100_000_000;

Readonly my $test_size => 100_000;

my @array_results = keys count_in_array( $test_size );
my @hash_results  = keys count_in_hash(  $test_size );

is( max( @array_results ), 999, "max( keys count_in_array() ) in range." );
is( min( @array_results ),   1, "min( keys count_in_array() ) in range." );
is( max( @hash_results  ), 999, "max( keys  count_in_hash() ) in range." );
is( min( @hash_results  ),   1, "min( keys  count_in_hash() ) in range." );
done_testing();    



cmpthese( 5, {
    array => sub{ my $results = count_in_array() },
    hash  => sub{ my $results = count_in_hash()  },
} );




sub count_in_array {
    my @container;
    for( 1 .. $datasize ) {
        $container[ int( rand( 999 ) ) + 1 ]++;
    }
    return {
        map{ 
                $container[$_] > 0 
                    ? ( $_ => $container[$_] ) 
                    : () 
        } 1 .. $#container
    };
}



sub count_in_hash {
    my %container;
    for( 1 .. $datasize ) {
        $container{ int( rand ( 999 ) ) + 1 }++;
    }
    return \%container;
}

そして、これがそのベンチマークの結果です。

ok 1 - max( keys count_in_array() ) in range.
ok 2 - min( keys count_in_array() ) in range.
ok 3 - max( keys  count_in_hash() ) in range.
ok 4 - min( keys  count_in_hash() ) in range.
1..4
      s/iter  hash array
hash    24.9    --  -42%
array   14.5   72%    --

これは配列アプローチにとって大きなメリットです (72% 高速です)。それでも遅すぎる場合は、Inline::C を使用してサイクルをトリムし、int の配列を使用して配列アプローチを書き直します。それはさらに桁違いに速くなります。

これは、最適化が必要な重要な 3% である可能性があります。

では、一般的に認識されている慣用句からの脱却の影響を軽減するにはどうすればよいでしょうか? 将来の読者 (将来の私たち自身を含む) が、何が行われているか、なぜそれが私たちにはなじみのない方法で行われているのかを理解できるように、私たちが行っていることを必ず文書化します。

ちょうど私の.02。

于 2011-11-14T06:23:09.360 に答える
3

これを行うための Perl 構文は、私が期待したものではありません。

あなたの作品を見せてください

すべての数が必ず発生するわけではありません。

ゼロをスキップします (単純な if ブロック、http://perldoc.perl.org/perlintro.htmlを参照)

たぶんハッシュは行く方法ですが、配列にはおそらくいくつかの穴しかありません。

はい、ハッシュは自然に適合します perlfaq4。「count」、「uniq」、および「duplicate」を検索してください。

于 2011-11-14T02:08:20.647 に答える
0

システムのソート ユーティリティの品質に応じて、コマンド ラインで次の操作を行います。

sort giant-file.txt | uniq -c > giant_file_counts.txt
于 2011-11-14T13:53:12.573 に答える