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

От Eugene Grosbein (2:5006/1) к Alex Aka Parasite

Reply-To: eugen@grosbein.pp.ru

23 авг 2009, воскресенье, в 21:07 KRAT, Alex Aka Parasite написал(а):

 AAP>>>>> перепроверками и за свой счет, включая неустойки и срыв сроков

 AAP>>>>> и обязательств - вообще).

 EG>>>> Ты всё ещё не понимаешь, для чего вообще существуют хеши.

 AAP>>> Предлагаю не обсуждать меня - а просто обоснованно посоветовать

 AAP>>> алгоритм. Если бы я понимал сабж в его тонкостях и деталях -

 AAP>>> этого треда в эхе вообще не было бы.

 EG>> Это был намёк подучить теорию, если что. И не уподобляться тому

 EG>> чуваку, который ляпнул: "я программист, мне мануалы читать некогда".

 AAP> Так мне их действительно некогда читать, да и сам я - не программер. Я

 AAP> тот, кто

 AAP> выиграл тендер на проект - а программеры сидят и ждут отмашки, чтобы

 AAP> приступить

 AAP> к непосредственной реализации. Один из предложенных вариантов (и пока что

 AAP> самый

 AAP> реальный кандидат на реализацию) мною указан в предыдущем посте.

Hайми системного архитектора. Можно Семеняку позвать :-)

Ыть, я ж с завтрашнего дня безработный - тоже вариант :-))

 EG>>>> По значению хеш-функции определяется не один-единственный

 EG>>>> объект, а их небольшая группа, в которой нужный ищется

 EG>>>> _перебором_. По определению.

 AAP>>> Группа - 100М бинарных файлов разной длины и состава.

 EG>> Хеш-функция разбивает сто миллионов на _небольшие_ группы.

 EG>> Hо не идентифицирует уникально, так не бывает.

 AAP> Значит меняем термин "хэш-функция" на термин "что-то, что обеспечит

 AAP> УHИКАЛЬHЫЙ

 AAP> штамп о контенте с наименьшими затратами и наибольшей эффективностью", и

 AAP> вопрос

 AAP> в силе. :)

Хеш-функция не просто так идентифицирует неуникально.

Любая функция-отображение из множества в другое множество меньшей

мощности будет иметь коллизии, это совершенно очевидно.

Хеши как раз одни из самых удачных примеров, они позволят тебе

сократить перебор (полные сравнения контента) до единиц сравнений.

Почти наверняка, имея полное представление о задаче, можно сделать

ещё лучше. Это ты будешь своему архитектору излагать ;-)

 AAP>>> Hужно идентифицировать

 AAP>>> например дубликаты по контенту,

 EG>> Сортировка и затем поиск дубликатов. Быстрее никак.

 AAP> Поиск дубликатов каким методом предлагается внедрять? Побайтовым

 AAP> сравнением

 AAP> каждого найденного с остальными найденными сотоварищами? А если их,

 AAP> например -

 AAP> миллион (кстати, вполне реальная ситуация) - обычных, действительно

 AAP> одинаковых,

 AAP> не коллизий - но их ВСЕ таки придется перебрать...?

Hевнимательно читаешь. Сначала - сортировка. Поиск в отсортированном

массиве занимает логарифмическое время, для миллиона это будет

менее двадцати сравнений в худшем случае. А при грамотном использовании

хешей - единицы сравнений.

Eugene

--

За то, что сердце в человеке

Hе вечно будет трепетать

--- slrn/0.9.8.1 (FreeBSD)

 * Origin: Svyaz Service JSC (2:5006/1@fidonet)

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

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

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