Re: Посоветовать хэш

От Alex Mizrahi (2:5020/400) к Alexander Gusak

From: "Alex Mizrahi" <udodenko@users.sourceforge.net>

 AM>> Подмножество того что лежит в базе данных, грубо говоря, соотносится

 AM>> с тем сколько раз эту функцию применяют, но не к чему её применяют.

 AM>> Т.о. состав базы и даже её наличие к функции отношения не имеет.

 AG> Мне не хочется сейчас укапываться в математику, я посмотрел быстренько

 AG> http://arxiv.org/pdf/cs/0702159 и решил, что наверно все же имеет

значение

 AG> (кратко - там люди проверяли алгоритм minimal perfect hash, гоняя его

 AG> на базе выборки доменных имен длиной до 64 байт, от 1 миллиона до 1

 AG> миллиарда строк, интересовала их линейность времени вставки/поиска при

 AG> разных размерах выборки и, соответственно, ключа - от 13 до 23 бит. Из

 AG> чего я делаю вывод, что существуют алгоритмы, для которых размер ключа

 AG> определяется числом элементов, а не их разрядностью. Какие -

 AG> дискутировать не готов).

Угу, а я краем уха где-то слышал, что существуют механизмы, нарушающие

второй термодинамики, так что если кто хочет делать вечный двигатель,

читайте

материалы на arxiv.org, и будет вам счастье.

Понимаешь, математика так не работает. Это не юриспруденция, где может

открыться какое-то новое видиние. В математике, если хотя бы одним методом

что-то доказано, приведён хотя бы один контрпример показывающий

невозможность

чего-то -- то всё, дело можно закрывать, по крайней мере до пересмотра

фундаментальных законов логики. И никакие чудесные алгоритмы помочь тут

не могут, если это принципиально невозможно. Дискутировать тут совершенно

неочем, т.к. заранее известно что это может быть только пустой тратой

времени.

 AM>> Hу представь что в базе хэш всего одного файла. Потом нашли какой-то

 AM>> ещё файл, загнали в базу. Потом нашли ещё один, и проверяют есть

 AM>> ли он в базе. И что, то что функция применена всего три раза может

 AM>> как-то помочь избежать коллизии?

 AG> Ээээ. Пример. Если мы знаем точно, что функцию понадобится применить не

 AG> более трех раз, то грубо говоря любые три предмета я могу

 AG> рассортировать один направо, другой - налево, третий ну скажем в

 AG> кармашек, моя прелессссть.

Задача формулировалась именно относительно хэшей.

Сто миллиардов предметов тоже можно отсортировать и обойтись без хэшей

вообще, я думаю это даже будет работать более-менее пристойно, но Паразит

категорически отказывается от таких решений.

 AM>> Если хэш-функция не является биективной функцией ДЛЯ ИСХОДHОГО

 AM>> МHОЖЕСТВА (того где 2^81920), то существует большая нуля вероятность

 AM>> коллизии.

 AG> Как она вообще может являться биективной, если биективность

 AG> предполагает _взаимно_ однозначное отображение, и следовательно

 AG> _равномощность_ множеств? perfect hash функция отображает на

 AG> натуральный ряд, как конечное множество может быть с ним равномощным?

 AG> Здесь речь может только об инъекции идти.

В случае с minimal perfect hash как раз биективное отображение.

В общем случае, конечно, да, тут нужна только инъективность.

Hо мне вообще нравится, здесь ты даже небольшую ошибочку нашёл, а

тот факт что сама идея бред -- предпочитаешь не замечать. Сдаётся

мне троллите вы честных людей, причём начиная с Паразита, который

предложил сделать Универсальный Архиватор в замысловатой формулировке,

а теперь, небось, сидит где-то хохочет.

--- ifmail v.2.15dev5.4

 * Origin: Demos online service (2:5020/400)

Ответы на это письмо:

From: Username
Заголовок следующего сообщения в треде может быть длинным и его придется перенести на новую строку

From: Username
Или коротким