OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 29 Март, 2024 02:57

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 103 ]  На страницу 1, 2, 3, 4, 5, 6  След.
Автор Сообщение
СообщениеДобавлено: Четверг, 25 Август, 2011 13:51 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Пробую различные алгоритмы хэширования и обнаружил следующий, так сказать, закон природы.

Если значение хэшкода 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 с копейками процентов не получается :roll: :roll: :roll:

Что это за закон природы такой?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 14:16 
Аватара пользователя

Зарегистрирован: Пятница, 11 Май, 2007 21:57
Сообщения: 1488
Откуда: Украина, Киев
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.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 15:21 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N.
0.63


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 15:26 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Ярослав Романченко писал(а):
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.
Они говорят, что скорость поиска перестаёт быть постоянной и начинает увеличиваться если хэштаблица заполнена более чем на 2/3.
albobin писал(а):
Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N.
0.63
Вот только почему? Где-то тут, видимо, запрятана центральная предельная теорема...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 15:40 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Сергей Губанов писал(а):
Ярослав Романченко писал(а):
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.
Они говорят, что скорость поиска перестаёт быть постоянной и начинает увеличиваться если хэштаблица заполнена более чем на 2/3.
albobin писал(а):
Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N.
0.63
Вот только почему? Где-то тут, видимо, запрятана центральная предельная теорема...

Почему что?
1. Почему 0.63 в "Сгенерите N раз случайное целое число из диапазона 1..N ..." ?
или
2. Почему в исходной проблеме те же 0.63?

IMHO это по сути одно и то же.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 15:44 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Придумал формулу:

0.63212.... = 1 - 1/e = 1 - Limit[(1 - 1/n)^n, n->Infinity]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 15:54 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Вероятность того что два числа совпадут равна 1/N, а не совпадут равна 1 - 1/N. Вероятность того что все числа будут разными равна (1 - 1/N)^N-1, то есть примерно 1/e = 0.367879. А вероятность совпадений 1 - 1/e = 0.632121


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 16:00 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Сергей Губанов писал(а):
Вероятность того что два числа совпадут равна 1/N, а не совпадут равна 1 - 1/N. Вероятность того что все числа будут разными равна (1 - 1/N)^N-1, то есть примерно 1/e = 0.367879. А вероятность совпадений 1 - 1/e = 0.632121
Сергей Губанов писал(а):
...
Перепробовал кучу других вариантов какие-только в голову пришли, но лучше чем 63 с копейками процентов не получается :roll: :roll: :roll:
Что это за закон природы такой?
Так получается, что все сгенерированные числа могут быть разными? Или только в бесконечности? :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 16:12 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Да, точно. Это я не правильно сказал. Надо ещё раз подумать.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 16:17 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Я не к тому, что формула неправильная... просто м.б. смысл у неё другой... допустим, не вероятностный?..
Интуитивно кажется - это как бы "предел возможности имитировать алгоритмически" разнообразие действительности...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 16:27 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
0.63 естественно при N не равном 2 :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 16:28 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
Сергей Губанов писал(а):
Вероятность того что два числа совпадут равна 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 19:59, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 16:34 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Александр Ильин писал(а):
...
Естественно, при равной вероятности выпадения всех чисел.
Как я понимаю, у Сергея "образовался закон", о котором говорил allbobin - что всегда в выборке из N чисел, "случайно" составленной по любому алгоритму, будет не более, чем ок.63% разных числовых объектов. Т.е. ок. 37% членов выборки будут совпадать с уже имеющимися.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 17:11 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Драконограф писал(а):
Я не к тому, что формула неправильная... просто м.б. смысл у неё другой...
Да формула просто угадана. Смысл пока не понят.

Видимо рассуждать следует так. Есть таблица на 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 не будут практически никогда.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 17:30 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
IMHO формула должна быть ((N-1)/N)^N
трактовка такова: это вероятность непопадания в конкретную ячейку, а это и есть доля "дыр" во всём диапазоне
остаётся только вычесть из единицы и получить "заполненность" диапазона


Последний раз редактировалось albobin Пятница, 26 Август, 2011 16:22, всего редактировалось 3 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 17:35 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Сергей Губанов писал(а):
На каждом шаге
Ф[X] переходит в Ф[X-1] с вероятностью X/N
или
Ф[X] остаётся самой собой с вероятностью (N-X)/N
Нарисовал начало этого процесса для N=10:
Вложение:
graph.png
graph.png [ 11.19 КБ | Просмотров: 13082 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 18:59 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Полный граф для N=5 (красная линия - наиболее вероятный путь)
Вложение:
graph5.png
graph5.png [ 10.72 КБ | Просмотров: 13066 ]


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 19:54 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
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 числа:
      да                    да                   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
Легко показать, что сумма строк правого столбца - это расписанный куб разности (1-1/4)^3 = (1-1/N)^(N-1) = 27/64 = (3/4)^3.

Для N = 5 таблица истинности опять увеличится вдвое, и т.д.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 20:08 

Зарегистрирован: Воскресенье, 01 Ноябрь, 2009 05:13
Сообщения: 2046
Вот что вызывает вопрос:
albobin в viewtopic.php?p=64996#p64996 писал(а):
Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N.
0.63
Если понимать это как экспериментальный факт (как и результаты Сергея), то надо принять, что 0,63 - это верхняя граница доли уникальных чисел в псевдослучайной последовательности при сколь угодно большой её длине N. И выходит, что вероятность события "все числа в последовательности разные" равна нулю... как и более широкого события "доля разных чисел в последовательности превышает 0,63". Т.е. такое приложение вероятности, получается, здесь не проходит... или это не надо понимать как верхнюю границу?..


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 25 Август, 2011 20:12 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Александр Ильин писал(а):
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
Остаётся лишь только интерпретировать нужным образом, как "заполненность" ячейки и / или всего диапазона.


Последний раз редактировалось albobin Пятница, 26 Август, 2011 16:22, всего редактировалось 4 раз(а).

Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 103 ]  На страницу 1, 2, 3, 4, 5, 6  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 6


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

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB