是否可以在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是否已有条目 - 它将为您自动生成数组引用.