是否可以在Perl中保留哈希表的大小？

我在Perl中創建了一個未知大小的哈希表。是否可以在Perl中保留哈希表的大小？

散列表將字符串映射到對數組的引用。

我的應用程序的主循環在每次迭代中向散列表添加5-10個元素。隨着哈希表填滿，事情開始大幅放緩。從觀察結果來看，當散列表中有〜50k個密鑰時，加入密鑰的速度會減慢20倍。

我假設散列表已滿，並且發生了衝突。我想'保留'哈希表的大小，但我不確定如何。

問題中的散列是hNgramsToWord。

對於每個單詞，該單詞的1-len-grams被添加爲鍵，並引用包含該ngram的單詞數組。

例如：

AddToNgramHash（「Hello」）;

並[h，E，L，L，O，他，EL，LL，LO，HEL，LLO，地獄，ELLO，你好]都被添加作爲密鑰，映射到「你好」

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; 
}

來源

2011-07-08 user756079

我的猜測是perl根本就不是用這樣的東西做的（這是很多鍵）。就我所知，在這種實現中沒有任何低級別的訪問。 –

@crimson_penguin：不正確，反正50k不是很多密鑰 – ysth

我立場正確。 :) –

可以設置桶的數量爲哈希像這樣：

keys(%hash) = 128;

數量將四捨五入到兩個電源。

也就是說，您看到的減速很可能是由於散列衝突過多所致，因爲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;

一旦有按鍵很多，你會發現一個當需要擴大桶的數量時，可以感覺到放緩，但它仍然保持着非常平穩的速度。

看着你的代碼，加載的單詞越多，每個單詞所做的工作就越多。

你可以通過改變這個解決它：

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

這樣：

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

無需數組複製兩次。無需檢查ngram是否已經有條目 - 它會爲您自動生成一個數組引用。

來源

2011-07-08 02:49:28 ysth

有趣。我已經添加了上面的代碼，並將測試設置散列大小。謝謝。 – user756079

@ user756079：是的，不是散列衝突的問題 – ysth

哇。它剛剛運行並在大約5秒內完成。你是一位紳士和學者。 – user756079

是否可以在Perl中保留哈希表的大小？

回答

相關問題