Самый быстрый алгоритм поиска по БД

[edranovdenis]

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

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

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

меня интересует вопрос: делаю ли я что-то стоящее или изобретаю велосипед? если кто знает что такие алгоритмы уже существуют, то подскажите где о них можно узнать.

спасибо.

[Liksys]

Когда я делал поиск слов по файлу, то делал индексацию по первому символу. В начале файла прописывается специальный заголовок, где перечисляются все возможные символы, с которых начинаются словав файле (например алфавит), и смещение в файле, после которого сразу начинается ряд слов, начинающихся с этой буквы. При поиске сначала ищется первая буква в заголовке, прога делает lseek в то место, где начинается кусок файла с первыми символами в строке, как буква искомого. Потом прога тупо перебирает варианты, как только находит - возвращает результат и переходит к другому файлу, если же ничего не нашлось и первый символ перестал совпадать, то слова на эту букву уже кончались и остаток файла можно пропустить.
Работает довольно быстро даже на 600 селероне, единственное условие - чтобы файл был рассортирован по алфавиту.

[Clear_Mind]

делаю ли я что-то стоящее или изобретаю велосипед?

читай Кнут Д. Исскуство программирования т.3
ищи в www.google.com

[miron]

Дональд Кнут "Искуство программирования" Том 3.

[oav]

делаю ли я что-то стоящее или изобретаю велосипед?

читай Кнут Д. Исскуство программирования т.3
ищи в www.google.com

Completely agree. +1

[elide]

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

это называется ассоциативной памятью.

согласно рассчетам поиск значения будет занимать 100-300 циклов по ячейкам

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

[edranovdenis]

Кнут есть в библиотеке Мошкова, качаю (я его уже читал когда-то, может что не понял тогда, ладно если так настаиваете еще разик прочитаю. но насколько помню там такого нет) (кстати: http://algolist.manual.ru/ вот еще вроде неплохой ресурс)

to liksys: получается сначала файл надо отсортировать(или сортировать в процессе создания) потом индексировать, эти два процесса сами по себе уже достаточно тяжелые... а почему бы не файл сортировать, а индексы расположить в отсортированном порядке?

to elide: ассоциативная память где нибудь исспользуется? (надо поискать инфу, спасибо). (предполагаю, что стоит она в разы дороже обычной и не на любой платформе есть вообще, на IBM РС наверняка нету...)
просмотров ячеек, даже если их миллиарды...

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

[Liksys]

Неа, не получица. Объясняю принцип работы:

Код: Выделить всё

[index]
A 123
B 456
C 789
D 1234
[/index]
...
a...
a...
and  bla-bla-bla
a...
...
band  bla-bla-bla2
b...
...
c...
counter  bla-bla-bla3
c...
c...
...
d...
disk  bla-bla-bla4
d...
...

при поиске слова, например counter, программа ищет индекс на "c"6 перемещается в файл, где в первый раз в качестве первого символа встречается эта буква. Начинает перебирать слова, начинающиеся с этой буквы. Находит counter, возвращает его перевод. Не находит - идет пока первым символом не станет символ, отличный от "c". Слова должны бить не то что рассортированы, а хотя бы сгруппированы по первому символу.

[edranovdenis]

ну, принцип это не закон...

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

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

но я уже делаю по другому... :)

[elide]

ассоциативная память где нибудь исспользуется?

да. в основном в специализированных вычислителях, типа ассоциативных SIMD процессоров, где на АП строятся либо устройства управления, либо сами исполнительные устройства.

(предполагаю, что стоит она в разы дороже обычной и не на любой платформе есть вообще, на IBM РС наверняка нету...)

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

[edranovdenis]

to elide: АП наверное еще не больше мегабайта бывает и тогда там остро встает вопрос смены содержимого... с учетем нынешнего снижения цен на флэш, наверное пора реализовывать это именно на них, получиться неплохое хранилище ключей БД, ну сами данные хранить на винчестере разумеется. А почему не нужна? мне пригодилась бы :-)

to liksys: ksokrat не ты написал? если ты делаешь переводчик, то насчет него у меня есть еще пара идеек.

to all: Кнута внимательно читаю :-)

[edranovdenis]

offtop: to liksys:
Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву.
Хеширование - Википедия. :-)

[sarutobi]

2 Liksys & edranovdenis
Вообще-то сортируют обычно индексы, а не сырые данные. Единственное исключение из этого правила (которое мне известно) - кластерный индекс. В общем случае построение индекса выполняется так (для одного элемента данных):
1. В конец основного файла с данными дописывается новое значение
2. Методом поиска по индексу находится позиция, в которой должно находится вставленное значение
3. В индексный дескриптор в найденную позицию записывается указатель на добавленное значение (перестроение индекса).
После этого поиск можно вести по индексу, не трогая основные данные до момента выборки.
Так что предложенный поиск по файлу с индексом можно улучшить
Вообще же критичной в задаче поиска будет именно сортировка, поиск по отсортированным значениям выполняется на несколько порядков быстрее. Второй критичный момент для поиска - размещение данных индекса. Поиск по дереву требует в разы меньшего числа операций нежели поиск по списку, поиск в сбалансированном дереве быстрее поиска в обычном и т.п...
На эту тему написана уже не одна научная работа, но оптимального универсального способа решения проблемы еще нет....

[edranovdenis]

Хм... вроде как просмотрел Кнута...

Не нашел ничего больше чем бинарное дерево. (Вы мне на него намекали?)
Представьте себе игру "угадай число от 1 до 100", самым эфективным алгоритмом отгадывания будет называние числа посередине (50 - больше, 75 - меньше, 62 и т.д.). Бин. дерево это тоже самое, только в нем могут присутствовать не все числа от 1 до 100, соответственно середина будет смещена от 50, если же мы нашли ровно середину, то такое дерево называется симметричным. Соответственно, чтобы бинарное дерево было эффективным мы должны контролировать его симметричность, кроме того, центр (корень) может плавать по дереву, что усложняет механизм оптимизации частых запросов.
Получается количество иттераций равно pi*log n+1. если n=1000 000 000, то 29. (кстати, log это количество 0, можно сказать...)

Хм... все же мой алгоритм не зависит от n. Пошел оптимизировать алгоритм... :-) (благо возможностей для этого море...)

[edranovdenis]

to sarutobi: не понял, каким образом сортировка может влиять на эффективность алгоритма с 28 индексами? если вот например менять местами запрошенное значение с предидущим в индексе (оно как бы всплывает), то получиться автооптимизация наиболее частых запросов. вот это может ускорить в разы, а сортированность... не понимаю.

[Liksys]

to liksys: ksokrat не ты написал? если ты делаешь переводчик, то насчет него у меня есть еще пара идеек.

Нет, не я. Но ты почти прав: я пишу словарь. Интересно услышать твои идеи, поделись Если хочешь - пиши в личку.

[sarutobi]

edranovdenis
Поясняю.
Данные и индекс пишутся в разные файлы. Данные идут в том порядке в котром их занесли, индекс сортируется. Теперь поиск осуществляется по индексу, который
а) отсортирован
б) содержит меньше данных, нежели основной блок
Применим пример Liksys только для индекса а не для всего файла - в результате находим в индексе номер позиции в файле основных данных откуда требуется сделать выборку.
Теперь возьмем случай с двумя индексами. Поиском по первому находим выборку из второго индекса, поиском по второму - получаем выборку из основного набора данных.
Далее по индукции (для трех и более индексов).
Если же не сортировать индекс - то выигрыш в производительности будет только за счет поиска среди меньшего объема данных.
Тепрь давай те рассмотрим ваш вариант с бинарным деревом. Пусть у нас не все числа от одного до 100 а какая то выборка из n (n<=100) чисел. перенумеруем их как (1..n), т.е. построим индекс.
Дальше объяснять?
))))

[Liksys]

Всем, кто обсуждает эту тему: вот интересная статья на тему сортровки и поиска: http://www.citforum.ru/programming/theory/...ting2.shtml#5_2

[edranovdenis]

to sarutobi:
1. я не против чтобы разместить 28 индексов в отдельном файле.
2. про случай с двумя индексами, честно говоря, пока не догоняю. можно на пальцах объяснить, а то как я говорил у меня нет компьютерного образования.
3. Про вариант с бинарным деревом. Бинарное дерево имеет смысл исспользовать только в случае произвольной выборки(напр. символьные ключи, как слова, произвольные числа или хэши), если в процессе решения задачи мы можем их пронумеровать по порядку, то здесь используется просто таблица с указателями(если нужно 50 значение, то мы не ищем, а смотрим сразу указатель который лежит в 50-й ячейке).

to liksys:
:-) зачем в личку? опен сорц всетаки...
1. неплохим вариантом будет создание всетаки того же бинарного дерева.
2. представь: есть 28 индексов, делаем еще 28, но уже индексируем по последней букве слова, когда ищем слово, то берем 2 индекса по первой и последней букве и находим все совпадающие указатели, т.о. количество для переборки сокращается. а теперь делаем финт ушами и... приходим к выводу что нам влом каждый раз сравнивать 2 таблицы индексов и делаем 28*28=784 таблицы где все уже сравнено и мы делаем только выборку.

offtop:
грустные мысли. приверженцы опен сорца частенько оправдывают опен тем что он вышел из научной среды и является её продолжением. к сожалению продолжения научных традиций практически не вижу, а все более желание получить халяву или иногда повторение уже сделанного. процесс творческого создания новых идей практически отсутствует, хуже нет даже желания.
очень надеюсь, что я просто плохо смотрел (такое бывает частенько... :-)

еще offtop:
ждал я както товарища у него на работе, и пока ждал машинально подбирал пароль к его 1с, минут через 10 она открылась... символов было 7-8, подобраный мною пароль отличался от его. случайность конечно, но есть повод еще раз задуматься над хешированием... :-)

[edranovdenis]

мда... меньше 100 итераций (+/- 50) никак не получается

но!

1. мой алгоритм относительно легко расспаралеливается. можно-ли расспаралелить бинарное дерево?
2. вес итерации в моем алгоритме, раз в 5-10 легче чем в бинарном дереве.
3. вес вставки и удаления значений легче на порядок.

ушел проверять имперически...

[Portnov]

edranovdenis
а где же результаты применения столь любимого вами принципа open source?
в смысле, если найден алгоритм поиска с временем работы О(1) - интересно было бы посмотреть.

[edranovdenis]

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

кстати, я не утверждал что О(1), оно к нему стремиться. кроме того очень близко от него находиться.
1 там быть не может.

вообще-то может при аппаратном решении(см. выше), но тяжело реализовывается.

[sarutobi]

Да, посмотреть на реализацию алгоритма с близким к О(1) временем работы очень интересно....
edranovdenis, к вам есть несколько вопросов:
вы несколько раз упомянули что образование у вас "не компьютерное". Можно узнать какое?
что вы имели в виду под "распараллелить бинарное дерево"?

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

Гм..... интересный взгляд на вещи......

[edranovdenis]

1. zx-spectrum класса с 5-го.
ср. спец. технология хранения и переработки зерна. (занятия по информатике практически не посещал после того как спросили что такое чегототам.dll я рассказал что такое динамические библиотеки, оказывается имелось в виду что dll это расширение файла :-)
несколько раз посещал лекции в универе(ходил с бывшим однокласником), после чего решил туда не поступать.
сейчас учусь заочно на юриста. информатики нет.
есть свое дело - 1с и СПС Референт.

2. "распаралелить бинарное дерево". не знал бы о чем речь сам бы не понял :-), имел в виду возможность разделение на несколько процессов выполняющихся паралельно.

3. ничего странного. (сорри за оформление, так было... а texа пока нет под рукой)

вО МНОГИХ ПРОГРАММАХ ПОИСК ТРЕБУЕТ НАИБОЛЬШИХ ВРЕМЕННЫХ ЗАТРАТ, ТАК ЧТО ЗАМЕНА
ПЛОХОГО МЕТОДА ПОИСКА НА ХОРОШИЙ ЧАСТО ВЕДЕТ К СУЩЕСТВЕННОМУ УВЕЛИЧЕНИЮ СКОРОСТИ
РАБОТЫ. дЕЙСТВИТЕЛЬНО, НЕРЕДКО УДАЕТСЯ ТАК ОРГАНИЗОВАТЬ ДАННЫЕ ИЛИ СТРУКТУРУ
ДАННЫХ, ЧТО ПОИСК ПОЛНОСТЬЮ ИСКЛЮЧАЕТСЯ, Т. Е. МЫ ВСЕГДА ЗНАЕМ ЗАРАНЕЕ, ГДЕ
НАХОДИТСЯ НУЖНАЯ НАМ ИНФОРМАЦИЯ. сВЯЗАННАЯ ПАМЯТЬ ЯВЛЯЕТСЯ ОБЩЕПРИНЯТЫМ МЕТОДОМ
ДОСТИЖЕНИЯ ЭТОГО; НАПРИМЕР, В СПИСКЕ С ДВУМЯ СВЯЗЯМИ НЕТ НЕОБХОДИМОСТИ ИСКАТЬ
ЭЛЕМЕНТ, СЛЕДУЮЩИЙ ЗА ДАННЫМ ИЛИ ПРЕДШЕСТВУЮЩИЙ ЕМУ. дРУГОЙ СПОСОБ ИЗБЕЖАТЬ
ПОИСКА ОТКРЫВАЕТСЯ ПЕРЕД НАМИ, ЕСЛИ ПРЕДОСТАВЛЕНА СВОБОДА ВЫБОРА КЛЮЧЕЙ.
сДЕЛАЕМ ИХ ЧИСЛАМИ $\{1,2, \ldots, N\}$, И ТОГДА ЗАПИСЬ, СОДЕРЖАЩАЯ $K$, МОЖЕТ
БЫТЬ ПРОСТО ПОМЕЩЕНА В ЯЧЕЙКУ $|TABLE|+K$. оБА ЭТИ СПОСОБА ИСПОЛЬЗОВАЛИСЬ ДЛЯ
УСТРАНЕНИЯ ПОИСКА ИЗ АЛГОРИТМА ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ, ОБСУЖДАВШЕГОСЯ В
П.~2.2.3. тЕМ НЕ МЕНЕЕ ВО МНОГИХ СЛУЧАЯХ ПОИСК НЕОБХОДИМ (НАПРИМЕР, КОГДА
ОБ®ЕКТАМИ ТОПОЛОГИЧЕСКОЙ СОРТИРОВКИ ЯВЛЯЮТСЯ СИМВОЛИЧЕСКИЕ ИМЕНА, А НЕ ЧИСЛА),
ТАК ЧТО ВЕСЬМА ВАЖНО ИМЕТЬ ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ПОИСКА.

Д. Кнут Исскуство программирования. Том 3 (однако пригодилось :-)

[sarutobi]

Бинарное дерево - это структура данных, не более того. Как осуществляется обращение к этой структуре - зависит от программного кода, и если он thread-safe(предусматривает возможность множественных обращений) - то ответ на ваш вопрос очевиден.
По поводу цитаты из Кнута
для того чтобы мне точно знать что требуемый мне элемент находится в ячейке N, я должен каким то образом рассчитать это N. Согласны? Наиболее общий вариант подобного расчета - хэширование, но предлагаемый вариант- хэш есть значение первого символа слова- имеет один недостаток: "Абрикос" и "Апельсин" имеют один и тот же хэш.
Второе замечание по поводу цитаты из Кнута - об использовании табличного программирования.
В чисто математическом понимании функция md5 (хэш-функция) необратима (не существует обратной функции, сопсобной по хэшу восстановить исходное значение). Однако, возможность восстановления аргумента существует. И решение здесь - именно табличное программирование. Создается таблица из пары аргумент-хэш md5. А теперь зайдите на сайт http://passcrack.spb.ru/ и посмотрите на размер этих таблиц и их возможности.
Это все к тому что программист чаще всего "слуга двух господ" - нужно обеспечить приемлемое быстродействие и приемлимый расход ресурсов. И всегда чем то приходится жертвовать (нужна скорость - жертвуют ресурсами, нужны ресурсы - жертвуют скоростью).

[edranovdenis]

to sarutobi:
вообще-то я пришел сюда не спорить и доказывать свою правоту, а набраться доп. знаний по теме для решения определенной задачи.

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

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

[edranovdenis]

рекомендую к прочтению:
http://www.citforum.ru/hardware/articles/asmem.shtml

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

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

[sarutobi]

edranovdenis
Вообще то я тоже не спорю. Насчет распараллелить бинарное дерево - Вы задали вопрос - получили ответ.
Насчет того что MD5 хэш не может быть порядковым - Вы сами то поняли что сказали? Этот хэш представляет из себя 4 числа long (32 бита).
Ваш алгоритм интересен, но как Вы предлагаете его распараллеливать?
И к сожалению сей алгоритм целиком не Ваш - похожий используется в ARP-протоколе для разрешения IP-адреса в MAC (правда там программно-аппаратная реализация).

[edranovdenis]

внутренности MD5 мне неизвестны, но 4 числа по 32 бита это 16 байт. чтобы хранить все возможные комбинации в таблице и соблюсти порядковость (выполняем несложный подсчет) необходимо...
4951155726514409703879249359,0472 терабайт
представленные таблицы в 40Гб содержат словарь наиболее часто используемых паролей, которые по определению не могут быть порядковыми.
(вы из принципа уперлись или действительно не понимаете о чем была речь в цитате из кнута?)

Насчет распаралеливания я наверное все-таки погарячился, реализация тяжеловата(чудес на свете не так много как нам хочется), пока отложу.

Свой алгоритм я не расскрывал.
"ARP - протокол низкого уровня. Поддерживается на уровне ядра и/или дравера сетевой платы." про аппаратную составляющую ничего не сказано.

Даешь каждому мужику бутылку водки, а каждой бабе трезвого мужика! Ура товарищи!
Опять лозунги.

[sarutobi]

Насчет МД5 я привел пример (достаточно показательный) на предмет "скорость работы против объема данных". И все. Поскольку Вы не хотите ничего слушать, а тем паче думать о том, что и зачем Вам говорят - а лишь как попугай кричите про лозунги - дальнейшее общение с Вами считаю бессмысленным.