возложите свои проблемы на БД, при этом проверяйте так,
select slovo FROM slovar WHERE slovo='mama' or slovo='myla' or slovo='ramy'
то есть не по одному слову, а предложениями, а затем уже результат сравнивайте "ручкими"...
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Perl: Общие вопросы > Как ускорить поиск по словарю? |
| Автор: Suppir 4.4.2012, 16:55 |
| Добрый день! Есть словарь из 200 тыс. слов. Мне нужно перебирать строки в файле и смотреть, есть ли слова из этой строки в моем словаре. Сейчас у меня словарь тупо отсортирован по алфавиту а загнан в хеш: $hash{word}=1. Ищу с помощью if (exists $hash{$word}) Подскажите, как лучше организовать такой словарь, чтобы ускорить в нем поиск? |
| Автор: Pretorian 4.4.2012, 17:09 |
| если отсортирован, можно организовать бинарный поиск. будет искать быстро |
| Автор: Pfailed 4.4.2012, 18:50 |
| Как вы умудрились отсортировать хеш? |
| Автор: ginnie 4.4.2012, 19:14 |
| Suppir, а какая скорость поиска сейчас и какую необходимо получить? |
| Автор: DurRandir 4.4.2012, 22:40 |
| Cкорость доступа к хэшу вообще O(1). Вы уверены, что проблема именно в этом, а не в чём-то другом? |
| Автор: Suppir 5.4.2012, 08:45 |
| Насчет хеша я наврал, конечно. Первоначальная версия программы была написана на Perl и я использовал хеш. А потом я перенес код на c# и использовал список (List) - аналог массива Perl. Так вот, сначала я использовал просто отсортированный по алфавиту словарь. А теперь сделал частотный - слова, которые встречаются часто, расположены в начале словаря, а те, которые встречаются редко - в конце. Программа стала в 5 раз быстрее!!! |
| Автор: od0201 5.4.2012, 14:18 |
| с хешем конечно быстрее, но.....как у меня есть вариант, который вам еще не предлагали (не судите строго) возложите свои проблемы на БД, при этом проверяйте так, select slovo FROM slovar WHERE slovo='mama' or slovo='myla' or slovo='ramy' то есть не по одному слову, а предложениями, а затем уже результат сравнивайте "ручкими"... |
| Автор: Suppir 6.4.2012, 13:15 |
| По базам данных поиск намного медленней, чем по словарю в оперативной памяти, имхо. |
| Автор: 500mhz 6.4.2012, 14:08 |
| зафигачить весь словарь (каждое слово) в crc32 , получим 800 кб что фигня, и сверять не слово из букавок непонятной длинны а crc32 слова, с точки зрения любого процессора самый быстрый вариант. |
| Автор: Suppir 6.4.2012, 14:12 |
| "зафигачить весь словарь (каждое слово) в crc32" можно поподробнее? Добавлено через 1 минуту и 51 секунду Дело в том, что мне потом не одно слово нужно будет искать в словаре, а много миллионов слов проверять через этот словарь. Если для каждого слова еще вычислять контрольную сумму, то, боюсь, это будет медленней работать, чем просто поиск по словарю. |
| Автор: 500mhz 6.4.2012, 14:16 |
| Ну к примеру в словаре слово "макулатура" занимает 10 байт + 1 как идентификатор конец строки (в лучшем случае) и того 11 байт которые нада сверить. Вместо слова храним его crc - контрольную сумму которая займет всего 4 байта. Соответственно при проверке текста , берем слово из текста, получаем его crc32 и сверяем с нашей базой-словарем. Если есть то есть, а если нет то нет ) |
| Автор: Suppir 6.4.2012, 14:47 |
| Если одно слово нужно сверить, то понятно. Но если нужно несколько миллионов слов сверять со словарем, то нужно каждое слово конвертировать в этот crc. |
| Автор: 500mhz 6.4.2012, 14:57 |
| Нифига, словарь ты готовиш заранее, а вычесление контрольной суммы строки/слова не процессороемкая задача. А вот сравнение двух строк очень даже. Грубо говоря не вникая в архитиктуру, сравнение двух 4 байтовых значений процессор сделает всего 1 операцией, а сравнение строки из 10 байт за 10. |