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

Question

我正在 Perl 中创建一个大小未知的哈希表。

哈希表将字符串映射到对数组的引用。

我的应用程序的主循环在每次迭代中向哈希表添加 5-10 个元素。随着哈希表填满，事情开始急剧放缓。根据观察，当哈希表中有大约 50k 个键时，添加键的速度会减慢 20 倍。

我假设哈希表已满，并且正在发生冲突。我想“保留”哈希表的大小，但我不确定如何。

有问题的哈希是 hNgramsToWord。

对于每个单词，该单词的 1-len-gram 被添加为键，并引用包含该 ngram 的单词数组。

例如:

AddToNgramHash("你好");

[h, e, l, l, o, he, el, ll, lo, hel, llo, hell, ello, hello ] 都作为键添加，映射到“hello”

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;

一旦有很多键，当它需要扩展桶的数量时，你会注意到明显的放缓，但它仍然保持相当均匀的速度。

查看您的代码，加载的单词越多，它为每个单词所做的工作就越多。

您可以通过更改以下内容来修复它:

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

对此:

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

无需复制数组两次。无需检查 ngram 是否已经有条目 - 它会为您自动激活数组引用。