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

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

From: "Alexander Gusak" <agusak@skengstroy.ru>

Wed Sep 02 2009 14:16, Alex Mizrahi wrote to Alexander Gusak:

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

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

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

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

 AM> читайте

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

Ссылку-то видел? Полноценно оформленная научная статья. Я же не на

forum.msk.ru посылаю.

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

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

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

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

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

Чего доказано-то? В реале доказано, что PFH существуют для любого множества,

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

причем теоретически обосновано и соотношение между числом элементов множества

и количеством бит в функции. Есть научная литература по этому вопросу, есть

стандартные библиотеки генерации таких функций - http://cmph.sourceforge.net/

например:

The CMPH Library encapsulates the newest and more efficient algorithms in an

easy-to-use, production-quality, fast API. The library was designed to work

with big entries that cannot fit in the main memory. It has been used

successfully for constructing minimal perfect hash functions for sets with

more than 100 million of keys, and we intend to expand this number to the

order of billion of keys.

То есть существует что-то похожее на то, что хотел автор, и куда его можно

направить копать. Чего еще надо-то?

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

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

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

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

Hасколько я понял, он довольно быстро отказался от использования "хэша по

определению", и согласен на хоть какое-нибудь отображение.

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

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

MPFH это уже следующий шаг :) В данном случае необязательный.

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

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

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

Да мне вообще по барабану, не моя компетенция, разве что мозги размять.

Hепонятно только что эта тема в этой эхе делает.

С уважением

Александр Гусак

--- ifmail v.2.15dev5

 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)

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

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

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