Страницы: 1 2 3 вся ветка
Форум: "Прочее";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2011.12.18;
Скачать: [xml.tar.bz2];




Вниз

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


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 &#215; 10^23 байт. Классная идея :)



Jeer ©   (2011-08-31 12:58) [69]


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


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



DVM ©   (2011-08-31 18:30) [70]


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


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

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


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

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



Inovet ©   (2011-08-31 18:48) [71]

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

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



Anatoly Podgoretsky ©   (2011-09-01 14:01) [72]

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

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



Inovet ©   (2011-09-01 14:43) [73]

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

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



Anatoly Podgoretsky ©   (2011-09-01 15:07) [74]

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

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



tesseract ©   (2011-09-01 16:19) [75]


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


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



Inovet ©   (2011-09-01 17:00) [76]

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

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

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



Anatoly Podgoretsky ©   (2011-09-01 20:15) [77]

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

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



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


> Kerk ©   (31.08.11 11:40) [68]
> Для MD5 такой битовый массив займет 9.94832639 &#215; 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.

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



Сергей М. ©   (2011-09-01 23:00) [79]


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


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

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



DVM ©   (2011-09-02 00:06) [80]


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


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

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


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

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

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


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


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

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




Страницы: 1 2 3 вся ветка
Форум: "Прочее";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2011.12.18;
Скачать: [xml.tar.bz2];




Наверх





Память: 0.84 MB
Время: 0.036 c
2-1315288804      TrashReg              2011-09-06 10:00  2011.12.18  
Ключи реестра Windows


2-1315865245      Gu                    2011-09-13 02:07  2011.12.18  
Отловить закрытие приложения


2-1315421110      Эцилоп                2011-09-07 22:45  2011.12.18  
Эмуляция работы мышки


15-1314907012     Knight                2011-09-01 23:56  2011.12.18  
Инсталляция программ Windows XP


15-1314390597     Юрий                  2011-08-27 00:29  2011.12.18  
С днем рождения ! 27 августа 2011 суббота