OberonCore https://forum.oberoncore.ru/ |
|
Хэш 63% - что это за закон природы такой? https://forum.oberoncore.ru/viewtopic.php?f=27&t=3554 |
Страница 4 из 6 |
Автор: | Александр Ильин [ Понедельник, 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. Ага, увидел... ![]() |
Автор: | Валерий Лаптев [ Вторник, 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% - что это за закон природы такой? |
Слово "искусство" применительно к выбору хеш-функции, конечно, есть элемент надувания щек, но внимательность, несомненно, нужна, когда речь о специфических данных, где много сильно скоррелированных элементов (фамилии, например, где коррелируют буквы и много одинаковых суффиксов; или в той же символической алгебре, где могут коррелировать показатели степеней переменных, которыми кодируются мономы, которые и надо хешировать). Простодушный выбор х.ф. тогда может оказаться дико неудачным -- нерандомизирующим в силу коррелированности элементов данных. --- Я не следил за диспутом, но было бы странно, если бы такой вероятностный закон не был известен. В физике, во всяком случае, это было бы странно (не случайно физик, столкнувшись с задачей, сразу в пунктик пальцем ткнул). В сфере ИТ такой просмотр меня не особо удивил бы, -- но Кнут человек скрупулезный, может, у него где-то это все-таки упоминается? |
Автор: | Владислав Жаринов [ Среда, 31 Август, 2011 08:24 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Info21 писал(а): ... Ага... человек поставил эксперимент (вычислительный в данном случае), получил результат и задумался, как его объяснить. Я не следил за диспутом, но было бы странно, если бы такой вероятностный закон не был известен. В физике, во всяком случае, это было бы странно (не случайно физик, столкнувшись с задачей, сразу в пунктик пальцем ткнул). ... ![]() ![]() ![]() |
Автор: | 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 и смотрим, не попало ли число в категорию "ни разу не сгенерированных". |
Автор: | 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 писал(а): ... Не понял... имеется в виду, что алгоритм генерации как бы обладает данными, какие числа из интервала уже были сгенерированы?..
Опять возражаю. Нельзя применять перемножение вероятностей, события не независимы ![]() Мы можем строить сложные события вовлекающие несколько значений только с условием непересечения их в пределах каждой попытки. ... |
Автор: | albobin [ Четверг, 01 Сентябрь, 2011 07:26 ] |
Заголовок сообщения: | Re: Хэш 63% - что это за закон природы такой? |
Драконограф писал(а): albobin писал(а): ... Не понял... имеется в виду, что алгоритм генерации как бы обладает данными, какие числа из интервала уже были сгенерированы?..Опять возражаю. Нельзя применять перемножение вероятностей, события не независимы ![]() Мы можем строить сложные события вовлекающие несколько значений только с условием непересечения их в пределах каждой попытки. ... Язык моя - враг ... Мысль уточнил уже. PS. Боюсь, уточнил всё таки не точно. Рассмотрим ситуацию. событие A: негенерация числа A за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа B. событие B: негенерация числа B за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа А. Отсюда и отсутствие независимости. из A может следовать 'не B' и наоборот. |
Автор: | 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. |
Страница 4 из 6 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |