爲什麼在我的應用程序中查找stl :: map比stl :: vector慢？

我有點驚訝，特別是在讀this後。爲什麼在我的應用程序中查找stl :: map比stl :: vector慢？

我用

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; 
}

爲模板函數來獲取特定元素的索引，我矢量respectivly名單。

元素是唯一指向對象的指針，其中我想檢索索引。

然後我用這個模板在for循環像

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

雖然我收集的信息的所有位建議使用的地圖，地圖上實現幅度比較慢幾個數量級：使用57毫秒使用地圖比較70000ms的矢量變體。

這裏有東西被切斷了，但我不知道是什麼。你做？

發展plattform是MS VS 2008標準版SP1，Windows XP上

來源

2010-07-07 sum1stolemyname

既然你是按值傳遞它們，你應對在每次vector和map叫你正在。我認爲這使得結果幾乎沒有意義。

將它們作爲引用或const引用傳遞並再次運行測試。

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

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

來源

2010-07-07 13:47:53 shoosh

謝謝。這樣可以降低查找成本在這兩種情況下幾乎沒有什麼（我的測試用例爲6毫秒）。現在這是我的一個非常愚蠢的錯誤;） – sum1stolemyname 2010-07-08 05:46:58

注意，因爲你的代碼寫在這裏，您將同時傳遞載體和值映射，即你正在重建的每一個新副本每次通話。這顯然壓倒了搜索的時間。

嘗試：

template <class T> 
int GetPosition(const map<T, int> &mMap, T element)

來源

2010-07-07 13:47:09

除了使用引用來避免其他答案提及副本，這裏還有算法複雜性的差異。

查找大小爲n的（未排序）向量具有O（n）時間複雜度，而映射上的相同操作具有O（log n）時間複雜度。

簡單地說，這意味着查找向量中的對象需要時間K1 * n，而地圖需要K2 * log（n）時間，其中K1和K2是一些常量，這些常量取決於矢量和地圖。

這是在實踐中更快地取決於你的容器的大小和常數是什麼（我認爲這是肯定地說K1will更快。

事情是這樣的高速緩存一致性也將開始發揮作用，在這裏，如果你的容器（對於緩存，常量也不會真的是恆定的，但這是另一回事......）

來源

2010-07-07 23:13:50 Staffan

我建議你拿起一本介紹性的計算機科學書來學習Big O符號，基本數據結構和算法等東西。最大的性能優勢來自選擇正確的算法和數據結構;如果你對計算機科學的基礎知識掌握得不好，你註定要寫出次優的代碼。 – Staffan 2010-07-07 23:19:57

在排序列表上查找的是O（lg N）。在地圖上的查找應該是O（1），而不是O（lg N），儘管如果你的散列函數引起衝突它會降低。 – 2010-07-07 23:38:54

對於*散列*地圖查找時間是攤銷O（1），是的。對於std :: map，它是O（log n）。見例如這http://www.sgi.com/tech/stl/SortedAssociativeContainer.html – Staffan 2010-07-07 23:51:20

爲什麼在我的應用程序中查找stl :: map比stl :: vector慢？

回答

相關問題