информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медСетевые кракеры и правда о деле ЛевинаАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Линуксовый ботнет, распространяющийся... 
 Конец поддержки Internet Explorer 
 Рекордное число уязвимостей в 2021 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Информация интересная. Правда, есть вопрос... 20.08.06 21:07  Число просмотров: 5372
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 21.08.06 11:05  Количество правок: 1
<"чистая" ссылка>
Вот сейчас потихоньку наступают 64-битные процы. Есть ли смысл использовать 64-битные хеши (и алгоритмы), или это излишний оверхед по памяти?

Заранее всем спасибо за ответы.
<theory>
Эффективность hash-функций для строк 17.08.06 17:49  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
Вот приятель сделал небольшой тест, достаточно любопытно.

http://www.vak.ru/doku.php/proj/hash/efficiency
Не только количество коллизий характеризует hash-функцию... 18.09.06 12:07  
Автор: thror Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Вот приятель сделал небольшой тест, достаточно любопытно.

Не только количество коллизий характеризует hash-функцию. Более того -- количество коллизий не самый такой значительный показатель, как может показаться сперва. Для дополнительной информации рекомендую обратиться к следующим материалам:
[1] Ахо, Сети, Ульман. Компиляторы: принципы, технологии, инструменты -- Хэш-таблицы
[2] Керниган, Пайк. Практика программирования -- Хэш-таблицы
[3] Кормен, Лейзерсон, Ривест [, Штайн]. Алгоритмы: построение и анализ -- Идеальное хэширование

---
Судя по тестам многие другие материалы вам известны.
Информация интересная. Правда, есть вопрос... 20.08.06 21:07  
Автор: HandleX <Александр М.> Статус: The Elderman
Отредактировано 21.08.06 11:05  Количество правок: 1
<"чистая" ссылка>
Вот сейчас потихоньку наступают 64-битные процы. Есть ли смысл использовать 64-битные хеши (и алгоритмы), или это излишний оверхед по памяти?

Заранее всем спасибо за ответы.
hash в 64 бита реально нужен только когда кол-во элементов в таблице будет больше чем 2^32. 21.08.06 12:03  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
Но для таких больших таблиц все равно будет много hash-коллизий, поэтому для таких случаев "огромных данных", как правило, делают вложенные 32-битные hash-таблицы с использование двух разных hash-функций.
При чем тут количество элементов в таблице? Не понял. 10.12.06 23:36  
Автор: MadBinom Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Но для таких больших таблиц все равно будет много
> hash-коллизий, поэтому для таких случаев "огромных данных",
> как правило, делают вложенные 32-битные hash-таблицы с
> использование двух разных hash-функций.
При чем тут количество элементов в таблице? Не понял.
Спросили про наступление 64-разрядных процов - поэтому вложенные 32-битные таблицы давайте даже не упоминать. Ответ - да, надо использовать преимущества 64-х битных функций перед 32-х битными при использовании в 64-х разрядной архитектуре.
Поясняю 11.12.06 00:49  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
64-битная hash-функция, в случае её применения для построения ассоциативных hash-таблиц, может выиграть у 32-битной только когда размер "плоской" части таблицы приблизится или превзойдёт 2^32. В свою очередь, такой размер таблицы будет оправдан, только когда кол-во входов приблизится к 2^31. В реальной жизни таких наборов данных очень не много, для их обработки таким способом нужно как минимум несколько десятков мегабайт RAM.
Сказанное понял, но вот в чем тут проблема. Мы говорим о... 11.12.06 01:15  
Автор: MadBinom Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> 64-битная hash-функция, в случае её применения для
> построения ассоциативных hash-таблиц, может выиграть у
> 32-битной только когда размер "плоской" части таблицы
> приблизится или превзойдёт 2^32. В свою очередь, такой
> размер таблицы будет оправдан, только когда кол-во входов
> приблизится к 2^31. В реальной жизни таких наборов данных
> очень не много, для их обработки таким способом нужно как
> минимум несколько десятков мегабайт RAM.
Сказанное понял, но вот в чем тут проблема. Мы говорим о хеш-функциях для построения, например, строковых пулов и прочего, требующего именно скорости(ведь говорилти о хеш для строк). Такие хэш функции обладают очень плохими показателями по поводу коллизий. Поэтому рассмотрим 2 варианта, строковой пул большой(сказано грубо конечно, но да ладно, смысл разделения на 2 ситуации прояснится в подпунктах) или маленький.
1.Пул маленький
Коллизий немного как у 32-х так и у 64-х функций.
Скорость у 32-х разрядных меньше чем у 64-х разрядных.(учитывая 64х архитектуру)
Памяти примерно в 2 раза(тк коллизий мало) больше ест 64-разрядная реализация.Но ведь пул небольшой.
2.Пул большой.
Коллизий много больше у 32-х чем у 64-х функций.
Скорость у 32-х разрядных меньше чем у 64-х разрядных.(учитывая 64х архитектуру)
Памяти много больше ест 64-разрядная реализация(много больше так как строк много), но это ПОЧТИ всегда единственный выход - так как тут у нас резкое падение производительности при использовании 32-х функций, так как много у них коллизий.
Возражение против CRC64 15.01.07 12:38  
Автор: xyz Статус: Незарегистрированный пользователь
<"чистая" ссылка>
>При чем тут количество элементов в таблице? Не понял.
>Спросили про наступление 64-разрядных процов - поэтому вложенные 32-битные таблицы давайте >даже не упоминать. Ответ - да, надо использовать преимущества 64-х битных функций перед 32-х >битными при использовании в 64-х разрядной архитектуре.

1) Насколько я знаю, в системе команд обычных процов нет команды типа "сдвинуть AX пользуя BX как массив битов обратных связей". Стало быть вместо регистра с обратными связями используется код с кучей логических операций плюс магические таблицы в помощь. Поэтому пофигу что вычислять crc64,
или две crc32, возможно, параллельно.

2) В последние время даже в популярных книжках стали публиковать неприводимые многочлены зверских степеней, это не проблема. Но как выбрать из них многочлен максимальной длины?
Это возможно только полным прогоном всех остатков. Перебрать 2^64-1 остатков просто нереально,
насколько я знаю, перебором можно взять где-то 40 бит. Поэтому надежней сшить или перемножить пару полиномов 32 степени.

Вот вам и 64 разряда.
Про систему команд. 16.01.07 01:18  
Автор: leo <Леонид Юрьев> Статус: Elderman
<"чистая" ссылка>
Почти все операции, кроме некоторых, таких как циклический сдвиг и сложение по модулю 2^32, не имеют отличий при вычислении HASH-функций.

Другими словами, любой нормальный компилятор для любой 32-битной HASH-функции сгенерирует 64-битный код, при необходимости усекая результаты до 2^32-1.

Использовать 64-битную хеш-функции имеет смысл только для экономии на операциях усечения, или когда действительно нужен 64-битный результат (т.е. для огромных таблиц).

P.S.
CRC32 и CRC64 хоть и основываются на делении полиномов в поле 2, реально всегда выполняются на таблицах. Полиномная арифметика нужна только при построении этих таблиц.
1




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2022 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach