Почему поиск в stl :: map медленнее, чем в stl :: vector в моем приложении? - PullRequest
Новая
       4

Почему поиск в stl :: map медленнее, чем в stl :: vector в моем приложении?

1 голос
/ 07 июля 2010

Я немного удивлен, особенно после прочтения this .

Я использую 

template <class T>
int GetPosition(vector<T> mVec, T element)
{
    return find(mVec.begin(), mVec.end(), element) - mVec.begin();
}

и 

template <class T>
int GetPosition(map<T, int> mMap, T element)
{
    return mMap.find(element)->second;
}

в качестве шаблонных функцийчтобы получить индекс определенного элемента в моем списке векторов соответственно.

Элементы - это уникальные указатели на объекты, из которых я хочу получить индекс.

Затем я использую этот шаблон вцикл for подобен 

for(int i = 0; i < myCount; i++)
{
  index = GetPosition(myVector, elements[i]) //or GetPosition(myMap, elements[i])
}

В то время как все биты информации, которые я собрал, предлагали использовать карту, реализация карты на несколько порядков медленнее: 57 мс с использованием векторного варианта при сравнении 70000 мс с использованиемкарта.

Здесь что-то сильно изуродовано, но я не знаю что.А вы?

Платформа для разработки - MS VS 2008 Standard sp1, для Windows XP

Ответы [ 3 ]

3 голосов
/ 07 июля 2010

Поскольку вы передаете их по значению, вы копируете vector и map в каждом звонке, который вы делаете.Я бы сказал, что это делает результаты в значительной степени бессмысленными.

Передайте их как справочные или константные ссылки и повторите тест.

3 голосов
/ 07 июля 2010

Обратите внимание: поскольку ваш код написан здесь, вы передаете и вектор, и карту по значению, т. Е. Вы перестраиваете новые копии каждого при каждом вызове.Это явно подавляющее время поиска.

try: 

template <class T> 
int GetPosition(const map<T, int> &mMap, T element)
1 голос
/ 08 июля 2010

Помимо использования ссылок, чтобы избежать копий, как упоминалось в других ответах, здесь также есть разница в алгоритмической сложности.

Поиск в (несортированном) векторе размера n имеет сложность времени O (n), тогда как та же операция на карте имеет сложность времени O (log n).

Проще говоря, это означает, что поиск объекта в вашем векторе занимает время K1 * n, тогда как для карты требуется K2 * log (n) время, где K1 и K2 - некоторые константы, которые зависят от реализации вектора и карта.

То, что быстрее на практике, зависит от размера вашего контейнера и от того, какие константы (я думаю, можно с уверенностью сказать, что K1 будет быстрее.

Здесь также будут задействованы такие вещи, как когерентность кэша, если ваш контейнер маленький, все будет в кэше для вектора, но не для карты. (С кешем константы тоже не будут постоянными, но это уже другая история ...)

...