由於性能原因，替代stdext :: hash_map

我正在開發一個高性能應用程序，其中所有調用都必須是合理的。我有一張在每次交易開始時使用過一次的地圖，用於查找我想改進的地方。地圖在啓動時加載，之後不會更改。由於性能原因，替代stdext :: hash_map

下圖中的關鍵字是一個std :: string，但如果需要它可以將其更改爲一個char數組。 C或C++作爲解決方案很好。

typedef stdext::hash_map<std:string, int> symbols_t;

有誰知道任何其他解決方案，可以消除查找或更快？

非常感謝您的幫助。

編輯的其他信息：
1. hash_map當前有350,000個元素。
2.每個鍵值通常在4到10個字符之間。
3.信息從第三方API的回調中收到。在進行地圖查找時，回調被賦予一個用作鍵值的符號。該軟件的其餘部分是從映射查找返回的int驅動的。

感謝：謝謝大家的意見。你給了我一些探索的途徑。我一定會嘗試一下。我很感激幫助。

來源

2010-09-22 skimobear

我非常懷疑，如果你用'char *'替換'std :: string'，整體性能會大大不同。但是，這肯定會使代碼更不易維護。 – ereOn 2010-09-22 11:59:02

哈希映射是O（1），因此查找時間僅取決於計算哈希所需的時間。你看過嗎？ – sbi 2010-09-22 12:19:35

我在想，這是你代碼中最大的瓶頸嗎？聞起來不成熟的優化。 – ybungalobill 2010-09-22 12:29:35

我想說我們缺乏這方面的信息來可靠地告訴你該怎麼做。

您可能希望更具體地瞭解查找內容以及函數的總體算法成本。

如果你用醜陋的黑客弄亂了代碼，在算法成本爲O(n²)的函數中贏得1個恆定的微秒，那麼你在錯誤的問題上浪費你的時間。

沒有額外的細節，我們無法確定。

來源

2010-09-22 12:03:56 ereOn

我添加了一些額外的信息。希望它有幫助，這是足夠的:) – skimobear 2010-09-22 12:20:47

手動編碼更適合您的數據的哈希映射。

簡單的哈希函數是不夠好
使用稀疏C-數組，它是足夠大的沒有衝突的數據
確保所有來電都被內聯
確保你永遠不會複製或轉換字符串
編寫代碼以生成此C數組的C源代碼。這是怎麼回事的樣子（用0表示無輸入）：
```
int symbols[] = { 0,0,0,0,0,0,5,0,0,0,0,0,3,0,0,0,0,0,0,2 /* etc */ }; 
```
你寫的代碼可以搜索那裏有你的數據沒有衝突的哈希函數。也許它是像符號的前兩個字符（或前4個）那樣簡單的int。如果你不關心空間，你不需要爲所有可能的數據做一個完美的哈希，而只需要一個對所有數據來說都很完美的快速哈希。

的數組索引是simple_hash(string& s)

請記住，如果你改變了符號，您可能需要重寫哈希，當然需要重新生成表。

編輯：根據@火焰的答案 - 在＃5的代碼是爲你寫的，被稱爲gperf

來源

2010-09-22 12:09:06

如果你真的需要鍵入上串一的hash_map，那麼你可以嘗試定製散列函數。如果你的字符串在前四個字符中都是唯一的，那就編寫一個自定義的散列函數，它只能查看字符串中前四個字符，然後使用hash_map。這裏有一個例子：

struct CustomStringHash: std::unary_function<std::string, size_t> 
{ 
    size_t operator()(const std::string & s) const 
    { 
     switch (s.size()) 
     { 
       case 0: 
        return 0; 
       case 1: 
        return s[0] + 1; 
       case 2: 
        return (s[0] << 8) + s[1]; 
       default: //3 or more chars long, plus a terminating null 
        return *reinterpret_cast<const uint32_t *>(s.c_str()); 
     } 
    }

如果你的字符串的字符8-12平均，和前四個字符大多是唯一的，那麼自定義哈希函數可以很顯著加快查找。

來源

2010-09-22 12:19:57 Doug

我們如何建議您如何消除您的查找，因爲您不告訴我們您查找什麼或爲什麼？我們需要更多的算法細節。

至於性能，是否使用hash_map取決於一些複雜性。 HashMap有（如果你有一個很好的實現，現實）O（1）查找，插入。但是不斷的開銷可能會很高。如果你有很少的條目，你可能會在這裏受到影響，並可能從std :: map中受益。如果頻繁訪問映射的許多不同元素並且可能會考慮某種排序數組，則可能還會遇到緩存一致性問題。

來源

2010-09-22 12:23:23 Puppy

上面添加了一些額外的信息。請讓我知道，如果它不夠。 thx – skimobear 2010-09-22 12:30:09

這個映射是完全不變的，還是程序調用之間的變化？對於常量散列（編譯時已知），有gperf程序，它可以生成快速且有保證的O（1）查找表。

此外，如果您告訴我們爲什麼以及如何確切地圖查找會減慢代碼，它可能有助於理解您的問題。

來源

2010-09-22 12:55:14 blaze

hash_map的內容每天都在變化。它每天早上從數據庫中取出。這聽起來很有趣，我會看看:) – skimobear 2010-09-22 13:06:10

gperf生成與您的數據硬編碼的C++源文件。使用gperf從數據庫創建一個動態庫，每天早上卸載和加載。 – 2010-09-22 14:51:34

散列表通常足夠快O（1），我們不能告訴你是否可以在不知道應用程序的整體結構的情況下襬脫散列表。這可能是不可能的。

我不知道如何實施stdext::hash_map<std::string,T>，但prefix tree是可能的更好的解決方案。它相當於一個具有完美散列函數的散列表。

 s 
     | 
     t 
    / \ 
    o  a 
    |  | 
(p,42) r 
     | 
     (t,69)

它會給你相應的你在O（1）最大10次迭代（字符串的最大長度）的字符串值，將最大限度地減少存儲密鑰的空間成本。

來源

2010-09-22 13:18:34 log0

以下是有關的hash_map，其中一個簡易替換提出的表現的文章，應該執行好得多：

http://www.codeproject.com/KB/cross-platform/BenchmarkCppVsDotNet.aspx

經歷了std_ext :: PERFO的hash_map當超過25000個元素時，這些元素的表現並不理想，隨着元素數量的增加查找速度變慢。更改爲boost :: unordered_map解決了問題。

來源

2011-07-05 11:28:57

感謝您的信息！ – skimobear 2011-07-09 13:10:03

由於性能原因，替代stdext :: hash_map

回答

相關問題