То, как я могу протестировать ту свою хеш-функцию, хорошо с точки зрения максимальной нагрузки?
Я прочитал различные статьи о 'Шарах и Мусорных ведрах' проблема, и кажется, что, если хеш-функция работает правильно (т.е. это - эффективно случайное распределение) затем следующее должно быть верным, если я хеширую n значения в хеш-таблицу с n слоты (или мусорные ведра):
- Вероятность, что мусорное ведро пусто для большого
n1/e. - Ожидаемое количество пустых мусорных ведер
n/e. - Вероятность, что мусорное ведро имеет
kшары<= 1/ek!(исправленный). - Вероятность, что мусорное ведро имеет, по крайней мере, k коллизии,
<= ((e/k)**k)/e(исправленный).
Они выглядят легкими проверить. Но max-load тест (максимальное количество коллизий с высокой вероятностью) обычно указывается неопределенно.
Большинство текстов указывает, что максимальное количество коллизий в любом мусорном ведре O( ln(n) / ln(ln(n)) ). Некоторые говорят, что это 3*ln(n) / ln(ln(n)). Другое бумажное соединение ln и log - обычно не определяя их или состояние это log журнал, основывают e и затем используют ln в другом месте.
ln журнал для базирования e или 2 и это max-load право формулы и как большой должен n должным быть запустить тест?
Эта лекция, кажется, покрывает его лучше всего, но я не математик.
http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture07.pdf
BTW, with high probability кажется, означает 1 - 1/n.
2 ответа
Это увлекательная статья / лекция - заставляет меня пожалеть о том, что я пошел на какой-нибудь класс формальных алгоритмов.
Я собираюсь попробовать несколько ответов здесь, основываясь на том, что я только что прочитал, и не стесняйтесь голосовать за меня. Я был бы признателен за исправление, а не за просто отрицательное голосование :) Я также собираюсь использовать здесь n и N как взаимозаменяемые, что в некоторых кругах является большим запретом, но поскольку я просто копирую вашу формулы, я надеюсь, вы меня простите.
Во-первых, база из журналов. Эти числа даны в виде большого О, а не в виде абсолютных формул. Это означает, что вы ищете что-то «порядка ln (n) / ln (ln (n))», не с ожиданием абсолютного ответа, а более того, чем больше n, тем больше отношение n к максимальное количество столкновений должно соответствовать этой формуле. Детали фактической кривой, которую вы можете построить, будут варьироваться в зависимости от реализации (и я недостаточно знаю о практических реализациях, чтобы сказать вам, что такое «хорошая» кривая, за исключением того, что она должна соответствовать этой зависимости большого О). Эти две формулы, которые вы опубликовали, фактически эквивалентны в нотации большого O. Цифра 3 во второй формуле - это просто константа, относящаяся к конкретной реализации. Менее эффективная реализация будет иметь большую константу.
Имея это в виду, я бы провел эмпирические тесты, потому что в душе я биолог и меня научили избегать жестких доказательств как указаний на то, как на самом деле устроен мир. Начните с N как некоторого числа, скажем 100, и найдите корзину с наибольшим количеством столкновений в ней. Это ваша максимальная нагрузка для этого пробега.Теперь ваши примеры должны быть как можно ближе к тому, что вы ожидаете от реальных пользователей, поэтому, возможно, вы захотите случайным образом вытащить слова из словаря или что-то подобное в качестве ввода.
Выполните этот тест много раз, по крайней мере, 30 или 40. Поскольку вы используете случайные числа, вам нужно убедиться, что средняя максимальная нагрузка, которую вы получаете, близка к теоретическому «ожиданию» вашего алгоритм. Ожидание - это просто среднее значение, но вам все равно нужно его найти, и чем точнее будет ваше стандартное отклонение / стандартное отклонение от этого среднего значения, тем больше вы можете сказать, что ваше эмпирическое среднее соответствует теоретическому ожиданию. Одного прогона недостаточно, потому что второй прогон (скорее всего) даст другой ответ.
Затем увеличьте N, скажем, 1000, 10000 и т. Д. Увеличьте его логарифмически, потому что ваша формула логарифмическая. По мере увеличения N ваша максимальная нагрузка должна увеличиваться на порядок ln (n) / ln (ln (n)). Если он увеличивается со скоростью 3 * ln (n) / ln (ln (n)), это означает, что вы следуете теории, изложенной в этой лекции.
Этот вид эмпирического теста также покажет вам, где ваш подход не работает. Возможно, ваш алгоритм хорошо работает для N <10 миллионов (или некоторого другого числа), но выше этого он начинает рушиться. Почему это могло быть? Возможно, у вас есть какое-то ограничение в 32 бита в вашем коде, не осознавая этого (т. Е. Вы используете «float» вместо «double») или какие-то другие детали реализации. Такие детали позволяют узнать, где ваш код будет хорошо работать на практике, а затем, по мере изменения ваших практических потребностей, вы можете изменить свой алгоритм.Возможно, работа алгоритма для очень больших наборов данных делает его очень неэффективным для очень маленьких или наоборот, поэтому точное определение этого компромисса поможет вам дополнительно охарактеризовать, как вы можете адаптировать свой алгоритм к конкретным ситуациям. Всегда полезный навык.
РЕДАКТИРОВАТЬ: доказательство того, почему основание функции журнала не имеет значения при использовании нотации большого O:
log N = log_10 (N) = log_b (N)/log_b (10)= (1/log_b(10)) * log_b(N)
1 / log_b (10) является константой, а в нотации большого O константы игнорируются. Базовые изменения бесплатны, поэтому вы сталкиваетесь с такими вариациями в статьях.
После некоторых дополнительных исследований и проб и ошибок, я думаю, что смогу частично дать ответ.
Начнем с того, что
lnиlog, похоже, относятся к log base-e, если вы посмотрите на математику, лежащую в основе теории. Но, как указано mmr, для оценок O (...) это не имеет значения.max-loadможно определить с любой вероятностью, которая вам нравится. Типичная используемая формула -1-1 / n ** c
В большинстве статей по данной теме используется
1-1/n
Самый простой пример.
Допустим, у вас есть хеш-таблица из 1000 слотов, и вы хотите хешировать 1000 элементов. Допустим, вы также хотите узнать max-load с вероятностью 1-1 / 1000 или 0,999 .
max-load - это максимальное количество хеш-значений, которые в конечном итоге совпадают, т.е.коллизии (при условии, что ваша хеш-функция в порядке).
Используя формулу для вероятности получения точно k идентичных хеш-значений
Pr[ exactly k ] = ((e/k)**k)/e
, затем путем накопления вероятности точно 0..k элементов до тех пор, пока общая сумма не станет равной или превысит 0,999 сообщает вам, что k - это максимальная нагрузка .
например.
Pr[0] = 0.37
Pr[1] = 0.37
Pr[2] = 0.18
Pr[3] = 0.061
Pr[4] = 0.015
Pr[5] = 0.003 // here, the cumulative total is 0.999
Pr[6] = 0.0005
Pr[7] = 0.00007
Итак, в этом случае максимальная загрузка равна 5 .
Итак, если моя хеш-функция хорошо работает с моим набором данных, я должен ожидать, что максимальное количество идентичных хеш-значений (или коллизий) будет 5 .
Если это не так, то это может быть связано со следующими причинами:
В ваших данных есть небольшие значения (например, короткие строки), хэш которых соответствует одному и тому же значению. Любой хэш одного символа ASCII выберет 1 из 128 хеш-значений (есть способы обойти это. Например, вы можете использовать несколько хеш-функций, но они замедляют хеширование, и я мало что знаю об этом).
Ваша хеш-функция плохо работает с вашими данными - попробуйте ее со случайными данными.
Ваша хеш-функция работает некорректно.
Другие тесты, которые я упомянул в своем вопросе, также помогают убедиться, что ваша хеш-функция работает должным образом.
Между прочим, моя хеш-функция работала хорошо - за исключением коротких (1..4 символов) строк.
Я также реализовал простую версию с разделенной таблицей, в которой хеш-значение помещается в наименее используемый слот из двух мест. Это более чем вдвое снижает количество коллизий и означает, что добавление и поиск в хеш-таблице происходит немного медленнее.
Надеюсь, это поможет.