Самопознание

человеческий потенциал безграничен

Хеши

03.11.2011


  • правовые рассуждения на балконе

  • Средние потребительские цены на топливо на 9 февраля 2009 года по данным Росстата

  •  В очередной раз посмотрел в профайлере кода поиска Яндекса, и меня посетило чувство легкой грусти. В его топе не видно функций, которые надо уговаривать побыстрее работать. Есть код, который явно надо написать покрасивее, порасширяемее и почище, а тормозного кода не нету.

    Решил не терять квалификацию.  Вспомнил, что давно (уже 3 года) хотел поглядеть на хеши от Гулина: тымц#1 и тымц#1. Поглядел, пишу маленький отчет.

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

    Автор изготавливает хеш без коллизий на заданном множестве. Изготавливает его следующим образом: cначала берет две хеш функции h(x) и g(x), потом по ним находит массив чисел value, такой что функция f(x) = value[h(x)] + value[g(x)]  принимает на исходном множестве строк все значения от 0 до N - 1, причем принимает один раз, причем f(x) совпадает с порядковым номером строки в исходном множестве. Массив value существует не для всех функций, автор перебором находит две достаточно ортогональные хеш функции.

    Берем код по ссылке, запускаем, получаем на ноутбуке с i5 скорость поиска в  3.1736 миллионов строчек в секунду. Глаз наталкивается на strcmp для сравнения строк и на такую уйобищную хеш функцию.  

    Давайте напишем внятный код? 

    Хуяк! Вот это строчечка длины до 8 байт,  простая хеш функция и хеш функция сразу с 2 значениями, и функция сравнения двух таких строчечек. 

    struct TStrS {    ui64 Buffer[1];    ui64 Hash() const {        ui64 v = Buffer[0] * r;        v = v ^ (v >> 33);        return v >> 17;    }    void Hash(const THashTable &table, ui64 &v1, ui64 &v2) const {        v1 = Buffer[0] * table.Seed1[0];        v2 = Buffer[0] * table.Seed2[0];        v1 = v1 ^ (v1 >> 33);        v2 = v2 ^ (v2 >> 33);        v1 = (v1 >> 17) & table.Size;        v2 = (v2 >> 17) & table.Size;    }    bool IsEqual(const TStrS &str) const {        return Buffer[0] == str.Buffer[0];    }};
    _Winnie C++ Colorizer

    Хуяк! Вот это строчечка длины до 16 байт, простая хеш функция и хеш функция сразу с 2 значениями, и функция сравнения двух таких строчечек. 

    struct TStrL {    ui64 Buffer[2];    ui64 Hash() const {        ui64 v = (Buffer[0] * r) ^ (Buffer[1] * r);        v = v ^ (v >> 33);        return v >> 17;    }    void Hash(const THashTable &table, ui64 &v1, ui64 &v2) const {        v1 = (Buffer[0] * table.Seed1[0]) ^ (Buffer[1] * table.Seed1[1]);        v2 = (Buffer[0] * table.Seed2[0]) ^ (Buffer[1] * table.Seed2[1]);        v1 = v1 ^ (v1 >> 33);        v2 = v2 ^ (v2 >> 33);        v1 = (v1 >> 17) & table.Size;        v2 = (v2 >> 17) & table.Size;    }    bool IsEqual(const TStrL &str) const {        return Buffer[0] == str.Buffer[0] && Buffer[1] == str.Buffer[1];    }};
    _Winnie C++ Colorizer

    Ну и длинная строчка:

    struct TStrX {    ui64 *Buffer;    ui64 Length;    ui64 Hash() const {        ui64 v = 0;        for (ui64 i = 0; i < Length; ++i)            v = v ^ (Buffer[i] * r);        v = v ^ (v >> 33);        return v >> 17;    }    void Hash(const THashTable &table, ui64 &v1, ui64 &v2) const {        v1 = 0;        v2 = 0;        for (ui64 i = 0; i < Length; ++i) {            v1 = v1 ^ (Buffer[i] * table.Seed1[i]);            v2 = v2 ^ (Buffer[i] * table.Seed2[i]);        }        v1 = v1 ^ (v1 >> 33);        v2 = v2 ^ (v2 >> 33);        v1 = (v1 >> 17) & table.Size;        v2 = (v2 >> 17) & table.Size;    }    bool IsEqual(const TStrX &str) const {
    
            if (str.Length != Length)            return false;
    
            for (ui64 i = 0; i < Length; ++i)            if (Buffer[i] != str.Buffer[i])                return false;
    
            return true;    }};
    _Winnie C++ Colorizer

    Строчек длиной до 8 байт в коллекции 70 процентов, 30 процентов 16 байтных, длинные строчки присутствуют в следовых значениях, 

    Как писать код дальше - совершенно понятно. Строчечка состоит из union'а строк 3 типов, и числа, говорящего, какой именно тип имеет данная строка.  Для трех типов строчек 3 разные ветки кода про хеша и сравнение строчек. Берем из кода Гулина построение идеального хеша по двум заданным функциям. Получаем 6.29723 миллионов запросов в секунду.

    А теперь давайте и выкинем идеальный хеш. Что от него, кроме расстройства? Надо считать две хеш функции, два раза смотреть в массив (два кеш мисса), потом еще один раз сравнивать в массиве со строчками.

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

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

    Получаем 8.76424 миллионов запросов в секунду. А что удивительного? Хеш функция одна, а не две, не надо дважды смотреть в промежуточный массив и промахиваться в кеше. Типичное сравнение - сравнение ui64. Типичный hash - умножение 64 битных чисел и пара сдвигов.

    Вот исходники. Напомню, что первоначальные исходники и тестовый файл со строчками можно взять тут.

    Забавным образом видна цена абстракции в чистом виде. 


  • правовые рассуждения на балконе

  • Средние потребительские цены на топливо на 9 февраля 2009 года по данным Росстата






  • Последние новости


    Дружба

    Все жизненные проблемы приносят с собой золотые самородки мудрости, обнаружить которые помогает истинная дружба. Вы замечали, что есть люди, которые дают вам силы, поднимают настроение и вызывают желание находиться рядом? И те, кто стремится вытянуть из вас энергию, надоедает вам и делает все так, что хочется сбежать. Нас подде...
    Читать далее »

    Советы, способствующие успеху

    ВЫЯВЛЕНИЕ ЦЕННОСТЕЙ Правильный выбор – Это результат жизни в соответствии со своими высшими ценностями, то есть путь к лучшей жизни. ЖИЗНЕННАЯ ЦЕЛЬ Лучшие люди выбирают цель, которая затрагивает лучшие струны в других. МИССИЯ Жизнь нельзя прожить дважды. Теперь или никогда, поэто...
    Читать далее »

    Утренние вопросы

    Если бы мне осталось жить всего месяц, что бы я делал из того, что делаю сегодня? Что я сделаю сегодня, чтобы почувствовать себя счастливым? Какие прекрасные воспоминания останутся у меня в памяти сегодня? Какие убеждения сделали мою жизнь такой, какая она есть? Во что нужно поверить, чтобы прожить удивительную жизнь? ...
    Читать далее »

    И еще несколько вопросов

    Знать мысли Бога – все равно что знать, как преуспеть в жизни. Глубоко поразмыслив над вопросами этой книги и записав свои ответы в дневник, вы развили в себе привычку анализировать. Поздравляю! Это важнейший навык успешной жизни. Способность к самоанализу и постановке правильных вопросов наряду с пониманием того, как использовать интуицию и природную мудрость, изменит нап...
    Читать далее »

    Путешествия

    Поставьте перед собой цель жить полноценно. Самый печальный итог – оглянуться назад и вопрошать, что можно было бы иметь, если бы… Дорожите своими заветными мечтами, воплощая их в жизнь. Ах, путешествия… Большинство из нас любят путешествовать и страстно стремятся к этому. Мы тоскуем по приключениям в реальной жизни. Хотим посетить удаленные места, узнать культуры, не...
    Читать далее »

    Счастье

    Там, где жизнь бьет ключом, где оживленно и весело, там и ищите свое счастье. Моя шестилетняя внучка Элла однажды зашла в мой офис и уселась в кресло. Она давно слышала, что я занимаюсь коучингом, поэтому я спросил ее: «Не хочешь побыть сегодня тренером и немного поучить других?» Малышка посмотрела на меня, выпрямилась в кресле, и я понял: она готова. Элла спросила: – О ч...
    Читать далее »

    Взаимоотношения

    Любовь Магия Бога выражается через любовь; наивысшая форма любви – бескорыстная помощь другим. Вы когда нибудь смотрели в глаза новорожденного и ощущали восторг, который ребенок приносит в этот мир? Большинство из нас чувствуют исходящую от детей любовь. Мы являемся в мир с любовью и открытым сердцем. С самого детства мы отдаем свою любовь этому миру. Из л...
    Читать далее »

    Ваш комментарий:


    Вы должны войти в систему, чтобы оставить комментарий.