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

← →
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. Избыточность - избыточностью, но - самое быстрое решение, уже отполированное по скорости и надежности . Да и одну дллку с собой, думаю, не особенная проблема таскать.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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