這個實驗在電腦裡躺了一段時間了,雖然不是很有價值的實驗,但想說既然做了不如就整理一下放上來吧。
大約兩個月前在 xkcd 上看到有位仁兄挑戰既有的資料結構常識:「假使只查詢而不需要更新資料,使用排序陣列搭配二分搜尋,效能通常會勝過複雜精巧的二元搜尋樹」。這位仁兄很意外的發現,用 std::lower_bound 對排序過的 vector 做二分搜尋比 map 還慢。他提供的程式很快被網友點出兩個錯誤:
- 他使用 rand() 產生 key。由於 map 只會保留獨一無二的 key,因此當資料量超過 rand() 重複週期之後,map 的元素明顯少於 vector。
- 他使用 pair 預設的 operator<。但 pair 預設的 operator< 不只會比較 first,還會比較 second,因此 map 的比較運算比較廉價。
我認為他還有一個非常重要的缺失卻沒有人提起:他完全依序搜尋,但是對資料結構進行測速,順序會影響快取率(想想看,日常應用比較容易出現哪種順序)。 所以我才會做以下的實驗來印證想法。請注意本實驗的重點不在於測速,而是在於指出一般人測速時常忽略的現象,所以不要拿本篇作為選擇編譯器/資料結構的唯一依據。他的程式並不是很好讀,所以我做了改寫並額外增加以下部份:
- 加入隨機搜尋作為依序搜尋的對照,這是本實驗的目的。
- 加入了原生陣列作為 vector 的對照。
- 加入以 string 為 Key 的部份
- 實作了不同版本的二分搜尋。大家都知道二分搜尋有兩種實作方式,第一種是嚴格二分,第二種將等於也分成一類,通常第二種會比第一種少一些比較次數,但複雜度是同等級的。我的第一個二分搜尋直接抄自 GCC 的 std::lower_bound,這是一種嚴格二分搜尋,唯一的差別是將 advance 和 distance 改為直接指標運算。
- 改掉依賴 C++11 的語法,並改寫輸出格式以便導出資料與繪圖自動化。
我在 32 位元 Win7 環境下分別以 GCC 和 VC++ 2008 進行實驗:GCC 的編譯選項是「-O2 -flto -fwhole-program -s」,VC++ 用的是 CMake 自動生成的 Release 組態。篇幅有限,一些實驗中發現的有趣現象就留給有心人去探索。這裡只提一點,在 GCC 下交叉套用演算法時,vector::iterator 效能和原生指標幾乎沒有差別;但是在 VC 下 vector::iterator 慢到了一種非常誇張的地步,不曉得是編譯器還是程式庫實作的問題。(我沒手動關閉 VC 的 checked iterator,但也有一些跡象讓我懷疑編譯器)
以下我讓 vector 套用嚴格二分搜尋,而原生指標採用考慮等號的二分搜尋,請記住在 GCC 下套用相同演算法時兩者幾乎是一樣的。部份實驗的結果如下,在隨機搜尋的情況下陣列明顯比 map 快,不過依序搜尋的情況下 map 有時會快很多,雖然我大概知道這是快取效應造成的,但並沒有繼續深究細部的原因。如果你覺得我的程式碼犯了哪些錯誤也歡迎提出來討論,雖然我最近不是很有空回應。
#include <cstdlib> #include <cstdio> #include <cstring> #include <ctime> #include <algorithm> #include <map> #include <string> #include <vector> using namespace std; //#define USE_STRING_KEY 1 #ifdef USE_STRING_KEY typedef string Key; #else typedef int Key; #endif typedef pair<Key, unsigned> Pair; typedef map<Key, unsigned> Map; typedef vector<Pair> Vector; const int TEST_COUNT = 50000000; struct Less1st { inline bool operator()(const Pair& lhs, const Pair& rhs) const { return lhs.first < rhs.first; } }; struct TriComp1st { inline int operator()(const pair<string, unsigned>& lhs, const pair<string, unsigned>& rhs) const { return strcmp(lhs.first.c_str(), rhs.first.c_str()); } inline int operator()(const pair<int, unsigned>& lhs, const pair<int, unsigned>& rhs) const { return lhs.first - rhs.first; } }; template <class RandIter, class T, class Comp> RandIter BinSearch1(RandIter first, RandIter last, const T& target, Comp cmp) { typedef typename iterator_traits<RandIter>::difference_type Diff; Diff len = last - first; while (len > 0) { Diff half = len >> 1; RandIter mid = first + half; if (cmp(*mid, target)) { first = mid; ++first; len = len - half - 1; } else { len = half; } } return (first != last && first->first == target.first)? first : last; } template <class RandIter, class T, class TriComp> RandIter BinSearch2(RandIter first, RandIter last, const T& target, TriComp cmp) { RandIter notFound = last, mid; while (first <= last) { mid = first + ((last - first) >> 1); int r = cmp(*mid, target); if (r < 0) { first = mid + 1; } else if (r > 0) { last = mid - 1; } else { return mid; } } return notFound; } inline Pair* RawFind(Pair* first, Pair* last, const Pair& target) { return BinSearch2(first, last, target, TriComp1st()); } inline Vector::const_iterator VecFind(const Vector& v, const Pair& target) { // return BinSearch2(v.begin(), v.end(), target, Less1st()); Vector::const_iterator it = lower_bound(v.begin(), v.end(), target, Less1st()); return (it != v.end() && it->first == target.first)? it : v.end(); } inline Map::const_iterator MapFind(const Map& m, const Pair& target) { return m.find(target.first); } volatile unsigned nocheat; clock_t TestRaw(const Vector& data) { Pair* raw = new Pair[data.size()]; copy(data.begin(), data.end(), raw); sort(raw, raw + data.size(), Less1st()); nocheat = 0; clock_t beg = clock(), end; for (int i = 0; i < TEST_COUNT; ++i) { const Pair& target = data[i % data.size()]; Pair* found = RawFind(raw, raw + data.size(), target); nocheat += found->second; } end = clock(); delete[] raw; fprintf(stderr, "%u\n", nocheat); return end-beg; } clock_t TestVec(const Vector& data) { typedef Vector::const_iterator citerator; Vector v(data.begin(), data.end()); sort(v.begin(), v.end(), Less1st()); nocheat = 0; clock_t beg = clock(), end; for (int i = 0; i < TEST_COUNT; ++i) { const Pair& target = data[i % data.size()]; citerator found = VecFind(v, target); nocheat += found->second; } end = clock(); fprintf(stderr, "%u\n", nocheat); return end-beg; } clock_t TestMap(const Vector& data) { typedef Map::const_iterator citerator; Map m(data.begin(), data.end()); nocheat = 0; clock_t beg = clock(), end; for (int i = 0; i < TEST_COUNT; ++i) { const Pair& target = data[i % data.size()]; citerator found = MapFind(m, target); nocheat += found->second; } end = clock(); fprintf(stderr, "%u\n", nocheat); return end-beg; } int main(int ac, char* av[]) { const int dataSize = (ac > 1)? atoi(av[1]) : 1000; srand(8165); Vector data(dataSize); for (unsigned i = 0; i < data.size(); ++i) { #ifdef USE_STRING_KEY unsigned j; for (j = i; j > 9; j /= 10) { data[i].first.push_back('0' + j % 10); } data[i].first.push_back('0' + j); #else data[i].first = i; #endif data[i].second = rand(); } // random_shuffle(data.begin(), data.end()); clock_t r = TestRaw(data); clock_t v = TestVec(data); clock_t m = TestMap(data); printf("%8u %8u %8u %8u\n", dataSize, r, v, m); return 0; }