unordered_multimap :: equal_range慢

我希望unordered_multimap :: equal_range是在平均的常複雜，但以下情況不與正線性增長預期：unordered_multimap :: equal_range慢

#include <iostream> 
#include <tr1/unordered_map> 
#include <cstdlib> 

using namespace std::tr1; 
using namespace std; 

int main(){ 
     int n; 
     cin >> n; 
     unordered_map<int, int> um; 
     for(int i=0; i<n; ++i){ 
       um.insert(make_pair(i%100000, i)); 
       pair<unordered_map<int, int>::iterator,unordered_map<int,int>::iterator > t = um.equal_range(i); 
     } 
}

$ g++ testbr.cpp 
$ time echo 10000 | ./a.out 

real 0m0.065s 
user 0m0.060s 
sys  0m0.003s 
$ time echo 100000 | ./a.out 

real 0m4.492s 
user 0m4.490s 
sys  0m0.003s

是有辦法解決這個問題？

編輯： 沒有equal_range它如預期完美縮放。
如果我插入所有具有相同鍵0的元素（並且總是調用equal_range（0）），它會按預期縮放，即使助推文檔聲明等於範圍的平均值爲O（count（k））...？

來源

2012-07-17 user1531083

將'equal_range'行註釋掉的時間。這可能是花費時間的「插入」。一般來說，要弄清爲什麼散列表行爲不當，查看'bucket_count'和每個存儲桶中元素的數量 - 你希望這個例子是均勻分佈的，但是我想你可能碰到了'max_bucket_count'。我希望不會。 – 2012-07-17 09:45:30

您應該始終分析一個優化版本。如果用'-O3'編譯，你會得到什麼？ – 2012-07-17 10:01:30

與-O3 100.000比10.000慢30倍 - 所以它更好但不好看 – user1531083 2012-07-17 10:10:58

這似乎是libstdC++中的一個錯誤，我找不到任何地方的錯誤報告，但#include <unordered_map>和編譯-std=c++11我得到預期的行爲。

來源

2013-09-02 10:04:56 user1531083

這不是規模O(n)，但O(n * n)（你打電話std::equal_rangen次）！

將std::equal_range移出內部循環。

來源

2012-07-17 09:30:55 orlp

根據boost文檔equal_range應該是平均數（k），在我的情況下是1！奇怪的是，如果我在同一個鍵中插入所有元素，速度會變得更快，因此count（k）== n – user1531083 2012-07-17 09:36:16

計數不會保持1.總運行時間約爲。 '1 + 2 + 3 + ... + N'。 – orlp 2012-07-17 09:40:24

@nightcracker：'k'是相同範圍的大小，即容器中具有該鍵的元素的數量。關鍵是'i％100000'，這個例子中'i'等於'i'，因爲'i 2012-07-17 09:49:38

unordered_multimap :: equal_range慢

回答

相關問題