Вибір бібліотеки чи бази даних для пошуку — питаю поради
Чи може хтось підказати бібліотеку чи базу даних максимально ефективну під одну єдину задачу — пошук по словнику декілька сотень тисяч слів. Під перл або сі.
Наразі я перевірив два варіянти.
Лінійний пошук в файлах, розкладених по дворівневому каталогу (з проміжним зберіганням в перловому хеші) — швидкодія цього процесу на словнику в 77000 словооснов видалась мені помірною, скажімо так.
Той же пошук в таблиці MySQL дає
Але, при цьому, структура даних в MySQL простіша простої — не бачу там практично ніяких можливостей оптимізації (всі поля фіксованої довжини, пошуковий індекс по одному полю — от і вся структура). В той же час, оптимізувати пошук по файловому дереву дуже навіть можна. Тільки навіщо ж майструвати велосипед?
Може, хтось підкаже підходящий інструмент?
21 коментар
Додати коментар Підписатись на коментаріВідписатись від коментарівЗачем изобретать велосипед — получится самокат, с отваливающимися колесами:)
З правил трапляються й винятки: -)
Перед тим, як розробляти щось, як правило ознайомлюються з подібними рішеннями:)
2 Сергей Волошин: Sphinx — це, як розумію, «інтеґроване рішення» щодо пошуку, мене просто такі не цікавлять. Не тому, що маю щось проти — але тому що сам розробляю щось такого типу.
2 Andrew: «типові випадки» бувають різних типів. Ніж вступати в обговорення — Ви б хоч поцікавились, про що мова. Словом, облишимо це.
А еще, на первый взгляд, мне кажется, было бы намного эффективней построить perfect hash (например gperf) по выбраным данным, и по нему потом уже искать
search.cpan.org/search query=trie& mode=all
Також якщо вся програма вже відпрацьовує за пару секунд, то замовник в кожному разі не захоче платити за подальшу оптимізацію.
В специфічних випадках можна пошукти щось (наприклад блум-фільтри), але то як правило тюниться під конкретну задачу, а не взагалі. Бажано мати типові датасети, знати тип мікроархітектури цільового процесора, розміри кешів, кількість ядер і т.п.
Треба також знати тип пошуку (наприклад чи потрібно точно знайти слово, чи з імовірністю (1- 1e-12))
В будь-якому разі це передбачає речі типу Сі, Паскаль, Асемблер.
Писати таке на Перлі беззмістовно через низьку швидкість інтерпретації.
2Павло Дзіковський:, а що ви скажете про Sphinx і компанію? Дивились їх?
Щодо встроєних в перл хешів — все ясно. Але окрім просто хешів — є спеціяльні швидкі алґоритми типу «префіксного дерева» — ru.wikipedia.org/...ефиксное_дерево — і зовсім не факт, що в перлі вони реалізовані, оскільки перловий хеш, це структура, яка повинна і швидко читатись, і швидко формуватись. Мені ж потрібне тільки швидке читання (бо читань — мільйони, а сформувати структру треба разово). Ось такі алґоритми — вже розроблені, відлагоджені і оптимізовані — я й шукаю. Не думаю, що вибір, написання і оптимізація такого алґоритму — це 10 рядків, ой, не думаю.
Тоді чому ж у приладі дані беруться з бази?
Вичитування з файла — це один оператор.Алгоритми організації хешів і списків у пам’яті — це частина стандартної бібліотеки на мовах типу перла чи пітона. Ці алгоритми використовуються автоматично при звертанні до відповідних структур даних. І тому шукати тут нічого не потрібно.
Така програма займає приблизно 10 рядків на пітоні.Написати її самому набагато швидше, ніж щось шукати.
То у чому власне проблема?
Що ж до того, щоб вичитувати всі дані з MySQL у внутрішній хеш — для цієї процедури MySQL, вважаю, не потрібен, оскільке скоріше буде вичитати всі ці ж дані в пам"ять зі спеціяльно подготованих файлів. От про деякий бібліотечний алґоритм для такої процедури — вичитування і оптимальна організація масиву в пам"яті — я й запитую.
Повторюсь — я без проблем можу запрограмувати це самостійно, але шукаю готове рішення, щоб не писати програму, яка вже багатократ написана до мене.
www.mysql.ru/...ext_Search.html
Я не спец по MySQL, как это настроить в MS SQL сказать могу.
Про sqlite vs mysql тест — там используеться mysql выпущеный больше 8 лет назад!
$sth_v-> execute ($basis);
Його слід замінити на пошук по хешу і тоді вся програма повинна відпрацьовувати мільйон пошуків приблизно за 1 секунду, не рахуючи операторів # обробка знайденого;
Тобто
«select * from index_v where basis =? »
замінити на
«select * from index_v order by basis»
Потім кожну групу даних, що відносяться до одного значення basis, записати в один елемент перлового хеша.
Потім замінити $sth_v-> execute ($basis); на читання з цього хеша.
Виграш від заміни MySQL на sqlite при пошуку по індексу — відсотків 10, як бачу. Теж діло, звісно — може й скористаюсь, як не буде кращих варіянтів. спасибі!
my $sth_v = $dbh-> prepare («select * from index_v where basis =? »);
while (my $basis =...) {
$sth_v-> execute ($basis);
while (my $o = $sth_v-> fetchrow_arrayref) {
# обробка знайденого;
} }
Структура таблиці:
basis char (30) not null
g0 char (5) not null
g1 char (5) not null
l0 tinyint (4)
f0 char (5) not null
На таблиці один індекс — по полю basis
—
Значення basis при виконанні програми йдуть в абсолютно випадковому порядку (я схильний думати, що цей фактор не оптимізується), їх кількість — декілька мільйонів за раз, скажімо. Мова йде, властиво, про послівну індексацію значного корпусу документів.
Відповідно, все що треба — максимальна швидкість запитів. Нюанси оптимізації алґоритмів самого пошуку я би не хотів обговорювати, оскільки не хочу в тисячу перший раз програмувати ці алґоритми — шукаю, навпаки, бібліотеку, де коди пошукових алґоритмів (наприклад, «префіксне дерево» — ru.wikipedia.org/...фиксное_дерево вже вилизані належним чином і нормально працюють.
Слово «пошук» може означати дуже багато різних речей.
Варто було б описати задачу детальніше. Що взагалі робить програма і яка швидкодія потрібна (порядок величини)?
Можна якісь деталі? Цифри?Мабуть повинно було б бути біля мільйона пошуків в секунду.
Це мало? А скільки треба?
І до чого тут підкаталоги?
77000 слів — це файл розміром в мегабайт.
Чи програма запускається, шукає 1 слово і на цьому закінчується?
Чи треба перевірити по словнику мільярд слів зразу?
Можна деталі?Я очікував що перловий хеш буде давати 1е6 пошуків в секунду.
А MySQL напевно буде в зовсім інших порядках величин.
Знов нічого не зрозуміло.Якщо дані вже є в перловому хеші, то до чого тут файлове дерево?
sphinxsearch.com
можуть забазпечити швидкість, суттєво більшу за MySQL
У нас ще стаття була:
www.developers.org.ua/...-lucene-xapian
www.sqlite.org/speed.html
і по ідеї з ним простіше ніж з MySQL працювати.
Или я что-то не понял их условии задачи?