Можно ли зарезервировать размер хеш-таблицы в Perl? - PullRequest
Новая
       14

Можно ли зарезервировать размер хеш-таблицы в Perl?

3 голосов
/ 08 июля 2011

Я создаю хеш-таблицу в Perl неизвестного размера.

Хеш-таблица отображает строку на ссылку на массив.

Основной цикл моего приложения добавляет 5-10 элементов в хеш-таблицу в каждой итерации. Когда хеш-таблица заполняется, все начинает резко замедляться. По наблюдениям, когда в хэш-таблице есть ~ 50 тыс. Ключей, добавление ключей замедляется на величину 20х.

Я постулирую, что хеш-таблица заполнена и происходят конфликты. Я хотел бы «зарезервировать» размер хеш-таблицы, но не знаю, как.

Рассматриваемый хеш - hNgramsToWord.

Для каждого слова 1-ленграмм этого слова добавляются в качестве ключей со ссылкой на массив слов, которые содержат эту ngram.

Например:

AddToNgramHash ( "Hello");

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

1 Ответ

10 голосов
/ 08 июля 2011

Вы можете установить количество сегментов для хэша следующим образом: 

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 запись, она автоматически активирует для вас ссылку на массив.

...