Сказанное понял, но вот в чем тут проблема. Мы говорим о...11.12.06 01:15 Число просмотров: 5885 Автор: 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-х функций, так как много у них коллизий.
> Вот приятель сделал небольшой тест, достаточно любопытно.
Не только количество коллизий характеризует hash-функцию. Более того -- количество коллизий не самый такой значительный показатель, как может показаться сперва. Для дополнительной информации рекомендую обратиться к следующим материалам:
[1] Ахо, Сети, Ульман. Компиляторы: принципы, технологии, инструменты -- Хэш-таблицы
[2] Керниган, Пайк. Практика программирования -- Хэш-таблицы
[3] Кормен, Лейзерсон, Ривест [, Штайн]. Алгоритмы: построение и анализ -- Идеальное хэширование
---
Судя по тестам многие другие материалы вам известны.
Информация интересная. Правда, есть вопрос...20.08.06 21:07 Автор: HandleX <Александр М.> Статус: The Elderman Отредактировано 21.08.06 11:05 Количество правок: 1
Но для таких больших таблиц все равно будет много 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-х функций, так как много у них коллизий.
Возражение против CRC6415.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, реально всегда выполняются на таблицах. Полиномная арифметика нужна только при построении этих таблиц.
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
