快速查找整數索引值使用排序的整數數組鍵

我正在尋找最快的解決方案來查找整數值使用排序的整數數組鍵。快速查找整數索引值使用排序的整數數組鍵

鍵是整型數組，固定長度爲3，每個數組都被排序。
該值是一個整數。

我的數據保證只有一個或兩個排序的數組具有相同的內容。每個數組都有一個唯一索引。我試圖找到匹配的數組對數組。

我的想法是使用字典（我在原型C＃和將移動到C++）

對於每個陣列，我會看在字典，看看它是否已經存在。如果是這樣，我將它從字典中刪除。如果我沒有在字典中找到它，那麼它不是單例就是它是匹配對中的第一個，所以我將它添加到字典中。

我的問題是這樣的 - 給予數據非常具體的保證，什麼是最好的容器 - 考慮到速度是我最關心的問題？此外，任何關於適當（快速）哈希函數或排序整數數組比較函數的建議將不勝感激。

2013-04-12 scotsman60

如果你的代碼最終需要C++，不要浪費時間在C＃上。你在C＃中發現的工作很快，並不意味着你在C++中得到了相同的結果。 – Kelmen

CRC32是一種無密碼保證的快速哈希函數。此外，除非您希望獲得大量具有相同第一個X條目的數組，否則您只能散列第一個X條目以節省時間。 – Patashu

當你到C++，遷移到這個

這是我碰到的最快速的HashMap實現之一。同時，對於C＃來說，等價物會是這樣的：http://msdn.microsoft.com/en-us/library/xfhwa508.aspx我想有更快的字典實現可用，但由於C＃不是最終的容器，它應該做得很好。

您可能想要考慮在項目中包含berkeleydb。它非常快速並且可以在數據集增長時管理存儲。它也支持各種平臺。

2013-04-12 04:12:42

回答