Когда имеет смысл использовать хеш?

Question

С perldata :

You can preallocate space for a hash by assigning to the keys() function.
This rounds up the allocated buckets to the next power of two:

   keys(%users) = 1000;      # allocate 1024 buckets

Есть ли эмпирическое правило, когда нажатие на хеш улучшает производительность?

Answer 1

Эмпирическое правило гласит, что чем больше будет хеш-код, тем больше вероятность того, что вы предварительно получите его значение.Подумайте, есть ли в вашем хэше 10 слотов, и вы начнете добавлять одно за другим, количество расширений будет а) небольшим (если вообще будет) и б) небольшим (поскольку данных мало).

Но если вы ЗНАЕТЕ, что вам понадобится как минимум 1 МБ элементов, то нет смысла расширять и копировать базовые и постоянно расширяющиеся структуры данных по мере роста таблицы.

ЗАМЕЧАЕТЕ ЛИ ВЫ это расширение?Эх, может быть.Современные машины чертовски быстры, может не подойти.Но это отличная возможность для расширения кучи, что приводит к GC и каскаду всех видов вещей.Так что, если вы знаете, что собираетесь его использовать, это «дешевое» решение, позволяющее настроить еще несколько показателей производительности.

Answer 2

Я пытался измерить стоимость расширения при росте хеша:

use Benchmark qw(cmpthese);

# few values
cmpthese(-4, {
    prealloc => sub {
        my %hash;
        keys(%hash) = 17576;
        $hash{$_} = $_ for 'aaa' .. 'zzz';
    },
    normal   => sub {
        my %hash;
        $hash{$_} = $_ for 'aaa' .. 'zzz';
    },
});

# more values
cmpthese(-8, {
    prealloc => sub {
        my %hash;
        keys(%hash) = 456976;
        $hash{$_} = $_ for 'aaaa' .. 'zzzz';
    },
    normal   => sub {
        my %hash;
        $hash{$_} = $_ for 'aaaa' .. 'zzzz';
    },
});

Результаты не похожи на большую оптимизацию, однако может оказаться полезным уменьшение фрагментации кучи, упомянутое Уиллом Хартунгом. Запуск perl 5.12 на машине WinXP.

       Rate   normal prealloc
normal   48.3/s       --      -2%
prealloc 49.4/s       2%       --
        (warning: too few iterations for a reliable count)
     s/iter   normal prealloc
normal     3.62       --      -1%
prealloc   3.57       1%       --

Answer 3

По сути, это дверь для оптимизации производительности хеширования. Производительность хэширования сильно зависит как от используемого алгоритма хеширования, так и от данных, с которыми вы работаете, поэтому практически невозможно придумать правило. Во всяком случае, что-то можно сказать.

Вы знаете, что каждая структура данных предлагает определенный баланс между пространственной и временной эффективностью. Хеш-таблицы особенно хороши с точки зрения эффективности времени, предлагая привлекательный постоянный (0 (1)) доступ к времени.

Это верно, если нет столкновения. Когда происходит столкновение, тогда время доступа является линейным с размером сегмента, соответствующего значению столкновения. (Посмотрите на это для более подробной информации). Столкновения, помимо того, что они «медленнее», в основном нарушают гарантию времени доступа, которая является единственным наиболее важным аспектом, который часто приводит к выбору хеш-таблицы.

В идеале хеш-таблицы могут быть нацелены на то, что известно как «идеальное хеширование» (что на самом деле выполнимо, только если вы можете точно настроить алгоритм в соответствии с типом данных, которые вы будете обрабатывать), но это не так легко достичь в общем случае (на самом деле это эвфемизм). В любом случае, на самом деле большие хеш-таблицы (вместе с хорошим алгоритмом хеширования) могут снизить частоту коллизий и, следовательно, повысить производительность за счет памяти. Меньшие хеш-таблицы будут видеть больше коллизий (следовательно, будут иметь меньшую производительность и меньшую гарантию времени доступа к качеству), но занимают меньше памяти.

Итак, если вы профилируете свою программу и видите, что доступ к хеш-таблице является узким местом (по любым причинам), у вас есть шанс решить эту проблему, зарезервировав больше памяти для хеш-пространства (если у вас есть память, которую можно выделить).

В любом случае я бы не увеличивал это значение случайным образом, а только после тщательного профилирования, поскольку верно также и то, что используемый Perl алгоритм компилируется в (AFAIK), и это также оказывает большое влияние на производительность хеширования (в другими словами, вы можете столкнуться с множеством коллизий, даже если увеличите размер хеша).

Как обычно с вещами, связанными с производительностью, это может быть полезно или нет, это зависит от вашего конкретного случая.