OberonCore :: Просмотр темы - Хэш 63% - что это за закон природы такой?

Александр Ильин писал(а):

В общем, чем жёстче условия на последовательность, тем меньше вероятность соответствия ей, и вероятности эти надо по-разному высчитывать.

Вероятность появления любой конкретной последовательности чисел одинакова и равна (1/N)^N

Я тут было засомневался в том, а правильно ли делать вывод 2. сразу же из 1. , но потом на досуге не нашёл опровержений.

Формула такая же, как и приведённая Trurl-ем на 2 странице. Только описка в трактовке числа N^N.

Сергею Губанову.
Вот наткнулся на Tiger.
http://ru.wikipedia.org/wiki/Tiger_%28% ... 8%D1%8F%29
http://ru.wikipedia.org/wiki/TTH
C ним не пробовали поэкспериментировать?

...
Сформулирую "достижение мысли" этой ветки форума. Эффективность (для построения хэштаблицы) идеальной хэшфункции равна 1-1/e. Около этого значения очень маленькая дисперсия. Поэтому при больших N совершенно бессмысленно брать сложную хэшфункцию с эффективностью, например, 0.632, если самая простая имеет эффективность 0.631 (всего на одну тысячную меньше).
...

...
Я не следил за диспутом, но было бы странно, если бы такой вероятностный закон не был известен. В физике, во всяком случае, это было бы странно (не случайно физик, столкнувшись с задачей, сразу в пунктик пальцем ткнул).
...

albobin писал(а):

Наверное, не совсем правильно, но легко поправимо. Из 1 следует, что у нас биномиальное распределение, а для него матожидание = np, т.е n*(1+1/n)^n.

... Л.Д. Ландау (кажется) спросили, что он может сказать об учёном Н. как о физике. Ландау ответил: "Физики получают результаты, а Н. доказывает теоремы."

В то же время необязательна оппозиция мышлений. ...

Книжки почитать правильней, но ответ то хочется знать без приложения усилий

1. N раз генерируем число из диапазона 1..N, для каждого числа вероятность появления в одной попытке одинакова и равна 1/N, и непоявления (1-1/N)
2. Для любого из чисел 1..N вероятность события "это число ни разу за N попыток не сгенерировано" равна (1-1/N)^N

... Другими словами ...

albobin писал(а):

Для простоты обозначим эту вероятность p.
Для любых k чисел вероятность события "за N попыток ни разу не сгенерированы эти и только эти числа" равна p^k*(1-p)^(N-k) ...

...
Опять возражаю.
Нельзя применять перемножение вероятностей, события не независимы

Мы можем строить сложные события вовлекающие несколько значений только с условием непересечения их в пределах каждой попытки.
...

albobin писал(а):

...
Опять возражаю.
Нельзя применять перемножение вероятностей, события не независимы

Не понял... имеется в виду, что алгоритм генерации как бы обладает данными, какие числа из интервала уже были сгенерированы?..

Рассмотрим ситуацию.
событие A: негенерация числа A за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа B.
событие B: негенерация числа B за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа А.
Отсюда и отсутствие независимости.
из A может следовать 'не B' и наоборот.

Автор:	Александр Ильин [ Понедельник, 29 Август, 2011 16:35 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
albobin писал(а): Александр Ильин писал(а): В общем, чем жёстче условия на последовательность, тем меньше вероятность соответствия ей, и вероятности эти надо по-разному высчитывать. Вероятность появления любой конкретной последовательности чисел одинакова и равна (1/N)^N Да, это минимальная вероятность. Я имел в виду условия вида: "Какова вероятность того, что среди выпавших неуникальных чисел сумма чётных будет равна 50?"

Автор:	Trurl [ Понедельник, 29 Август, 2011 18:36 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
albobin писал(а): Я тут было засомневался в том, а правильно ли делать вывод 2. сразу же из 1. , но потом на досуге не нашёл опровержений. Наверное, не совсем правильно, но легко поправимо. Из 1 следует, что у нас биномиальное распределение, а для него матожидание = np, т.е n*(1+1/n)^n.

Автор:	Валерий Лаптев [ Понедельник, 29 Август, 2011 20:01 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Я рассуждал так. Пусть у нас есть N чисел. Всего комбинаций без повторений - это перестановки - равно N! Всего комбинаций с повторениями равно N^N. Итого отношение N!/N^N дает вероятность выпадения N чисел без повторений. Что не так?

Автор:	Valery Solovey [ Понедельник, 29 Август, 2011 20:47 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Формула такая же, как и приведённая Trurl-ем на 2 странице. Только описка в трактовке числа N^N.

Автор:	Валерий Лаптев [ Понедельник, 29 Август, 2011 21:14 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Valery Solovey писал(а): Формула такая же, как и приведённая Trurl-ем на 2 странице. Только описка в трактовке числа N^N. Ага, увидел...

OberonCore https://forum.oberoncore.ru/

Хэш 63% - что это за закон природы такой? https://forum.oberoncore.ru/viewtopic.php?f=27&t=3554	Страница 4 из 6

Автор:	Валерий Лаптев [ Вторник, 30 Август, 2011 08:18 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Сергею Губанову. Вот наткнулся на Tiger. http://ru.wikipedia.org/wiki/Tiger_%28% ... 8%D1%8F%29 http://ru.wikipedia.org/wiki/TTH C ним не пробовали поэкспериментировать?

Автор:	Сергей Губанов [ Вторник, 30 Август, 2011 18:49 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Валерий Лаптев писал(а): Сергею Губанову. Вот наткнулся на Tiger. http://ru.wikipedia.org/wiki/Tiger_%28% ... 8%D1%8F%29 http://ru.wikipedia.org/wiki/TTH C ним не пробовали поэкспериментировать? Не пробовал и не собираюсь. Сформулирую "достижение мысли" этой ветки форума. Эффективность (для построения хэштаблицы) идеальной хэшфункции равна 1-1/e. Около этого значения очень маленькая дисперсия. Поэтому при больших N совершенно бессмысленно брать сложную хэшфункцию с эффективностью, например, 0.632, если самая простая имеет эффективность 0.631 (всего на одну тысячную меньше). То что в книжках по программированию пишут, что мол изобретение хорошой хэшфункции (для хэштаблицы) является искусством - ложь поскольку эффективность самой простой хэшфункции при больших N практически не отличается от эффективности идеальной.

Автор:	Рэйлвэй Каген [ Вторник, 30 Август, 2011 21:15 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Валерий Лаптев писал(а): ..Tiger Нечесна . Tiger - это не хеш-функция, а способ применения оной.

Автор:	Владислав Жаринов [ Среда, 31 Август, 2011 06:21 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Сергей Губанов писал(а): ... Сформулирую "достижение мысли" этой ветки форума. Эффективность (для построения хэштаблицы) идеальной хэшфункции равна 1-1/e. Около этого значения очень маленькая дисперсия. Поэтому при больших N совершенно бессмысленно брать сложную хэшфункцию с эффективностью, например, 0.632, если самая простая имеет эффективность 0.631 (всего на одну тысячную меньше). ... Вот теперь интересно: а как объяснить эту очень маленькую дисперсию? Что здесь за закон природы такой действует?..

Автор:	Info21 [ Среда, 31 Август, 2011 06:45 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Слово "искусство" применительно к выбору хеш-функции, конечно, есть элемент надувания щек, но внимательность, несомненно, нужна, когда речь о специфических данных, где много сильно скоррелированных элементов (фамилии, например, где коррелируют буквы и много одинаковых суффиксов; или в той же символической алгебре, где могут коррелировать показатели степеней переменных, которыми кодируются мономы, которые и надо хешировать). Простодушный выбор х.ф. тогда может оказаться дико неудачным -- нерандомизирующим в силу коррелированности элементов данных. --- Я не следил за диспутом, но было бы странно, если бы такой вероятностный закон не был известен. В физике, во всяком случае, это было бы странно (не случайно физик, столкнувшись с задачей, сразу в пунктик пальцем ткнул). В сфере ИТ такой просмотр меня не особо удивил бы, -- но Кнут человек скрупулезный, может, у него где-то это все-таки упоминается?

Автор:	albobin [ Среда, 31 Август, 2011 09:37 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Trurl писал(а): albobin писал(а): Я тут было засомневался в том, а правильно ли делать вывод 2. сразу же из 1. , но потом на досуге не нашёл опровержений. Наверное, не совсем правильно, но легко поправимо. Из 1 следует, что у нас биномиальное распределение, а для него матожидание = np, т.е n*(1+1/n)^n. Хоть вроде бы уже всё обсуждено, но есть некоторая неудовлетворённость. Биномиальное распределение получится, если, наверное, всё таки "свольничать" и "нужным" образом эксперимент мысленно трансформировать. Имеем. 1. N раз генерируем число из диапазона 1..N, для каждого числа вероятность появления в одной попытке одинакова и равна 1/N, и непоявления (1-1/N) 2. Для любого из чисел 1..N вероятность события "это число ни разу за N попыток не сгенерировано" равна (1-1/N)^N 3. После N попыток имеем итог, что какое-то кол-во чисел из 1..N так и ни разу не появилось. (Хотелось бы найти мат.ожидание этого кол-ва) Начинаем "биномиализацию" Опираемся на изложенное в п.2 п.3, отвлекаемся от конкретных чисел и представляем, что будто бы в процессе исходного эксперимента неявно происходит и другой, в котором в каждой из N попыток имеем некое событие,назовём его - "нет числа", c вероятностью численно равной (1-1/N)^N (см. п.2) Получаем мат.ожидание кол-ва событий "нет числа" после N попыток N((1-1/N)^N) (бином.распред.) Следует заметить, что в этом неявном эксперименте результат значим только после окончания (N попыток), потому как эти попытки разворачиваются как бы "ортогонально" исходному процессу (N попыток, потому что N чисел) Наверное возможность сведения исходного эксперимента к случаю бином.распред. основана на том, что, рассматривая числа по отдельности (п.1), имеем случай бином.распред. кол-ва появлений конкретного числа. PS. Книжки почитать правильней, но ответ то хочется знать без приложения усилий

Автор:	Info21 [ Среда, 31 Август, 2011 11:59 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Драконограф писал(а): ... Л.Д. Ландау (кажется) спросили, что он может сказать об учёном Н. как о физике. Ландау ответил: "Физики получают результаты, а Н. доказывает теоремы." В то же время необязательна оппозиция мышлений. ... А главное, оппозиция мышлений не соответствует оппозиции наук (физики<>математики). А у Ландау от не в последнюю очередь сексуальной закомплексованности развилась манера чрезмерно выдрючиваться, отчего получались суждения экстремистского толка.

Автор:	Info21 [ Среда, 31 Август, 2011 12:00 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
albobin писал(а): Книжки почитать правильней, но ответ то хочется знать без приложения усилий По-моему наоборот: из Кнута проще, но самому поупражняться -- правильней

Автор:	Trurl [ Среда, 31 Август, 2011 12:44 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
albobin писал(а): 1. N раз генерируем число из диапазона 1..N, для каждого числа вероятность появления в одной попытке одинакова и равна 1/N, и непоявления (1-1/N) 2. Для любого из чисел 1..N вероятность события "это число ни разу за N попыток не сгенерировано" равна (1-1/N)^N Для простоты обозначим эту вероятность p. Для любых k чисел вероятность события "за N попыток ни разу не сгенерированы эти и только эти числа" равна p^k(1-p)^(N-k). Всего множеств по k чисел - C(k,N). Соотсветственно вероятность события "за N попыток ни разу не сгенерированы ровно k чисел" - C(k,N)p^k*(1-p)^(N-k). Другими словами: "процесс" состоит в том, что мы перебираем числа от 1 до N и смотрим, не попало ли число в категорию "ни разу не сгенерированных".

Страница 4 из 6	Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/

Автор:	albobin [ Среда, 31 Август, 2011 13:26 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Trurl писал(а): ... Другими словами ... "Другие слова" гораздо лучше выражают мысль. PS. Но опять что-то не то

Автор:	albobin [ Четверг, 01 Сентябрь, 2011 06:57 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
Trurl писал(а): albobin писал(а): 1. N раз генерируем число из диапазона 1..N, для каждого числа вероятность появления в одной попытке одинакова и равна 1/N, и непоявления (1-1/N) 2. Для любого из чисел 1..N вероятность события "это число ни разу за N попыток не сгенерировано" равна (1-1/N)^N Для простоты обозначим эту вероятность p. Для любых k чисел вероятность события "за N попыток ни разу не сгенерированы эти и только эти числа" равна p^k*(1-p)^(N-k) ... Опять возражаю. Нельзя применять перемножение вероятностей, события не независимы Ведь в одной попытке генерится только одно значение. Определяя вероятность негенерации конкретных чисел комбинаторным способом как отношение всех возможных вариантов развития событий за N попыток к числу всех возможных (N^N) получим то, что есть комбинации для разных чисел, которые вступают в противоречие из-за ограничение на единственность значения в конкретной попытке. Самое смешное но формула N((1-1/N)^N) для мат.ожидания интуитивно понятна, а формализьм пока не поддаётся. Хочется же быстренько, одним махом без погружения в теории

Автор:	Владислав Жаринов [ Четверг, 01 Сентябрь, 2011 07:22 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
albobin писал(а): ... Опять возражаю. Нельзя применять перемножение вероятностей, события не независимы Мы можем строить сложные события вовлекающие несколько значений только с условием непересечения их в пределах каждой попытки. ... Не понял... имеется в виду, что алгоритм генерации как бы обладает данными, какие числа из интервала уже были сгенерированы?..

Автор:	Trurl [ Четверг, 01 Сентябрь, 2011 10:20 ]
Заголовок сообщения:	Re: Хэш 63% - что это за закон природы такой?
albobin писал(а): Рассмотрим ситуацию. событие A: негенерация числа A за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа B. событие B: негенерация числа B за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа А. Отсюда и отсутствие независимости. из A может следовать 'не B' и наоборот. А давайте упростим. событие A: генерация числа A за 1 попыткe, означает негенерацию любого из остальных, в том числе и числа B. событие B: генерация числа B за 1 попыткe, означает негенерацию любого из остальных, в том числе и числа A. Однако A и B независимы, в чём легко убедиться: P(A\|B)=P(AB)/P(B), поскольку P(A\|B)=0,P(AB)=0.