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

← →
DVM © (2011-08-24 15:13) [0]

Исходные данные:

1) В программу поступают некие идентификаторы-строки фиксированного размера (например, текстовые представления MD5 или SHA1 дайджестов)
2) Программа должна для тех идентификаторов, что уже поступали ранее ничего не делать, а для тех, что не поступали ранее что-то там делать.
3) Количество идентификаторов стремится к бесконечности, т.е любое.
4) Идентификаторы никогда из списка не удаляются.

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

Само собой, здесь идеально бы подошла бы любая готовая СУБД, где есть индексы, но хотелось бы обойтись вообще без СУБД, так как их функционал избыточен, а мне нужна всего лишь одна таблица с одним полем и индексом по ней.
Я конечно знаю о встраиваемых СУБД и прочее (собственно если не изобрету свой велосипед возьму Firebird Embedded), но хотелось бы обойтись без сторонних dll и вообще минимумом кода. И желательно, чтобы файл базы был один.

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

← →
RWolf © (2011-08-24 15:21) [1]

дерево каталогов со вложенностью, равной длине идентификатора.
к примеру, идентификатор ABCDEF сохраняется как файл c именем ABCDEF в каталоге A\B\C\D\E\F\

← →
RWolf © (2011-08-24 15:22) [2]

поправка: каталог A\B\C\D\E\.

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

один xml будет быстрее чем несколько (по итогу) файндфёрстов/файнднекстов по диску

← →
Dimka Maslov © (2011-08-24 15:23) [4]

Можно для "идентификаторов, что уже поступали ранее" создавать соотв. файлы на диске. Таким образом, чтобы выяснить что идентификатор новый, достаточно проверить существование файла с указанным именем. А чтобы не получить папку со 100500 файлами, их тоже можно распихивать по подкаталогам

← →
DVM © (2011-08-24 15:24) [5]

> RWolf © (24.08.11 15:21) [1]

Оригинальная идея. Что-то типа иерархической СУБД. Но безумное количество файлов и папок, которое будет создано меня пугает :)

← →
Jeer © (2011-08-24 15:26) [6]

> 3) Количество идентификаторов стремится к бесконечности,
> т.е любое.

Ну ты загнул :)

← →
DVM © (2011-08-24 15:26) [7]

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

А если будет 10 000 000 записей, оно не начнет тормозить?

← →
oldman © (2011-08-24 15:26) [8]

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

Какая на фиг СУБД?
Храни в таблице и seek, locate
if not found then делай свои действия

← →
Омлет © (2011-08-24 15:27) [9]

Строки складывать в кучу в один файл. Индексы хранить в отдельном файле.

← →
DVM © (2011-08-24 15:27) [10]

> Jeer © (24.08.11 15:26) [6]

Теоретически, пока SHA1 не повторится.

← →
Pavia © (2011-08-24 15:28) [11]

Используй хэш таблицы. Таблицу хранить в файле.

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

тормозить - понятие относительное.
насколько быстрая требуется реакция на очередную поступившую строку?

← →
Игорь Шевченко © (2011-08-24 15:32) [13]

искать по слову Nosql

← →
DVM © (2011-08-24 15:33) [14]

> oldman © (24.08.11 15:26) [8]

> Храни в таблице и seek, locate
> if not found then делай свои действия

В какой таблице? Формат таблицы? Как организованы индексы? Насколько быстро будет происходить поиск? Таблица в памяти меня не устраивает. Поиск перебором тоже.

> Омлет © (24.08.11 15:27) [9]

> Строки складывать в кучу в один файл. Индексы хранить в
> отдельном файле.

Ну это очевидно конечно. Проблема в организации индексов. Индексный файл теоретически тоже может быть большим и его тоже нельзя полностью грузить в память, но как быстро добавить в индексный файл еще один элемент, чтобы сохранить упорядоченность индексов без перезаписи файла я что-то не представляю. Как оно в СУБД делается?

← →
Pavia © (2011-08-24 15:37) [15]

Теория про хэши описана тут -
http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF

← →
Inovet © (2011-08-24 15:38) [16]

> [9] Омлет © (24.08.11 15:27)
> Строки складывать в кучу в один файл. Индексы хранить в
> отдельном файле.

Строки не надо

← →
Inovet © (2011-08-24 15:41) [17]

> [14] DVM © (24.08.11 15:33)
> Как оно в СУБД делается?

Бинарные деревья и страницы в файле. Где-то попадались описания структуры для Фокспро.

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

> Inovet © (24.08.11 15:38) [16]

> Строки не надо

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

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

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

← →
Inovet © (2011-08-24 15:44) [20]

http://yandex.ru/yandsearch?text=%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82+cdx&lr=62

← →
Anatoly Podgoretsky © (2011-08-24 15:46) [21]

> DVM (24.08.2011 15:13:00) [0]

Быстро находить - это нужны индексы, а тогда лучше БД

← →
DVM © (2011-08-24 15:47) [22]

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

> приходящая строка - это и так уже хэш.

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

← →
Компромисс (2011-08-24 15:48) [23]

> искать по слову Nosql

+1

← →
Jeer © (2011-08-24 15:52) [24]

Поддерживаю АП.
"Не нужно изобретать велосипед, если он уже продается в магазине" (С)

← →
Pavia © (2011-08-24 15:54) [25]

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

Ответ никак так как число записей безгранично. Следовательно перезапись будет. А да ссылку на теорию я дал. Там написано, как уменьшить число перезаписей к минимуму.

← →
asail © (2011-08-24 15:56) [26]

Ну можно любую файл-серверную БД использовать. Парадокс там какой или access... Мона Embeded FB. Ну да - есть избыточный функционал... И что?

← →
Jeer © (2011-08-24 15:58) [27]

> DVM © (24.08.11 15:47) [22]
> Да, она и есть хэш длиной 20 байт.

Ты уже прикинул размер БД ? :)

← →
Дмитрий Белькевич (2011-08-24 16:01) [28]

Я за базу. Какой-нить SQ Lite. Избыточность - избыточностью, но - самое быстрое решение, уже отполированное по скорости и надежности . Да и одну дллку с собой, думаю, не особенная проблема таскать.

← →
Anatoly Podgoretsky © (2011-08-24 16:05) [29]

> asail (24.08.2011 15:56:26) [26]

избыточный функционал можно применить для других целей, а то сегодя MD5 а
завтра черта лысого, аппетит ведь придет, не так ли?

← →
Anatoly Podgoretsky © (2011-08-24 16:07) [30]

> Jeer (24.08.2011 15:58:27) [27]

Согласно заявлению - безграничный

← →
Дмитрий Белькевич (2011-08-24 16:07) [31]

В принципе, я что-то такое почти один-в-один уже делал, как раз на sqlite, если есть интерес - стучи в мыло - кину.

← →
asail © (2011-08-24 16:25) [32]

> Anatoly Podgoretsky © (24.08.11 16:05) [29]

Дык, а я об чем? Тем более, что дополнительные издержки в случае, скажем, с Embeded FB минимальны. А профиту вагон и маленькая тележка. Сильно сомневаюсь, что можно самому быстро и качественно написать что-то сравнимое по производительности.

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

один список глобальный.
+ список вспомогательный (быстрый кэш) с управляемым временем жизни (один запуск программы, один день, и т.д. в зависимости от стиля использования проги)

очередная проверка:
1. быстро проверяем по быстрому кэшу (который маленький).
если строка уже есть, в глобальный список не лезем.
если нет, проверяем по длинному списку.

2. если нашли в длинном - вносим значение в быстрый кэш.

← →
asail © (2011-08-24 17:39) [34]

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

Если разброс входных кэшей большой, то можно нарваться вообще на не детские такие тормоза... Например, если в течении дня нет ни одного повтора или повторы вообще редки (скажем на 1000 строк один повтор). Т.е. такой подход может оказаться полезным в весьма ограниченных случаях.

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

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

← →
DVM © (2011-08-24 18:01) [36]

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

> а раз так, то задача фактически сводится к защите от коллизий
> хеша.
> поэтому вместо всей этой алхимии предлагаю например пойти
> совсем другим путем : взять не sha1 а gas48, который длиннее.
>

Дело то не в том что sha1 хэши могут совпасть, а в том, что данные от которых они вычисляются действительно одинаковые. Поэтому какой алгоритм - не важно. Вот одинаковые данные мне и не надо обрабатывать. Такие совпадения могут быть весьма частыми. Скажем так, примерно 1/2..1/3 всех данных поступающих - дубли.

← →
DVM © (2011-08-24 18:04) [37]

Пока остановился на sqllite как на временном решении, которое хорошо по всем параметрам: быстрый поиск, всего одна dll, база в одном файле. Добавил 1000 000 записей без проблем. Поиск - доли секунды.
Но сама задача заинтересовала. Почитаю по ссылкам про хэши, попробую сделать свою реализацию, может быстрее выйдет.

← →
Jeer © (2011-08-24 18:11) [38]

Да поиск и не надо делать.
Хранить hash в строке по которой сделан PK.
On exception - ничего не делать, иначе todo

← →
QAZ (2011-08-24 18:34) [39]

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

← →
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]

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

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

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

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

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

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

> 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-31 05:23) [63]

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

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

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

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

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

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

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

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

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

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

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

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

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

> Котик Б (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 что прямо перед носом)

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

> DVM (02.09.2011 00:06:20) [80]

Тогда возьми другую СУБД, их же как собак нерезаных.

Кто как извращается... http://habrahabr.ru/blogs/php/127569/

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