Robin Hood hashing

Поигрался на днях в Робин Гуда - это такой вариант open addressing hash table. Open addressing - это когда данные (пары ключ-значение) все хранятся в одном большом массиве, никаких связных списков. По ключу считаем хэш, его отображаем на пространство позиций в массиве, получаем стартовую позицию, от которой уже пляшем. В простейшем случае Linear Probing мы от стартовой позиции просто последовательно идем вправо, пока не найдем нужное значение. Если мы добавляем новое значение, то так же находим стартовую позицию, от нее движемся вправо, пока не найдем свободную ячейку, там и сохраняем. Robin Hood hashing обычно описывается так: он похож на Linear Probing, при добавлении нового элемента мы так же находим стартовую позицию и движемся последовательно вправо, но поглядываем на хэши тех значений, что нам встречаются на пути, и если находим богача - которому повезло иметь более короткий путь от его стартовой позиции до занимаемой - то раскулачиваем и меняемся с ним: на место богача записываем новое значение, после чего продолжаем процесс (последовательное движение вправо) уже с этим богачом в качестве вставляемого. Такое перераспределение богатств заметно снижает число "бедняков" - значений, оказавшихся очень далеко от своей стартовой позиции, а ведь чем дальше от стартовой позиции находится значение, тем дольше до него идти при поиске, и тем больше может потребоваться линий кэша загрузить из памяти.

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

маленькие радости

Есть вещи, которые совершенно тривиальны в динамически типизированных и в зависимотипизированных языках, но вот в куче промежуточных - привычных нам статически типизированных - или не делаются вовсе, или требуют страшных слов на букву "м" (нет, не монад). К счастью, бывают исключения. Пара примеров из свеженаписанного кода:

1.

...
alias types = TypeTuple!(bool, int, double, char, string, 
                         TestStruct!false, TestStruct!true, TestClass!false, TestClass!true);
foreach(t1; types)
    foreach(t2; types) 
        testRB!(t1, t2, false)(num);

Тут функция вызывается с 81 комбинацией типов.

2.

alias MakerType(T) = T delegate();
void testHashesHisto(K, V, Hs...)(size_t num, staticMap!(MakerType, Hs) makers) {
...
    foreach(i, H; Hs) {
        auto h = makers[i]();
        measure("# " ~ H.stringof ~ ".make_histo", (){
        ...

Эта функция помимо целого числа num принимает произвольное количество функций, производящих значения указанных при ее вызове типов. Тип каждой конкретной ф-ии из тупла makers формируется применением type-level ф-ии MakerType к переданному типу из тупла Hs. В теле ее имеется цикл, проходящий по этому набору функций, на разных итерациях вызываются разные ф-ии из этого набора, получаются значения разных типов, и дальше используются как сами эти значения, так и имена их типов.

Что приятно, что тут не возникает раздумий о макросах и метапрограммировании, все пишется довольно естественно и органично, это просто код.