Похожих стандартных задач поиска уйма. Например, MySQL C API позволяет получить значение поля "рекордсет"-а по индексу (что в 90% практических задач достаточно), типа:
std::string val = get_StringField(size_t_field_index);
Иногда, правда, софтверные архитекторы просят, чтобы можно было получать полe "рекордсет"-а по его имени, типа:
std::string val = get_StringField("some_field_name");
При этом, конечно, интересует лексикографическое сравнение "some_field_name", и число полей, как правило, не велико, до 20.
Нехитрое применение google машины показывает предложения использовать от std::map или бинарного поиска по сорированному std::vector до хеширования.
Кстати, использование хеш таблиц есть в весима профессиональном коде, см., например, C# исходники MySQL .NET Connector 1.0.
Другое нехитрое сопоставление скорости получения индесов 15 полей рекордсета со случаиными именами по "значениям" этих полей с использованием прямого просмотра, бинарного поиска по сортированному std::vector, поиска елемента по ключу std::map
показывает, что:
vector - 30-40 ms
linear - 40-50 ms
map - 60-70 ms
Т.е при небольшом числе элементов ("полей") прямой просмотр - не хуже, а лучше c практической точки зрения с учётом накладных расходов.
Те результаты что выше не учитывают время, необходимое для создания std::vector, std::map, а в случае std::vector ещё и его сортировку. Т.е. это только затраты собственно на поиск. Поскольку в реальной программе это надо делать (создать std::vector или std::map, а в случае std::vector ещё сортировать его) , то результаты будут:
linear - 40-50 ms
vector - 110-150 ms
map - 170-210 ms
Может, я чего-то упускаю? Меня интересует мнение практиков. В схожих задачах вы делаете прямой просмотр? Похоже прямой просмотр - вне конкуренции.
|