Цитата(Леопольд @ 7.9.2011, 12:36  ) |
| std::sort и std::find |
лучше параллельные алгоритмы из http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Что использовать для быстрого поиска? |
| Автор: becks 7.9.2011, 12:18 |
| Добрый день коллеги, такой вопрос: Необходимо делать поиск слова в некотором множестве слов. Слов может быть от 50 до 1000. Допустим, что слова в множестве отсортированы. Необходимо определить входит искомое слово в данное множество или нет, важна СКОРОСТЬ определения. Подскажите, пожалуйста, как это множество мне лучше представить: использовать один из контейнеров stl, файл (тут плюс, что непосредственно пользователь может пополнять множество) или как-то еще. Повторюсь, главный акцент на скорости работы. Спасибо. |
| Автор: Леопольд 7.9.2011, 12:36 |
| becks, если множество константно (т.е. не надо периодически его менять) то два варианта, 1-ый слегка побыстрее, 2-ой удобнее 1. std::vector, std::sort и std::find std::lower_bound | std::upper_bound(сложность поиска элемента будет O log2n : n размер контейнера) 2. std::set (сложность поиска элемента будет O log2n + xn : x оверхед на доступ к елементу) Чтение из файла и работа с контейнером не исключают друг-друга. Читай файл в контейнер... В любом случае, работать с ОЗУ гораздо быстрее чем с ПЗУ в современных реалиях. |
| Автор: newbee 7.9.2011, 13:11 |
| Еще можешь использовать хеш или одно из сбалансированных бинарных деревьев. |
| Автор: boostcoder 7.9.2011, 13:28 | ||
лучше параллельные алгоритмы из http://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode.html. |
| Автор: Леопольд 7.9.2011, 13:37 | ||
boostcoder, из пушки по воробьям... |
| Автор: boostcoder 7.9.2011, 13:39 |
| Леопольд, не обратил внимание. тогда в любом случае, считывание из файла будет в несколько раз дольше, чем самый левый поиск  |
| Автор: azesmcar 7.9.2011, 14:13 | ||
Не будет, для бинарного поиска одной сортировки массива недостаточно, алгоритм тоже нужно выбирать http://www.cplusplus.com/reference/algorithm/binary_search/  |
| Автор: Леопольд 7.9.2011, 15:51 | ||
azesmcar, если топикстартеру достаточно информации что слово в массиве есть, тогда std::binary_search подойдёт.
P.S. Что то погорячился я по поводу std::find...  |
| Автор: azesmcar 7.9.2011, 15:55 | ||||
Вроде бы ему это и нужно.
|
| Автор: becks 7.9.2011, 16:07 | ||
Да, мне это и нужно, огромное всем спасибо. |
| Автор: xvr 8.9.2011, 13:46 | ||
trie дерево. Съест много памяти, но поиск будет за линейное время от длинны проверяемого слова и не будет зависеть от количества слов в множестве |
| Автор: boostcoder 8.9.2011, 14:05 | ||
это что? гугл выдает всякий бред. |
| Автор: azesmcar 8.9.2011, 14:07 | ||
http://en.wikipedia.org/wiki/Trie |
| Автор: boostcoder 8.9.2011, 14:17 | ||
спасибо. прикольная структура. |
| Автор: fish9370 8.9.2011, 15:02 |
| а как насчет перемешаных таблиц? на мой взгляд для этой задачи это более оптимальное решение.. |
| Автор: xvr 8.9.2011, 15:31 | ||
А это что? (Или у вас так хэш таблицы называются?) |
| Автор: fish9370 8.9.2011, 15:52 | ||
вообще у нас (в университете) это называется таблица с вычисляемым входом, а перемешаная таблица, это ее частный случай.. ну впринципе хеш-таблица, это тоже ее частный случай.. Добавлено через 1 минуту и 54 секунды ну впринципе, да они обе основаны на хеш-функции.. |
| Автор: xvr 8.9.2011, 21:48 | ||
Хеш в данном случае будет эффективен если будет идеальным, т.е. без коллизий. Да и даже без коллизий потребуется как минимум 2 раза обработать входную строку - 1 раз для вычисления хеша, второй раз для посимвольного сравнения с найденным образцом. Trie дерево требует только одного прохода по исходной строке и не дает коллизий. С другой стороны оно требует дополнительных обращений в память (по штуке в каждом узле). Так что подходы приблизительно одинаково эффективны (в идеале) |
| Автор: fish9370 9.9.2011, 10:09 | ||||||
я не до конца понял условие задачи, я думал, что все строки уникальные, а значит и хеш будет уникальным (для этого существуют офигительные хеш-функции, которые используются для поиска процесса в ядре или в астере для поиска строк) так же я предположил, что количество строк будет не более 2000
ну это реализиуется элегантно..
такая хеш таблица, будет работать со скоростью O(1) (плюс-минус разрешение коллизий, но их быть не должно если строки будут уникальными) - так что этот способ быстрее.. |
| Автор: volatile 9.9.2011, 10:44 | ||
Не-а. Строго говоря, какой бы замечательный хеш не был, это не избавляет от возможности коллизий. |
| Автор: xvr 9.9.2011, 12:17 | ||
Вычисление самого хэша от строки потребует по ней пройти как минимум 1 раз, так что скорость работы такая же |
| Автор: fish9370 9.9.2011, 12:20 | ||||
вероятность коллизий мизерная, что ей можно принебречь..
стоило бы проверить.. |