 |
|
Модераторы: 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 |
|||
|
||||
| xvr |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
А это что? (Или у вас так хэш таблицы называются?) |
|||
|
||||
| fish9370 |
|
|||
|
Опытный Профиль Группа: Участник Сообщений: 663 Регистрация: 15.4.2007 Где: Москва Репутация: -1 Всего: 1 |
вообще у нас (в университете) это называется таблица с вычисляемым входом, а перемешаная таблица, это ее частный случай.. ну впринципе хеш-таблица, это тоже ее частный случай.. Добавлено через 1 минуту и 54 секунды ну впринципе, да они обе основаны на хеш-функции.. -------------------- undefined |
|||
|
||||
| xvr |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
Хеш в данном случае будет эффективен если будет идеальным, т.е. без коллизий. Да и даже без коллизий потребуется как минимум 2 раза обработать входную строку - 1 раз для вычисления хеша, второй раз для посимвольного сравнения с найденным образцом. Trie дерево требует только одного прохода по исходной строке и не дает коллизий. С другой стороны оно требует дополнительных обращений в память (по штуке в каждом узле). Так что подходы приблизительно одинаково эффективны (в идеале) |
|||
|
||||
| fish9370 |
|
||||||
|
Опытный Профиль Группа: Участник Сообщений: 663 Регистрация: 15.4.2007 Где: Москва Репутация: -1 Всего: 1 |
я не до конца понял условие задачи, я думал, что все строки уникальные, а значит и хеш будет уникальным (для этого существуют офигительные хеш-функции, которые используются для поиска процесса в ядре или в астере для поиска строк) так же я предположил, что количество строк будет не более 2000
ну это реализиуется элегантно..
такая хеш таблица, будет работать со скоростью O(1) (плюс-минус разрешение коллизий, но их быть не должно если строки будут уникальными) - так что этот способ быстрее.. -------------------- undefined |
||||||
|
|||||||
| volatile |
|
|||
 Эксперт Профиль Группа: Завсегдатай Сообщений: 2107 Регистрация: 7.1.2011 Репутация: 37 Всего: 85 |
Не-а. Строго говоря, какой бы замечательный хеш не был, это не избавляет от возможности коллизий. |
|||
|
||||
| xvr |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 7046 Регистрация: 28.8.2007 Где: Дублин, Ирландия Репутация: 60 Всего: 223 |
Вычисление самого хэша от строки потребует по ней пройти как минимум 1 раз, так что скорость работы такая же |
|||
|
||||
| fish9370 |
|
||||
|
Опытный Профиль Группа: Участник Сообщений: 663 Регистрация: 15.4.2007 Где: Москва Репутация: -1 Всего: 1 |
вероятность коллизий мизерная, что ей можно принебречь..
стоило бы проверить.. -------------------- undefined |
||||
|
|||||
|
|
| Правила форума "С++:Общие вопросы" | |
|
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
[ Время генерации скрипта: 0.0723 ] [ Использовано запросов: 22 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |