OberonCore https://forum.oberoncore.ru/ |
|
Хэш 63% - что это за закон природы такой? https://forum.oberoncore.ru/viewtopic.php?f=27&t=3554 |
Страница 1 из 6 |
Автор: | Сергей Губанов [ Четверг, 25 Август, 2011 13:51 ] |
Заголовок сообщения: | Хэш 63% - что это за закон природы такой? |
Пробую различные алгоритмы хэширования и обнаружил следующий, так сказать, закон природы. Если значение хэшкода h ограничено диапазоном (0 <= h) & (h < N), то при хэшировании N случайных объектов различных хэшкодов получается примерно 0.63 * N или меньше если хэшфункция совсем плохая. Придумать хэшфункцию ограниченную числом N, которая при хэшировании N случайных объектов выдавала бы больше чем 63 процента с копейками различных хэшкодов не удаётся, почему-то. Наиболее простая "63%" хэшфункция: Код: private static unsafe uint Hash (char* a, int n) { uint h = 0; int i = 0; while (i < n) { h = h * 2 + a[i++]; } return h % N; } Перепробовал кучу других вариантов какие-только в голову пришли, но лучше чем 63 с копейками процентов не получается Что это за закон природы такой? |
Автор: | Ярослав Романченко [ Четверг, 25 Август, 2011 14:16 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
http://en.wikipedia.org/wiki/Hash_table#Load_factor Цитата: With a good hash function, the average lookup cost is nearly constant as the load factor increases from 0 up to 0.7(about 2/3 full) or so.[citation needed] Beyond that point, the probability of collisions and the cost of handling them increases.
|
Автор: | albobin [ Четверг, 25 Август, 2011 15:21 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N. 0.63 |
Автор: | Сергей Губанов [ Четверг, 25 Август, 2011 15:26 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Ярослав Романченко писал(а): http://en.wikipedia.org/wiki/Hash_table#Load_factor Они говорят, что скорость поиска перестаёт быть постоянной и начинает увеличиваться если хэштаблица заполнена более чем на 2/3. Цитата: With a good hash function, the average lookup cost is nearly constant as the load factor increases from 0 up to 0.7(about 2/3 full) or so.[citation needed] Beyond that point, the probability of collisions and the cost of handling them increases. albobin писал(а): Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N. Вот только почему? Где-то тут, видимо, запрятана центральная предельная теорема...
0.63 |
Автор: | albobin [ Четверг, 25 Август, 2011 15:40 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Сергей Губанов писал(а): Ярослав Романченко писал(а): http://en.wikipedia.org/wiki/Hash_table#Load_factor Они говорят, что скорость поиска перестаёт быть постоянной и начинает увеличиваться если хэштаблица заполнена более чем на 2/3. Цитата: With a good hash function, the average lookup cost is nearly constant as the load factor increases from 0 up to 0.7(about 2/3 full) or so.[citation needed] Beyond that point, the probability of collisions and the cost of handling them increases. albobin писал(а): Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N. Вот только почему? Где-то тут, видимо, запрятана центральная предельная теорема...0.63 Почему что? 1. Почему 0.63 в "Сгенерите N раз случайное целое число из диапазона 1..N ..." ? или 2. Почему в исходной проблеме те же 0.63? IMHO это по сути одно и то же. |
Автор: | Сергей Губанов [ Четверг, 25 Август, 2011 15:44 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Придумал формулу: 0.63212.... = 1 - 1/e = 1 - Limit[(1 - 1/n)^n, n->Infinity] |
Автор: | Сергей Губанов [ Четверг, 25 Август, 2011 15:54 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Вероятность того что два числа совпадут равна 1/N, а не совпадут равна 1 - 1/N. Вероятность того что все числа будут разными равна (1 - 1/N)^N-1, то есть примерно 1/e = 0.367879. А вероятность совпадений 1 - 1/e = 0.632121 |
Автор: | Владислав Жаринов [ Четверг, 25 Август, 2011 16:00 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Сергей Губанов писал(а): Вероятность того что два числа совпадут равна 1/N, а не совпадут равна 1 - 1/N. Вероятность того что все числа будут разными равна (1 - 1/N)^N-1, то есть примерно 1/e = 0.367879. А вероятность совпадений 1 - 1/e = 0.632121 Сергей Губанов писал(а): ... Так получается, что все сгенерированные числа могут быть разными? Или только в бесконечности?
Перепробовал кучу других вариантов какие-только в голову пришли, но лучше чем 63 с копейками процентов не получается Что это за закон природы такой? |
Автор: | Сергей Губанов [ Четверг, 25 Август, 2011 16:12 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Да, точно. Это я не правильно сказал. Надо ещё раз подумать. |
Автор: | Владислав Жаринов [ Четверг, 25 Август, 2011 16:17 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Я не к тому, что формула неправильная... просто м.б. смысл у неё другой... допустим, не вероятностный?.. Интуитивно кажется - это как бы "предел возможности имитировать алгоритмически" разнообразие действительности... |
Автор: | albobin [ Четверг, 25 Август, 2011 16:27 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
0.63 естественно при N не равном 2 |
Автор: | Александр Ильин [ Четверг, 25 Август, 2011 16:28 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Сергей Губанов писал(а): Вероятность того что два числа совпадут равна 1/N, а не совпадут равна 1 - 1/N. Вероятность того что все числа будут разными равна (1 - 1/N)^N-1, то есть примерно 1/e = 0.367879. А вероятность совпадений 1 - 1/e = 0.632121 Всё правильно, при N стремящемся к бесконечности такой предел и будет: N = 1 => 1 N = 2 => 0.5 N = 3 => 4/9 = 0,44[4] N = 4 => 27/64 = 0,390625 ... Естественно, при равной вероятности выпадения всех чисел. Доп: Исправил одну цифру. |
Автор: | Владислав Жаринов [ Четверг, 25 Август, 2011 16:34 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Александр Ильин писал(а): ... Как я понимаю, у Сергея "образовался закон", о котором говорил allbobin - что всегда в выборке из N чисел, "случайно" составленной по любому алгоритму, будет не более, чем ок.63% разных числовых объектов. Т.е. ок. 37% членов выборки будут совпадать с уже имеющимися.
Естественно, при равной вероятности выпадения всех чисел. |
Автор: | Сергей Губанов [ Четверг, 25 Август, 2011 17:11 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Драконограф писал(а): Я не к тому, что формула неправильная... просто м.б. смысл у неё другой... Да формула просто угадана. Смысл пока не понят.Видимо рассуждать следует так. Есть таблица на N значений. Начинаем её заполнять. На каком-то шаге в ней X ячеек пусты и N-X ячеек заполнены быть может с повторениями (начальное значение X=N). Добавляем ещё одно случайное число. Оно может попасть в незаполненную ячейку с вероятностью X/N или в уже заполненную с вероятностью (N-X)/N. Попав в свободную ячейку оно уменьшит количество свободных ячеек на единицу. А попав в заполненную ячейку оно не изменяет состояние Ф[X] системы. Рисуем граф переходов: На каждом шаге Ф[X] переходит в Ф[X-1] с вероятностью X/N или Ф[X] остаётся самой собой с вероятностью (N-X)/N Надо видимо отыскать наиболее вероятный путь в этом графе переходов. Кстати, вероятность того что все числа будут разными равна (N/N)*((N-1)/N)*((N-2)/N)*((N-3)/N)*...*(3/N)*(2/N)*(1/N). Для N=10 это 0.00036288, для N=20 это 2.3202*10^{-8}. Вобщем, все числа разными при больших N не будут практически никогда. |
Автор: | albobin [ Четверг, 25 Август, 2011 17:30 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
IMHO формула должна быть ((N-1)/N)^N трактовка такова: это вероятность непопадания в конкретную ячейку, а это и есть доля "дыр" во всём диапазоне остаётся только вычесть из единицы и получить "заполненность" диапазона |
Автор: | Сергей Губанов [ Четверг, 25 Август, 2011 17:35 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Сергей Губанов писал(а): На каждом шаге Нарисовал начало этого процесса для N=10:Ф[X] переходит в Ф[X-1] с вероятностью X/N или Ф[X] остаётся самой собой с вероятностью (N-X)/N Вложение: graph.png [ 11.19 КБ | Просмотров: 13239 ] |
Автор: | Сергей Губанов [ Четверг, 25 Август, 2011 18:59 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Полный граф для N=5 (красная линия - наиболее вероятный путь) Вложение: graph5.png [ 10.72 КБ | Просмотров: 13223 ] |
Автор: | Александр Ильин [ Четверг, 25 Август, 2011 19:54 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
albobin писал(а): IMHO формула должна быть ((N-1)/N)^N Неа, у Сергея Губанова правильная формула. У вас показатель степени не тот, должен быть N-1. А возводимая в степень часть (N-1)/N = N/N - 1/N = 1 - 1/N, т.е. как у Сергея.Смотрите, для N = 3: 1) первое число уникально с вероятностью = 1; 2) второе число либо уникально с вероятностью = (N-1)/N, т.е. 2/3, либо совпадает с первым числом с вероятностью = 1/3 = 1-(N-1)/N; 3) третье число: - если первые два числа равны, то третье уникально с вероятностью = 2/3; сам этот вариант имеет вероятность = 1/3 (см. пункт 2), т.е. общая вероятность = 1/3*2/3; - если первые два числа не равны (уникальны), то третье уникально с вероятностью = 1/3; сам этот вариант имеет вероятность = 2/3 (см. пункт 2), т.е. общая вероятность = 1/3*2/3; Итого: третье число уникально с вероятностью = 1/3*2/3+1/3*2/3 = 2/9+2/9 = 4/9 = (1-1/N)^(N-1) = (1-1/3)^2 = (2/3)^2 = 4/9. Для N = 4: 1) аналогично; 2) аналогично, только N = 4, т.е. второе число либо равно первому с вероятностью 1/4, либо уникально с вероятностью 3/4; 3) - если первые два равны, то общая вероятность уникальности третьего = 1/4*3/4; - если первые два уникальны, то общая вероятность уникальности третьего = 3/4*2/4; 4) здесь у нас уже 4 варианта в соответствии с таблицей истинности: Код: 2 число уникально? 3 число уникально? вероятность уникальности 4 числа: Легко показать, что сумма строк правого столбца - это расписанный куб разности (1-1/4)^3 = (1-1/N)^(N-1) = 27/64 = (3/4)^3.да да 3/4*2/4*1/4 = 6/64 да нет 3/4*2/4*2/4 = 12/64 нет да 1/4*3/4*2/4 = 6/64 нет нет 1/4*1/4*3/4 = 3/64 Для N = 5 таблица истинности опять увеличится вдвое, и т.д. |
Автор: | Владислав Жаринов [ Четверг, 25 Август, 2011 20:08 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Вот что вызывает вопрос: albobin в viewtopic.php?p=64996#p64996 писал(а): Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N. Если понимать это как экспериментальный факт (как и результаты Сергея), то надо принять, что 0,63 - это верхняя граница доли уникальных чисел в псевдослучайной последовательности при сколь угодно большой её длине N. И выходит, что вероятность события "все числа в последовательности разные" равна нулю... как и более широкого события "доля разных чисел в последовательности превышает 0,63". Т.е. такое приложение вероятности, получается, здесь не проходит... или это не надо понимать как верхнюю границу?..
0.63 |
Автор: | albobin [ Четверг, 25 Август, 2011 20:12 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Александр Ильин писал(а): albobin писал(а): IMHO формула должна быть ((N-1)/N)^N Неа, у Сергея Губанова правильная формула. У вас показатель степени не тот, должен быть N-1. А возводимая в степень часть (N-1)/N = N/N - 1/N = 1 - 1/N, т.е. как у Сергея.Вероятность непопадания в конкретную ячейку за один "выстрел" равно (N-1)/N, ( N-1 для наглядности) Вер.-ть. N непопаданий в конкретную ячейку соответственно степень N, X=((N-1)/N)^N Вер-ть того что было хотя бы одно попадание в конкретную ячейку равно 1-X Остаётся лишь только интерпретировать нужным образом, как "заполненность" ячейки и / или всего диапазона. |
Страница 1 из 6 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |