是否可以在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中保留哈希表的大小？

回答

相关问题