7
我有一個關於C++中數百個唯一字符串的列表，我需要檢查列表中是否存在一個值，但最好快閃。快速搜索C++中的字符串排序列表
我currenly與使用的std ::串一的hash_set（因爲我無法得到它與爲const char *工作），像這樣：
stdext::hash_set<const std::string> _items;
_items.insert("LONG_NAME_A_WITH_SOMETHING");
_items.insert("LONG_NAME_A_WITH_SOMETHING_ELSE");
_items.insert("SHORTER_NAME");
_items.insert("SHORTER_NAME_SPECIAL");
stdext::hash_set<const std::string>::const_iterator it = _items.find("SHORTER_NAME"));
if(it != _items.end()) {
std::cout << "item exists" << std::endl;
}
有沒有人有一個好主意，以便更快搜索方法沒有建立一個完整的散列表我自己？
該列表是不會更改的字符串的固定列表。它包含一個受某些bug影響的元素名稱列表，並且應該在用新版本打開時即時修復。
我在使用Aho-Corasick之前就已經構建了哈希表，但是我不太願意添加太多的複雜性。
我很驚訝的答案的數量。最後，我測試了幾種方法，結果使用了kirkus和Rob K.的答案。我之前嘗試過二分搜索，但我想我有一個小錯誤實現它（有多難......）。
結果令人震驚...我以爲我有一個快速實現使用hash_set ......好吧，結果我沒有。下面是一些統計數據（和最終碼）：
現有5個按鍵和一個不存在的鍵的隨機查找，50.000倍
我原來的算法，平均需18,62秒
平均檢索時間平均爲2,49秒
二分查找平均需要0,92秒。
使用gperf生成的完美hashtable進行搜索，平均需要0,51秒。
這是我現在使用的代碼：
bool searchWithBinaryLookup(const std::string& strKey) {
static const char arrItems[][NUM_ITEMS] = { /* list of items */ };
/* Binary lookup */
int low, mid, high;
low = 0;
high = NUM_ITEMS;
while(low < high) {
mid = (low + high)/2;
if(arrAffectedSymbols[mid] > strKey) {
high = mid - 1;
}
else if(arrAffectedSymbols[mid] < strKey) {
low = mid + 1;
}
else {
return true;
}
}
return false;
}
注：這是微軟VC++所以我不使用從SGI在std ::的hash_set。
我做了一些測試今天上午的gperf使用作爲VardhanDotNet建議，這是相當快一點確實如此。
嗯...我想我目前的實現速度夠快，但是我會給gperf一個嘗試，只是爲了體驗和比較材料。 – Huppie 2009-01-27 07:30:51