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

anonymous 03.05.2010 18:23

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

Відповісти

Підтримати

Павло Дзіковський 03.05.2010 10:04

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

Відповісти

Підтримати

Sergii Voloshyn Product Manager в DOU.ua 03.05.2010 08:39

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

Відповісти

Підтримати

Павло Дзіковський 03.05.2010 08:06

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

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

Відповісти

Підтримати

anonymous 02.05.2010 12:04

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

Відповісти

Підтримати

anonymous 02.05.2010 11:54

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

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

Відповісти

Підтримати

anonymous 02.05.2010 11:28

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

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

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

Відповісти

Підтримати

Sergii Voloshyn Product Manager в DOU.ua 02.05.2010 10:28

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

Відповісти

Підтримати

Павло Дзіковський 02.05.2010 09:50

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

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

Відповісти

Підтримати

anonymous 02.05.2010 08:09

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

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

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

Вичитування з файла — це один оператор.

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

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

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

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

Відповісти

Підтримати

Павло Дзіковський 02.05.2010 05:44

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

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

Відповісти

Підтримати

anonymous 02.05.2010 00:44

www.mysql.ru/...ext_Search.html

Відповісти

Підтримати

anonymous 02.05.2010 00:43

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

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

Відповісти

Підтримати

crypto5 01.05.2010 23:07

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

Відповісти

Підтримати

anonymous 01.05.2010 20:06

Наскільки я зрозумів, 99% часу мабуть займає оператор
$sth_v-> execute ($basis);
Його слід замінити на пошук по хешу і тоді вся програма повинна відпрацьовувати мільйон пошуків приблизно за 1 секунду, не рахуючи операторів # обробка знайденого;
Тобто
«select * from index_v where basis =? »
замінити на
«select * from index_v order by basis»
Потім кожну групу даних, що відносяться до одного значення basis, записати в один елемент перлового хеша.

Потім замінити $sth_v-> execute ($basis); на читання з цього хеша.

Відповісти

Підтримати

Павло Дзіковський 01.05.2010 19:47

Виграш від заміни MySQL на sqlite при пошуку по індексу — відсотків 10, як бачу. Теж діло, звісно — може й скористаюсь, як не буде кращих варіянтів. спасибі!

Відповісти

Підтримати

Павло Дзіковський 01.05.2010 19:42

Ось вся програма в сенсі пошуку
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/...фиксное_дерево вже вилизані належним чином і нормально працюють.

Відповісти

Підтримати

anonymous 01.05.2010 18:46

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

Слово «пошук» може означати дуже багато різних речей.

Варто було б описати задачу детальніше. Що взагалі робить програма і яка швидкодія потрібна (порядок величини)?

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

Можна якісь деталі? Цифри?
Мабуть повинно було б бути біля мільйона пошуків в секунду.
Це мало? А скільки треба?
І до чого тут підкаталоги?
77000 слів — це файл розміром в мегабайт.
Чи програма запускається, шукає 1 слово і на цьому закінчується?

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