Perlでハッシュテーブルのサイズを予約することはできますか？

Question

私は、不明なサイズのPerlでハッシュテーブルを作成しています。

ハッシュテーブルは、文字列を配列への参照にマップします。

私のアプリケーションのメインループは、各反復でハッシュテーブルに5-10要素を追加します。ハッシュテーブルがいっぱいになると、物事は急速に減速し始める。観測から、ハッシュテーブルに〜50kのキーがある場合、キーを追加すると20倍の速度で減速します。

私は、ハッシュテーブルがいっぱいになって、衝突が発生していると仮定します。私はハッシュテーブルのサイズを '予約'したいと思っていますが、わかりません。

---

ハッシュはhNgramsToWordです。

各単語に対して、その単語の1-len-gramがキーとして追加され、そのngramを含む単語の配列を参照します。例えば

：

AddToNgramHash（ "こんにちは"）。

[H、E、L、L、O、彼、EL、ハロー、ello、地獄、LLO、HEL、LO、LL]はすべてのキーとして追加され、

sub AddToNgramHash($) { 
    my $word = shift; 
    my @aNgrams = MakeNgrams($word); 
    foreach my $ngram (@aNgrams) { 
     my @aWords; 
     if(defined($hNgramsToWord{$ngram})) { 
      @aWords = @{$hNgramsToWord{$ngram}}; 
     } 
     push (@aWords, $word); 
     $hNgramsToWord{$ngram} = \@aWords; 
    } 
    return scalar keys %hNgramsToWord; 
} 

sub MakeNgrams($) { 
    my $word = shift; 
    my $len = length($word); 
    my @aNgrams; 
    for(1..$len) { 
     my $ngs = $_; 
      for(0..$len-$ngs) { 
      my $ngram = substr($word, $_, $ngs); 
      push (@aNgrams, $ngram); 
     } 
    } 
    return @aNgrams; 
} 

Answer 1

"ハロー" へのマッピングあなたはそのようなハッシュのためのバケットの数を設定することができ

：

keys(%hash) = 128; 

数が2の累乗に切り上げられます。

これは、Perlが必要に応じてバケットの数を動的に拡張するため、表示される減速が過剰なハッシュ衝突によるものである可能性は非常に低いと言います。また、5.8.2以降、病的データを検出して、指定されたバケットが過度に使用され、そのハッシュのハッシュ関数が再構成されることさえあります。

コードを表示すると、実際の問題を見つけるのに役立つでしょう。

ハッシュキーの数が多い（あなたがメモリ不足しているまでそれが継続することはできません...）のデモンストレーション：

use strict; 
use warnings; 
my $start = time(); 
my %hash; 
$SIG{ALRM} = sub { 
    alarm 1; 
    printf(
     "%.0f keys/s; %d keys, %s buckets used\n", 
     keys(%hash)/(time() - $start), 
     scalar(keys(%hash)), 
     scalar(%hash) 
    ); 
}; 
alarm 1; 
$hash{rand()}++ while 1; 

キーが多いたら、あなたは気づくでしょうバケットの数を増やす必要がある場合には知覚可能な減速が見られますが、それでもまだかなりのペースを維持しています。

コードを見ると、単語が読み込まれるほど、単語ごとに多くの作業が必要になります。

あなたは、この変更によってそれを修正することができます：二回配列をコピーする

push @{ $hNgramsToWord{$ngram} }, $word; 

必要がありません：これに

my @aWords; 
    if(defined($hNgramsToWord{$ngram})) { 
     @aWords = @{$hNgramsToWord{$ngram}}; 
    } 
    push (@aWords, $word); 
    $hNgramsToWord{$ngram} = \@aWords; 

を。 ngramに既にエントリがあるかどうかを確認する必要はありません。それは配列参照を自動化します。