Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
[C++] У Кнута есть довольно подробное разжевывание преимуществ и недостатков алгоритмов. 22.05.07 11:19 Число просмотров: 3024
Автор: amirul <Serge> Статус: The Elderman
|
> Нехитрое применение google машины показывает предложения
> использовать от std::map или бинарного поиска по
> сорированному std::vector до хеширования.
Если бы набор данных был большим, то я бы их хранил в векторе, а к нему прицепил бы std::map или std::hash_map из boost::shared_ptr-ов (или boost::intrusive_ptr-ов) на элементы этого вектора.
> Кстати, использование хеш таблиц есть в весима
> профессиональном коде, см., например, C# исходники MySQL
> .NET Connector 1.0.
Ну к примеру майкрософтовский tcpip.sys использует хэш таблицы для связывания пар ip:port со внутренними структурами. Тоже далеко не новички писали :-)
Вообще хэш-таблицы - очень удобная штука. В своем классе задач, разумеется :-)
> Т.е при небольшом числе элементов ("полей") прямой просмотр
> - не хуже, а лучше 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
> Может, я чего-то упускаю? Меня интересует мнение практиков.
> В схожих задачах вы делаете прямой просмотр? Похоже прямой
> просмотр - вне конкуренции.
На малых размерах данных линейный поиск действительно заслуживает внимания. В данной конкретной задаче на мой взгляд все зависит от того, можно ли отнести сортировку вектора к предвычислениям (то есть является ли тип доступа write once read many) или нет. Если нужна еще бОльшая скорость, то на таких объемах данных очень неплохо должна проявить себя хэш-таблица.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
