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/ |