#perl #hash #perfect-hash
#perl #хэш #идеальный хэш
Вопрос:
Я собираюсь использовать хранилище ключей: значений и хотел бы создать непротиворечивые хэши в Perl. Есть ли модуль или функция Perl, которые я могу использовать для создания неколлирируемой хэш-функции или таблицы (может быть, что-то вроде gperf)? Я уже знаю свой диапазон входных значений.
Комментарии:
1. А. Сбой понимания прочитанного. Извините за это…
2. Нет, совершенно круто. Спасибо, что дали мне лучшее представление о том, как быстро можно создавать хэши в Perl 🙂 Я мог бы просто использовать gperf с XS
Ответ №1:
Я не могу найти чисто Perl-решение, ближе всего к исследованиям Рейни Урбан по использованию совершенных хэшей с системой типов. Если бы вы делали это в XS, CMPH (библиотека минимального идеального хеширования C) могла бы быть более подходящей, чем gperf. CMPH, похоже, оптимизирован для нетривиальных размеров ключей и генерации во время выполнения.
Стоимость создания идеальной хэш-функции во время выполнения в Perl может снизить ценность ее использования. Чтобы получить выгоду, вы бы хотели, чтобы она была скомпилирована и кэширована. Итак, опять же, лучшим вариантом может быть написание модуля XS, который генерирует функцию из списка фиксированных ключей во время компиляции XS.
Из любопытства, насколько велики ваши данные и сколько ключей содержит набор?
Комментарии:
1. Я ТОЛЬКО начинаю понимать, как работает хеширование, так что на данный момент это кажется правильным решением. Я собираюсь использовать ее в качестве ключа в хранилище ключей: значений, возможно, LevelDB. По сути, мне нужно хранилище key:value или multi-key:value, чтобы просто выполнять простые подсчеты дублирования (агрегирование) для ключа в системе реального времени с высокой скоростью записи. Ключ считается в течение 24 часов, затем этот агрегат сбрасывается в файл CSV, и хранилище будет удалено за этот день.
2. Данные, которые я хочу сохранить, имеют длину около 1 КБ на запись, а общее количество записей превышает 2 гигабайта в день. Ключи довольно длинные; около 30 символов и несколько чисел int. Я не знаю, выполнимо ли это.
3. @EhevuTov Я бы настоятельно рекомендовал вам сначала оценить производительность вашей системы с помощью вашей базы данных, прежде чем использовать идеальный алгоритм хэширования. Если ваши данные не являются патологическими, и я подозреваю, что стандартный алгоритм хэширования для LevelDB довольно хорош, коллизии хэшей вряд ли будут вашим узким местом.
4. @EhevuTov Читая LevelDB, наиболее вопиющей проблемой с точки зрения производительности является то, что «только один процесс (возможно, многопоточный) может одновременно обращаться к определенной базе данных», что значительно ограничивает ваш доступ к данным, способность работать параллельно или использовать больше оборудования для решения проблемы. Возможно, вы захотите начать с менее простой базы данных.
5. Ну, это тяжелая система ввода-вывода для записи, поэтому, если я добавлю больше потоков в ввод-вывод, я бы подумал, что это уменьшит, а не увеличит производительность. Я бы обработал хэши с помощью некоторого типа хэш-пула. Я рассматриваю SQLite и MongoDB в качестве альтернатив, но сомневаюсь, что они будут такими же быстрыми.
Ответ №2:
Возможно, вас заинтересует Джуди. Это не реализация хэш-таблицы, но предположительно это очень эффективная реализация ассоциативного массива.
Имейте в виду, хэши Perl очень хорошо настроены, и они автоматически перефразируются, когда объем корзины начинает увеличиваться.
Комментарии:
1. спасибо за предупреждение. Возможно, я использую Judy для другого проекта. Я работаю над системой реального времени, поэтому повторный хэш мне не подходит. Похоже, мне также может понадобиться создать рабочие процессы для хеширования. Пока не уверен, как это сделать.