| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Stl: нужен контейнер для быстрого поиска по имени |
| Автор: Alca 7.5.2009, 10:21 |
| Stl: нужен контейнер для быстрого поиска по имени? map? |
| Автор: azesmcar 7.5.2009, 10:29 | ||
map обеспечивает поиск логаритмической сложности. В принципе да - ассоциативный контейнер (либо отсортированный обычный контейнер - даст возможность применить бинарный поиск). Добавлено через 2 минуты и 52 секунды В принципе можно немного ускорить саму операцию сравнения - хранить вместо имени - числовой хеш. Сравнение чисел быстрее чем сравнение строк. Все зависит от задачи. |
| Автор: Lazin 7.5.2009, 10:35 |
если не нужно получать элементы в определенном порядке, а нужно только быстро искать их по имени, то лучше использовать hash_map  |
| Автор: Alca 7.5.2009, 10:36 | ||||
У меня в файле храняться данные о пользователях:
надо организовать быстрый поиск по имени пользователя. |
| Автор: azesmcar 7.5.2009, 10:39 | ||
| Alca Думаю тут можно применить хеш имя пользователя не такое длинное чтобы беспокоится о коллизиях.если нестандартные решения подходят
если нет - хешируйте имя пользователя сами. http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 |
| Автор: jonie 7.5.2009, 11:10 |
| если известны данные, что имя может начинаться с буквы из определенного множества, то можно сделать массив map-ов, нечто вроде vector<map<string>> , где индексом в vector будет первая буква имени. Т.о. мы существенно уменьшим количество данных в отдельной карте и увеличим скорость, в ущерб, конечно, памяти. Аналогично можно делать vector<vector<.....<map>>...> .... - главное фантазия. |
| Автор: Static 7.5.2009, 12:01 |
| Мне кажется, что при большом количестве имен при таком подходе получится кака, т.к. не получится равномерно распределить все имена. Они имеют подлую особенность начинаться с одинаковых букв. Может и не получиться "существенно уменьшить количество данных в одной карте". Или я неправ? |
| Автор: Alca 7.5.2009, 12:11 |
| Кол-во строк в файле порядка 1000 -1500. |
| Автор: baldina 7.5.2009, 12:24 | ||
двоичный поиск даст максимум 10-11 сравнений. это довольно быстро. думаю отсортированный массив вполне подойдет |
| Автор: Lazin 7.5.2009, 12:32 | ||
поиск в map - столько-же, в hash_map - в зависимости от количества коллизий |
| Автор: Void 7.5.2009, 12:49 | ||
Получилось префиксное дерево (trie). Дальше фантазия может работать в сторону Patricia и ternary search tree. Впрочем, не думаю, что топикстартеру при такой постановке задачи нужно что-то кроме хэш-таблицы. |
| Автор: mrbrooks 7.5.2009, 12:54 | ||
хм. может заюзать простенькую БД. Что - то пихать такое количество инфы в контейнер, имхо, не айс. |
| Автор: Alca 7.5.2009, 12:57 | ||
Типа эксесса? |
| Автор: azesmcar 7.5.2009, 13:02 | ||||
для 1000-1500 записей? там мап и хэш таблица особой разницы не дадут. Там порядке 10 сравнений, для подсчета хэша потеряем больше чем получим прироста при поиске на мой взгляд..хотя надо проверить, но по любому отходить от стандарта ради пары десятка милисекунд думаю не стоит. Добавлено @ 13:04
почему? ну пусть каждая структура в среднем ..ну пусть будет 100 байт. Пусть будет 2000 записей, 2000*100=20000, делим на 1024 получаем где-то 20 килобайт..учитывая некоторые затраты памяти требуемые ассоциативными контейнерами, пусть будет 25 килобайт, не больше..это что, так страшно? на мой взгляд не очень  |
| Автор: baldina 7.5.2009, 13:19 | ||
| задача мелкая, изобретений не стоит. Alca, тестирование уже показало, что требуется оптимизация? если нет - возьми простейшую реализацию. Lazin,
не совсем. во-первых это не идеально сбаласированные деревья, во вторых там больше накладные расходы на одну проверку. да и памяти больше требует. |
| Автор: azesmcar 7.5.2009, 13:28 | ||
Речь по видимому шла о сложности поиска. Они оба имеют логаритмическую сложность. |
| Автор: Alca 7.5.2009, 14:34 |
| Всем спасибо. |
