улучшить хеширование с помощью генетического программирования/алгоритма

Я пишу программу, которая может значительно уменьшить количество коллизий, возникающих при использовании хеш-функций, таких как «key mod table_size». Для этого я хотел бы использовать генетическое программирование/алгоритм. Но я мало что знаю об этом. Даже прочитав множество статей и примеров, я не знаю, что в моем случае (как и в определении программы) будет функцией пригодности, целью (целью обычно является требуемый результат), что будет представлять собой популяцию/индивидов и родителей, и Т. Д.

Пожалуйста, помогите мне определить вышеизложенное и, если возможно, несколько кодов/псевдокодов, так как это мой проект.

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

Благодарность..


hash genetic-algorithm evolutionary-algorithm genetic-programming
person TheLinuxEvangelist    schedule 04.11.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

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

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

Другой вопрос, как вы хотите представить свою функцию? Просто логическое выражение? Что-то, построенное из словесных операций, таких как AND, XOR, NOT, ROT? В зависимости от ваших ограничений (точнее, предположений) вопрос приспособленности и мутации будет другим.

person Krystian    schedule 04.11.2014

arrow_upward
0
arrow_downward

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

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

Итак, все сводится к тому, какие размеры таблиц попробовать и какую меру аккуратности применить. Доброжелательность зависит от контекста. Вы можете измерить «самое полное ведро» как меру времени вставки/поиска «наихудшего случая». Вы можете измерить сумму квадратов размеров корзины как меру «среднего» времени вставки/поиска на основе равномерного распределения поиска среди ключей.

Наконец, вам нужно решить, какой размер таблицы (или размеры) нужно тестировать. Принято считать, что простые числа часто используются, потому что хэш по простому модулю имеет тенденцию быть хорошо изменчивым для всех битов в хеше, тогда как что-то вроде хэша по модулю 2 ^ n включает только младшие n-1 бит. Чтобы уменьшить количество вычислений, вы можете рассматривать ряд следующего простого числа больше, чем каждая степень двойки. 5(>2^2) 11 (>2^3), 17 (>2^4) и т. д. до первой степени числа 2 включительно, превышающей размер вашей «выборки».

Существуют и другие способы рассмотрения пригодности, но без практического применения вопрос (конечно) нечетко определен.

Если ваше «пространство» потенциальных хеш-функций не имеет одинакового времени выполнения, вы также должны учитывать «стоимость». Довольно легко определить очень хорошие хеш-функции, но время выполнения может быть важным фактором.

person Persixty    schedule 04.11.2014