 |
|
Модераторы: Daevaorn |
 
|
|
Что использовать для быстрого поиска? 
| becks |
|
|||
 Бывалый  Профиль Группа: Участник Сообщений: 165 Регистрация: 6.7.2010 Репутация: нет Всего: нет |
Добрый день коллеги, такой вопрос:
Необходимо делать поиск слова в некотором множестве слов. Слов может быть от 50 до 1000. Допустим, что слова в множестве отсортированы. Необходимо определить входит искомое слово в данное множество или нет, важна СКОРОСТЬ определения. Подскажите, пожалуйста, как это множество мне лучше представить: использовать один из контейнеров stl, файл (тут плюс, что непосредственно пользователь может пополнять множество) или как-то еще. Повторюсь, главный акцент на скорости работы. Спасибо. |
|||
|
||||
Загрузка ...
| Леопольд |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
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 оверхед на доступ к елементу) Чтение из файла и работа с контейнером не исключают друг-друга. Читай файл в контейнер... В любом случае, работать с ОЗУ гораздо быстрее чем с ПЗУ в современных реалиях. Это сообщение отредактировал(а) Леопольд - 7.9.2011, 15:55 -------------------- вопросов больше чем ответов |
|||
|
||||
| newbee |
|
|||
 Бревно Профиль Группа: Участник Сообщений: 703 Регистрация: 24.8.2011 Репутация: 4 Всего: 19 |
Еще можешь использовать хеш или одно из сбалансированных бинарных деревьев.
-------------------- You're face to face With man who sold the world |
|||
|
||||
| boostcoder |
|
|||
 pattern`щик Профиль Группа: Завсегдатай Сообщений: 5458 Регистрация: 1.4.2010 Репутация: 49 Всего: 110 |
лучше параллельные алгоритмы из GCC STL extension. |
|||
|
||||
| Леопольд |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
boostcoder, из пушки по воробьям... -------------------- вопросов больше чем ответов |
|||
|
||||
| boostcoder |
|
|||
|
pattern`щик Профиль Группа: Завсегдатай Сообщений: 5458 Регистрация: 1.4.2010 Репутация: 49 Всего: 110 |
Леопольд, не обратил внимание.
тогда в любом случае, считывание из файла будет в несколько раз дольше, чем самый левый поиск  |
|||
|
||||
| azesmcar |
|
|||
 uploading... Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 81 Всего: 211 |
Не будет, для бинарного поиска одной сортировки массива недостаточно, алгоритм тоже нужно выбирать соответствующий  |
|||
|
||||
| Леопольд |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 943 Регистрация: 17.6.2009 Репутация: 10 Всего: 13 |
azesmcar, если топикстартеру достаточно информации что слово в массиве есть, тогда std::binary_search подойдёт.
P.S. Что то погорячился я по поводу std::find...  Это сообщение отредактировал(а) Леопольд - 7.9.2011, 15:54 -------------------- вопросов больше чем ответов |
|||
|
||||
| azesmcar |
|
||||
|
uploading... Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 81 Всего: 211 |
Вроде бы ему это и нужно.
|
||||
|
|||||
| becks |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 165 Регистрация: 6.7.2010 Репутация: нет Всего: нет |
Да, мне это и нужно, огромное всем спасибо. |
|||
|
||||
| xvr |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
trie дерево. Съест много памяти, но поиск будет за линейное время от длинны проверяемого слова и не будет зависеть от количества слов в множестве |
|||
|
||||
| boostcoder |
|
|||
|
pattern`щик Профиль Группа: Завсегдатай Сообщений: 5458 Регистрация: 1.4.2010 Репутация: 49 Всего: 110 |
это что? гугл выдает всякий бред. |
|||
|
||||
| azesmcar |
|
|||
|
uploading... Профиль Группа: Участник Клуба Сообщений: 6291 Регистрация: 12.11.2004 Где: Армения Репутация: 81 Всего: 211 |
http://en.wikipedia.org/wiki/Trie |
|||
|
||||
| boostcoder |
|
|||
|
pattern`щик Профиль Группа: Завсегдатай Сообщений: 5458 Регистрация: 1.4.2010 Репутация: 49 Всего: 110 |
спасибо. прикольная структура. |
|||
|
||||
| fish9370 |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 663 Регистрация: 15.4.2007 Где: Москва Репутация: -1 Всего: 1 |
а как насчет перемешаных таблиц? на мой взгляд для этой задачи это более оптимальное решение..
-------------------- undefined |
|||
|
||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0707 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |