Посоветуйте как лучше сделать

← →
Inovet © (2011-08-24 18:42) [40]

> [37] DVM © (24.08.11 18:04)
> про хэши, попробую сделать свою реализацию

Почему не индекс?

← →
Медвежонок Пятачок © (2011-08-24 19:19) [41]

а пользовательские данные которые приходят могут быть сегментированы по каким-нибудь признакам?
например по некой дате.
приходят данные, берем дату.
лезем в ту часть справочника, которая хранит хеш для этой даты, проверяем.
то есть не весь список шерстим а только часть.

← →
DVM © (2011-08-24 22:18) [42]

> Медвежонок Пятачок © (24.08.11 19:19) [41]

> а пользовательские данные которые приходят могут быть сегментированы
> по каким-нибудь признакам?
> например по некой дате.

Могут по дате, собственно дата одно из значений, которое участвует в формировании хэша. Но очень часто встречаются сообщения с датой совпадающей вплоть до миллисекунд, это и есть дубли.
У меня уже была мысль разбить по дням справочники, но пока отказался, много файлов неудобно.

> QAZ (24.08.11 18:34) [39]

> а зачем хранить текстовые представления MD5 когда числовые
> гораздо меньше,реще сортируюца и находятся ?

В поле какого типа класть 20 байтовый хэш? Разбивать? Блоб совсем медленно будет.

> Inovet © (24.08.11 18:42) [40]

> Почему не индекс?

индексы будут разумеется

← →
QAZ (2011-08-24 22:28) [43]

> В поле какого типа класть 20 байтовый хэш? Разбивать? Блоб
> совсем медленно будет.

приводить его к crc32 например

← →
DVM © (2011-08-24 22:38) [44]

> QAZ (24.08.11 22:28) [43]

> приводить его к crc32 например

Не очень надежно. Высока вероятность коллизий.

← →
QAZ (2011-08-24 22:54) [45]

> Не очень надежно. Высока вероятность коллизий

правда чтоли? для 20 байт?
а использование оного в файловых системах,архиваторах,при передачи данных и т.д. как объясниш? или типа там колизии менее страшны чем в твоей мегазадаче?

← →
RWolf © (2011-08-24 23:23) [46]

> правда чтоли? для 20 байт?

crc32 — это четыре байта. всего 4 млрд вариантов.

> а использование оного в файловых
> системах,архиваторах,при передачи данных и т.д. как объясниш?
> или типа там колизии менее страшны чем в твоей мегазадаче?
>

crc применяется для контроля ошибок передачи, а не для хэширования или поиска коллизий.

← →
DVM © (2011-08-24 23:36) [47]

> всего 4 млрд вариантов.

Даже значительно меньше на практике. Я проверял. В среднем 3 коллизии на 100000 значений получалось.

← →
Jeer © (2011-08-25 09:40) [48]

Если есть n-разрядное двоичное число и число используемых комбинаций максимально и есть хеш-функция разрядностью m, то вероятность коллизии
p <= 2^(2*n-m)

← →
Дмитрий С © (2011-08-25 10:15) [49]

TStringList переделать для того чтобы строки на диске сразу хранил
+ Sorted.

Все равно элегантного решения не будет.

← →
QAZ (2011-08-25 10:30) [50]

> crc32 — это четыре байта. всего 4 млрд вариантов.

а ничего не мешает делать двойной кряк и объединять в int64 например
опятьже кряк можно использовать как индекс для быстрого поиска,а там уш выискивать свои "колизии" побайтно если оч надо

> Даже значительно меньше на практике. Я проверял. В среднем
> 3 коллизии на 100000 значений получалось.

проверял как и на чем?

← →
sniknik © (2011-08-25 10:38) [51]

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

← →
RWolf © (2011-08-25 10:59) [52]

> QAZ (25.08.11 10:30) [50]
> не мешает делать двойной кряк и объединять в int64 например

куда проще взять любые 8 байт из исходного MD5.

← →
DVM © (2011-08-25 15:23) [53]

> Дмитрий С © (25.08.11 10:15) [49]
> TStringList переделать для того чтобы строки на диске сразу
> хранил
> + Sorted.
>
> Все равно элегантного решения не будет.

Проблема не в хранении строк это элементарно, легко переделывается и TStringList (переделанные кстати есть), проблема в хранении индексов. Индексы тоже где то надо хранить, причем в упорядоченном виде. И НЕ В ПАМЯТИ!!!

> QAZ (25.08.11 10:30) [50]

> проверял как и на чем?

Руками как же еще. Генерировал данные, получал CRC различные, клал CRC в базу, предварительно смотрел нет ли там таких же. Коллизий навалом. Причем со временем они все более и более возможны.
Тебе правильно сказали выше о назначении CRC. Он предназначен для обнаружения ошибки здесь и сейчас.

← →
Jeer © (2011-08-25 16:15) [54]

> о назначении CRC. Он предназначен для обнаружения ошибки
> здесь и сейчас.

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

Существенная разница между hash- и crc-методами идентификации (контроля уникальности данных) состоит в криптоустойчивости первых и высокой скорости вычисления вторых.
Так, что Вам - в CRC :)

Размерность CRC ( длина неприводимого полинома ) ограничена только Вашими фантазиями. Эффективные реализации есть для разных разрядностей.

С точки зрения коллизий - один фиг при одинаковой длине.
Т.е. выбрав CRC160 Вы не получите коллизий больше, чем при той или иной hash-160.

← →
RWolf © (2011-08-25 16:17) [55]

> Jeer © (25.08.11 16:15) [54]

да тут никакие вычисления не нужны вовсе.
входные данные и так суть хэш, достаточно отбросить лишние биты.

← →
Jeer © (2011-08-25 16:24) [56]

Ну, суть использования CRC состоит в уменьшенной длине сигнатуры от большой длины данных. Соотношение длин определяет вероятность коллизии.
Что там у DVM во входных данных - не мне судить.

← →
Иксик © (2011-08-26 20:12) [57]

Так ему предлагают не crc160 вместо hash160, а crc32 вместо hash160, что как бэ...

← →
Запад (2011-08-26 20:18) [58]

А вообще с какой скоростью данные приходят?

← →
Иксик © (2011-08-26 20:19) [59]

Тьфу, последний пост от меня, это после закрытой ветки TUser-a :)

← →
DVM © (2011-08-28 00:55) [60]

Если кому интересно, в книге:

Бакнелл Джулиан - Фундаментальные алгоритмы и структуры данных в Delphi

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

Практически один в один то, что мне требуется, там же есть и реализация на Delphi.

← →
картман © (2011-08-28 13:02) [61]

> RWolf © (24.08.11 15:21) [1]
>
> дерево каталогов со вложенностью, равной длине идентификатора.
>
> к примеру, идентификатор ABCDEF сохраняется как файл c именем
> ABCDEF в каталоге A\B\C\D\E\F\
> <Цитата>
>
> RWolf © (24.08.11 15:22) [2]
>
> поправка: каталог A\B\C\D\E\.

ну да, только почему бы не в файле?... Не знаю, как объяснить, в общем так:

256 отсортированных значений(или сколько там будет в приходящих?) записей для первого байта + ссылка(не всегда заполненная) на следующий байт со-сылкой?

Никаких перестроек индекса, максимальное время поиска - 1 переход головки * длину слова.

← →
картман © (2011-08-28 13:18) [62]

> картман © (28.08.11 13:02) [61]

кажись, это называется ассоциативное дерево

← →
Котик Б (2011-08-31 05:23) [63]

Возможно я пропустил, четыре страницы заново перечитывать лень, но:

> DVM © (24.08.11 15:13)
> 1) В программу поступают некие идентификаторы-строки фиксированного размера (например, текстовые представления MD5 или SHA1 дайджестов)
> 3) Количество идентификаторов стремится к бесконечности, т.е любое.

эти два пункта изначально противоречивы.

> Соответственно надо где-то хранить список таких идентификаторов
> и иметь возможность быстро находить в нем нужное значение.
> Хранить список ввиду его большого размера можно только
> на диске.

Соответственно нигде список идентификаторов хранить не нужно, а заранее сформировать битовый массив [0/1] для всех вариантов. А далее просто ставить бит в 1 для встреченного варианта используя строку как индекс.

← →
palva © (2011-08-31 07:51) [64]

> заранее сформировать битовый массив [0/1] для всех вариантов

да еще озаботиться тем, чтобы файл с этими битами нефрагментированно на диске лежал. Не пересоздавать его зря.

← →
Игорь Шевченко © (2011-08-31 10:32) [65]

> да еще озаботиться тем, чтобы файл с этими битами нефрагментированно
> на диске лежал. Не пересоздавать его зря.

А какая разница, фрагментировано или нет ?

← →
palva © (2011-08-31 11:23) [66]

> А какая разница, фрагментировано или нет ?

Подумал. Да, пожалуй, никакой. Сказалось мышление времен ЕС.

← →
Игорь Шевченко © (2011-08-31 11:35) [67]

> Сказалось мышление времен ЕС.

да и там все тоже самое. IMASPZAP не переписывал файл при замене битов

← →
Kerk © (2011-08-31 11:40) [68]

> Котик Б (31.08.11 05:23) [63]
> соответственно нигде список идентификаторов хранить не нужно,
> а заранее сформировать битовый массив [0/1] для всех вариантов.
> А далее просто ставить бит в 1 для встреченного варианта
> используя строку как индекс.

Для MD5 такой битовый массив займет 9.94832639 × 10^23 байт. Классная идея :)

> Классная идея :)

Тут, в соседней ветке, анекдоты про математиков и инженеров :)

> Котик Б (31.08.11 05:23) [63]

> эти два пункта изначально противоречивы.
>

Учитывая что количество вариантов хэша SHA-1 огромно, то будем считать, что вариантов у нас очень много, "бесконечно" много. Нет тут противоречий.

> а заранее сформировать битовый массив [0/1] для всех вариантов.
>

Я боюсь представлять размер такого массива для SHA1.

> [70] DVM © (31.08.11 18:30)
> то будем считать, что вариантов у нас очень много, "бесконечно" много.

Интересно, больше доступной памяти или даже адресного пространства можно считать бесконечностью? Видимо да, как при переполнении в CPU и FPU специальные состояния предусмотрены.

> DVM (31.08.2011 18:30:10) [70]

Просто надо больше денег заработать и купить Itanium со стойкой памяти.
(один блок 2 террабайта).

> [72] Anatoly Podgoretsky © (01.09.11 14:01)
> Просто надо больше денег заработать и купить Itanium со стойкой памяти.
> (один блок 2 террабайта).

Вот правильное решение, и не надо мозг напрягать, пусть компьютер думает - он железный.

> Inovet (01.09.2011 14:43:13) [73]

Ты представляешь сколько стоят 2 террабайта, особенно для стойки. Стойку
надо забивать сверху до низу.

> Бакнелл Джулиан - Фундаментальные алгоритмы и структуры
> данных в Delphi

Лет 5 уже активно рекламирую книжку. Фундамент любого программиста - в том числе и на делфи.

> [74] Anatoly Podgoretsky © (01.09.11 15:07)
> Ты представляешь сколько стоят 2 террабайта

Выбор один - Чё тут думать, трясти надо.

А наверно не так уж запредельно стоит. Пусть 1 ГБ стоечный 1000 рублей, значит 2 млн, пусть 5 даже. Цена джипа директора.

> Inovet (01.09.2011 17:00:16) [76]

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

← →
Котик Б (2011-09-01 22:06) [78]

> Kerk © (31.08.11 11:40) [68]
> Для MD5 такой битовый массив займет 9.94832639 × 10^23 байт.

Какой ты умный.

> palva © (31.08.11 07:51) [64]
> да еще озаботиться тем, чтобы файл с этими битами нефрагментированно на диске лежал.

Я о файле ничего не писал.
При неоходимости можно даже простенький дисковый драйвер написать и выделить отдельный раздел.

> DVM © (31.08.11 18:30) [70]
> Я боюсь представлять размер такого массива для SHA1.

Попросите гражданина двумя постами выше, он посчитает.

> DVM © (31.08.11 18:30) [70]
> Учитывая что количество вариантов хэша SHA-1 огромно, то будем считать, что вариантов у нас очень много, "бесконечно" много. Нет тут противоречий.

Вы бы потрудились сначала верно сформулировать задачу со всеми дополнительными условиями.

В условии отсутствуют два очень важных параметра: ресурсы и скорость.

1. Какими аппартными/програмными ресурсами располагаем для решения задачи ?
Вдруг окажеться что эту задачу нужно решать в реалтайме на обычной офисной машинке.

Или же у вас в наличии вот такое http://habrahabr.ru/blogs/hi/127189/

2. Какое количество запросов в секунду должно быть обработано ?
Это пара запросов в сутки или же несколько тысяч в секунду.

Могут по дате, собственно дата одно из значений, которое участвует в формировании хэша. Но очень часто встречаются сообщения с датой совпадающей вплоть до миллисекунд, это и есть дубли.

Судя про этой фразе скорость возможна вплоть до 1000 запросов в секунду.
Даже если скорость будет всего 100 зап/сек. Давайте прикинем обьем операций.

100 за секунду
6000 за минуту
360 тыс. за час
8.64 млн. записей за сутки

Сколько за год пускай посчитает вышеупомянутый умный гражданин.

А теперь на этом объеме прогоните ваш любимый SQLite.

При предложенных в этой теме способах реализации накладные расходы на содержание структуры/индексов очень быстро перерастут в размерах само содержание таблицы хешей.

> Никто не может ничего посоветовать из готового?

Ну возьми тот же TClientDataSet что прямо перед носом)

"Бесконечность" он, разумеется, не поддерживает, но зато полностью избавит тебя от геморроя с изобретением индексного велосипеда)

> Котик Б (01.09.11 22:06) [78]

> Судя про этой фразе скорость возможна вплоть до 1000 запросов
> в секунду.

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

> В условии отсутствуют два очень важных параметра: ресурсы
> и скорость.
>
> 1. Какими аппартными/програмными ресурсами располагаем для
> решения задачи ?
> Вдруг окажеться что эту задачу нужно решать в реалтайме
> на обычной офисной машинке.

Офисная машина вполне потянет. Как я уже писал данных не много в единицу времени, но собираться они будут долго. Не особенно критично, если поиск по базе уже принятых данных будет производиться скажем за секунду.

Вобщем, проблема не в производительности, как я, думаю, понятно. Мой вопрос состоял лишь в организации расширяемой хэш таблицы лежащей на диске, собственно я ответ на этот вопрос уже нашел в книге, среди миллиарда записей класс такой таблицы находит искомую очень быстро.

> Сергей М. © (01.09.11 23:00) [79]

> Ну возьми тот же TClientDataSet что прямо перед носом)

Он свои данные проецирует полностью в память, что при большом объеме их становится проблемой.

Посоветуйте как лучше сделать Найти похожие ветки