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

[edranovdenis]

to sarutobi: вам надоело? ну, слава богу! мне тоже. а то так до "тематического флейма" скатится недолго.

бинарное дерево кажеться расспаралеливается.

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

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

PS: мда... пора уже книгу написать "синдром велосипеда" :)

[edranovdenis]

OpenNET.ru 17.11.2006 18:17
В СУБД MySQL появится новое хранилище данных, основанное на разработке NitroEDB компании NitroSecurity, оптимизированной для многопоточного помещения большого объема данных в реальном режиме времени и обеспечивающей отличную производительность при выборке информации из БД содержащей миллиарды записей.

NitroSecurity originally developed its database technology to address the growing demand for real-time analysis within the network security event management market. Utilizing unique indexing techniques, data management methods and query processing algorithms, the technology enables “multiple order of magnitude” increases in relational data management and query performance with multi-billion record volumes – running on commodity hardware. The technology is currently deployed in NitroView Enterprise Security Manager, the industry’s highest performance network security monitoring and analysis solution.

[edranovdenis]

ну и разозлили меня эти NitroSecurity! :-)
наконец я создал макет кода (без оптимизаций).

машина: Celeron 2.66; DDR400 512Mb.
ОС: VMWare Player, Mandriva Linux 2006, gcc 4.0.1
алгоритм: в словарь помещенно 815Кб/86000 слов, затем эти же слова были найдены в словаре.
результат: помещение в словарь - 3сек., поиск 86000 слов - 8сек.
вывод: скорость ~10000 слов/сек.

Пока не сравнивал с другими алгоритмами. Если есть специалисты по БД, немогли бы вы привести другие примеры (особенно интерисует Berkley DB)? Спасибо.

[sarutobi]

машина: AMD Athlon 3000+ 512 Mб
ОС: openSuSE 10.1
алгоритм: cat Linux_polnoe_rukovodstvo.txt | ispell > log.txt
результат: Размер входного файла 2 177 289 байт. Размер лога 1 666 929 байт, 443 128 строк. Время исполнения 13 секунд.
вывод: скорость 443 128/13 = 34 086,8 слов/сек.
Исходные данные те же, алгоритм
cat Linux_polnoe_rukovodstvo.txt | ispell
Время 42 сек.
Вывод: скорость 443 128/42=10 526.9 слов/сек.
Словари для ispell из стандартной поставки - русский словарь Лебедева (1 149 000 слов).

[edranovdenis]

cat test.txt | ispell - выводит краткое описание ispell.
ispell test.txt - выводит диалог по замене слов.
Можно подробнее? (а то я дальше mc и gcc не далеко пока ушел...)

[sarutobi]

ispell testtext.txt так и должна работать - выполняется проверка правописания и при отсутсвии слова в словаре предлагаются варианты.
cat testtext.txt | ispell предлагает этой утилите проверить текст, передаваемый как входной поток - то есть диалога не будет а будут выдаваться только предупреждения о неверных словах. Почему оно у Вас не срабатывает - непонятно. просто ispell переходит в интерактивный режим?
Если ничего не получится - дайте Ваш тестовый файл, прогоню его вечером. так же могу попробовать прогнать его через БД.

[edranovdenis]

переписал с++ код на чистый си еще в ассемблере подправил чуток.
мда....
86000 слов искал 100 раз в цикле (когда было 1 подумал ошибся где :-)
результат - 2 сек.
итого - 86000*100/2=4300000 слов/сек
...не думал что си++ такой тормоз, когда ассемблерный код глянул - Афигел!

Пойду на "живой" машине прогоню...
заодно test.txt заберу и выложу, а то в терминале сижу (короче почему сразу файл выложить не могу объяснять долго. намудрил я тут.).

[edranovdenis]

Прогнал на Sempron 2800+ 512Mb DDR2 533
ОС: "живая" Mandriva 2006 (под селероном была VMWare)
результат 3 300 000 слов/сек.
видимо сказалась более низкая частота процессора и латентность памяти...

ну да, процессор с большей частотой за секунду сделает больше a++ (инкрементов) чем процессор с меньшей частотой но лучшей архитектурой. вот такие размышления...

файл test.txt прилагается. я из него предварительно убрал все знаки припинания из-за чего некоторые слова "слиплись".

[Bruce]

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

[sarutobi]

Загнал файл в mysql.
Число слов в примере 86396.
Поиск без индекса
Точный поиск по слову 0.07 сек (1 234 229 слов/секунду)
нечеткий поиск по известному началу слова 0.15 сек (575 973 слов/секунду)
нечеткий поиск по известному буквосочетанию в слове 0.14 сек (617 144 слов/секунду)
Поиск с индексом
Точный поиск по слову 0.02 сек (4 319 800 слов/секунду)
нечеткий поиск по известному началу слова 0.02 сек (4 319 800 слов/секунду)
нечеткий поиск по известному буквосочетанию в слове 0.21 сек (411 410 слов/секунду)

Возможности нечеткого поиска в Вашем алгоритме присутствуют?

[edranovdenis]

можно код Вашей работы с mysql?

возможностей реализованно пока минимум: add и find :)

[Bruce]

представляю "код":
с шелл скрипта заносится в базу
и далее - select * ....
какой код?

[sarutobi]

Первый результат - без индекса, вотрой - с индексом.
Точный поиск:
select * from words where txt='run';
12 rows in set (0.10 sec)
12 rows in set (0.01 sec)
select * from words where txt='remove';
1224 rows in set (0.07 sec)
1224 rows in set (0.01 sec)
Нечеткий поиск по известному началу слова
select * from words where txt like 'red%';
148 rows in set (0.06 sec)
148 rows in set (0.01 sec)
select * from words where txt like 'r%';
5973 rows in set (0.08 sec)
5973 rows in set (0.03 sec)
Нечеткий поиск по буквосочетанию
select * from words where txt like '%hat%';
930 rows in set (0.12 sec)
930 rows in set (0.24 sec)

[Bruce]

к слову сказать, для БД есть куда более объективные тесты. кои вам предлагается найти в гугле. На эти цифры ориентироваться бесмыссленно )

[Crazy]

Как будущему математику-программисту создается впечатление, что создается очередной велосипед.
В каждой хорошей СУБД включены оптимальные алгоритмы поиска данных. В MySQL встроенные регулярные выражения и подпрограммы. Эффективность MySQL зависит от структуры БД, и SQL запросов.
В книгах описаны не все оптимальные и современные алгоритмы.

[sarutobi]

Bruce
Пусть молодой человек свой алгоритм потестит на этих же данных.

[Bruce]

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

если говорят, что за 35 шагов без хеширования на любых объёмах данных - посмотрим

[edranovdenis]

когда я зогоняю слова в базу, то функция add(word) делает поиск по базе, если слова нет, то создает запись в базе, если есть, то ничего не делает. получается что содержимое базы это есть уникальные ключи. функция find(word) ищет слово и возвращает 1 если находит и 0 если не находит, в принципе, может возвращать указатель на реквизиты. т.о. 1-й цикл бежит по test.txt и если видит пробел, то значит слово закончилось и делает add(), и так до конца файла. создали словарик. 2-й цикл опять бежит по test.txt и на каждое слово делает find(), (естественно всегда возвращается 1). Получается 86k find() на один цикл. (надеюсь мы правильно друг друга поняли)

насчет примеров с SELECT думаю, что можно реализовать следующим образом: нашли слово и получили в виде реквизитов список указателей на строки (ROWS). скорость будет чуть больше поиска одного слова.

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

to crazy:
"В книгах описаны не все оптимальные и современные алгоритмы."
если не затруднит не моглибы вы в кратце описать принципы работы таких алгоритмов? очень интересно. буду признателен.

[sarutobi]

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

Тогда у вас не 86 с чем то тысяч слов а гораздо меньше + у них уникальные ключи. В моем тесте ключей не было вообще, таблица представляет собой один столбец varchar(250).

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

это пока лишнее. Нечеткий поиск вещь достаточно сложная.

[edranovdenis]

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

to sarutobi: уточните пожалуйста, вы делали 86k SELECT запросов когда получили результат 4,3млн слов/сек?

:) пока писал вы уже ответили. а можно ли поиск по ключу проверить в SQL?

[edranovdenis]

offtop:
Компания "Гарант" представляет новую версию системы ГАРАНТ Платформа F1 Турбо. Благодаря встроенному морфологическому анализатору и уникальному алгоритму сортировки результатов по степени соответствия запросу скорость поиска в версии Турбо увеличилась в 200 раз*, а точность поиска - в 10 раз*!

*По результатам сравнительных испытаний с обычной версией справочной правовой системы ГАРАНТ

[edranovdenis]

Занимался дополнительной оптимизацией и пришел к выводу, что код for(int n=10;n>0;n--), быстрее чем for(int n=0;n<10;n++). Но при компиляции с параметром -O9 в ассемблере они выглядят одинаково по первому варианту.

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

Кстати, про -О9 я вовремя вспомнил :). Новый результат на Celeron'e 12 000 000 слов/сек.

PS: кто нибудь гонял test.txt на SQL?

[Bruce]

-O9 ничего не даёт. Максимальный - третий. По крайней мере, AFAIK.

свои советы я уже все дал, но что-то этот товарищ притих ждём новых результатов )

[edranovdenis]

в каждую минуту жизни мы должны делать лучшее что можем сделать в эту минуту. я пока занят.

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

[edranovdenis]

доделал нечеткий поиск с О(1). единичка оказалась раз в 5 тяжелее чем при точном поиске :)

нашел ошибку в программе. проверенный и перепроверенный результат вдвое ниже. (Transmeta 1Ггц - 2 500 000 слов/сек.)

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

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

[Liksys]

доделал нечеткий поиск с О(1). единичка оказалась раз в 5 тяжелее чем при точном поиске

Какой алгоритм использовал?

[edranovdenis]

как только название придумаю, сразу скажу ;)

[Liksys]

Не "Алгоритм прыжка"? (с) Мое!

[edranovdenis]

тогда уж "алгоритм прыжка через гиперпространство"

[edranovdenis]

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

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