Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 30
×

Вибір бібліотеки чи бази даних для пошуку — питаю поради

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Чи може хтось підказати бібліотеку чи базу даних максимально ефективну під одну єдину задачу — пошук по словнику декілька сотень тисяч слів. Під перл або сі.

Наразі я перевірив два варіянти.

Лінійний пошук в файлах, розкладених по дворівневому каталогу (з проміжним зберіганням в перловому хеші) — швидкодія цього процесу на словнику в 77000 словооснов видалась мені помірною, скажімо так.

Той же пошук в таблиці MySQL дає 5–7 відсотків виграшу по швидкодії.

Але, при цьому, структура даних в MySQL простіша простої — не бачу там практично ніяких можливостей оптимізації (всі поля фіксованої довжини, пошуковий індекс по одному полю — от і вся структура). В той же час, оптимізувати пошук по файловому дереву дуже навіть можна. Тільки навіщо ж майструвати велосипед?

Може, хтось підкаже підходящий інструмент?

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Зачем изобретать велосипед — получится самокат, с отваливающимися колесами:)

З правил трапляються й винятки: -)

Перед тим, як розробляти щось, як правило ознайомлюються з подібними рішеннями:)

2 Alex: спасибі! це саме ті поради, яких я й питав
2 Сергей Волошин: Sphinx — це, як розумію, «інтеґроване рішення» щодо пошуку, мене просто такі не цікавлять. Не тому, що маю щось проти — але тому що сам розробляю щось такого типу.

2 Andrew: «типові випадки» бувають різних типів. Ніж вступати в обговорення — Ви б хоч поцікавились, про що мова. Словом, облишимо це.

А еще, на первый взгляд, мне кажется, было бы намного эффективней построить perfect hash (например gperf) по выбраным данным, и по нему потом уже искать

Префиксное_дерево — і зовсім не факт, що в перлі вони реалізовані, оскільки перловий хеш, це структура, яка повинна і швидко читатись, і швидко формуватись

search.cpan.org/search query=trie& mode=all

Мені ж потрібне тільки швидке читання (бо читань — мільйони, а сформувати структру треба разово). Ось такі алґоритми — вже розроблені, відлагоджені і оптимізовані — я й шукаю.

В типовому випадку обробка даних займає набагато більше часу ніж пошук по хешу, і тоді розробка своїх алгоритмів пошуку змісту не має.
Також якщо вся програма вже відпрацьовує за пару секунд, то замовник в кожному разі не захоче платити за подальшу оптимізацію.
В специфічних випадках можна пошукти щось (наприклад блум-фільтри), але то як правило тюниться під конкретну задачу, а не взагалі. Бажано мати типові датасети, знати тип мікроархітектури цільового процесора, розміри кешів, кількість ядер і т.п.
Треба також знати тип пошуку (наприклад чи потрібно точно знайти слово, чи з імовірністю (1- 1e-12))
В будь-якому разі це передбачає речі типу Сі, Паскаль, Асемблер.

Писати таке на Перлі беззмістовно через низьку швидкість інтерпретації.

2Павло Дзіковський:, а що ви скажете про Sphinx і компанію? Дивились їх?

Запити з бази в прикладі — це осібні пошуки, кожен з яких, природньо, виконується по індексу бази — саме задля цього індексу БД ц використовується. Якщо ж читати все чохом в хеш, то індекс бази не потрібен — всі ці дані можуть лежати на диску в посортоваеному порядку і, відтак, читання їх з дискового файлу буде, думаю, швидшим, аніж запит з БД.

Щодо встроєних в перл хешів — все ясно. Але окрім просто хешів — є спеціяльні швидкі алґоритми типу «префіксного дерева» — ru.wikipedia.org/...ефиксное_дерево — і зовсім не факт, що в перлі вони реалізовані, оскільки перловий хеш, це структура, яка повинна і швидко читатись, і швидко формуватись. Мені ж потрібне тільки швидке читання (бо читань — мільйони, а сформувати структру треба разово). Ось такі алґоритми — вже розроблені, відлагоджені і оптимізовані — я й шукаю. Не думаю, що вибір, написання і оптимізація такого алґоритму — це 10 рядків, ой, не думаю.

Що ж до того, щоб вичитувати всі дані з MySQL у внутрішній хеш — для цієї процедури MySQL, вважаю, не потрібен, оскільке скоріше буде вичитати всі ці ж дані в пам"ять зі спеціяльно подготованих файлів.

Тоді чому ж у приладі дані беруться з бази?

От про деякий бібліотечний алґоритм для такої процедури — вичитування і оптимальна організація масиву в пам"яті — я й запитую.
Вичитування з файла — це один оператор.

Алгоритми організації хешів і списків у пам’яті — це частина стандартної бібліотеки на мовах типу перла чи пітона. Ці алгоритми використовуються автоматично при звертанні до відповідних структур даних. І тому шукати тут нічого не потрібно.

Повторюсь — я без проблем можу запрограмувати це самостійно, але шукаю готове рішення, щоб не писати програму, яка вже багатократ написана до мене.
Така програма займає приблизно 10 рядків на пітоні.
Написати її самому набагато швидше, ніж щось шукати.

То у чому власне проблема?

Рекомендація «повнотекстового пошуку» та инших готових рішень — не приймається, даруйте.
Що ж до того, щоб вичитувати всі дані з MySQL у внутрішній хеш — для цієї процедури MySQL, вважаю, не потрібен, оскільке скоріше буде вичитати всі ці ж дані в пам"ять зі спеціяльно подготованих файлів. От про деякий бібліотечний алґоритм для такої процедури — вичитування і оптимальна організація масиву в пам"яті — я й запитую.

Повторюсь — я без проблем можу запрограмувати це самостійно, але шукаю готове рішення, щоб не писати програму, яка вже багатократ написана до мене.

Вам рекомендуется использовать полнотекстовый поиск. Для этого СУБД строит так называемый полнотекстовый индекс — словарь, в котором перечислены все слова и указано, в каких местах они встречаются. При наличии такого индекса достаточно осуществить поиск нужных слов в нём и тогда сразу же будет получен список документов, в которых они встречаются.

Я не спец по MySQL, как это настроить в MS SQL сказать могу.

Про sqlite vs mysql тест — там используеться mysql выпущеный больше 8 лет назад!

Наскільки я зрозумів, 99% часу мабуть займає оператор
$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 словооснов видалась мені помірною, скажімо так.
Можна якісь деталі? Цифри?
Мабуть повинно було б бути біля мільйона пошуків в секунду.
Це мало? А скільки треба?
І до чого тут підкаталоги?
77000 слів — це файл розміром в мегабайт.
Чи програма запускається, шукає 1 слово і на цьому закінчується?

Чи треба перевірити по словнику мільярд слів зразу?

Той же пошук в таблиці MySQL дає 5−7 відсотків виграшу по швидкодії.

Можна деталі?
Я очікував що перловий хеш буде давати 1е6 пошуків в секунду.

А MySQL напевно буде в зовсім інших порядках величин.

В той же час, оптимізувати пошук по файловому дереву дуже навіть можна.

Знов нічого не зрозуміло.

Якщо дані вже є в перловому хеші, то до чого тут файлове дерево?

Інструменти типу такого
sphinxsearch.com
можуть забазпечити швидкість, суттєво більшу за MySQL
У нас ще стаття була:

www.developers.org.ua/...-lucene-xapian

sqlite судячи з тестів може бути трохи швидшим за MySQL:
www.sqlite.org/speed.html

і по ідеї з ним простіше ніж з MySQL працювати.

Такой объем данных спокойно должен поместиться в памяти полностью.

Или я что-то не понял их условии задачи?

Підписатись на коментарі