高效地初始化unordered_map整數對的大數據集

Question

我有一個龐大的數組（ParticleId[]）唯一整數（代表粒子ID）以隨機順序存儲在內存中。我需要構建一個哈希表來將每個ID映射到它在數組內的位置，即從ID到索引。 ID不一定是連續的整數，所以一個簡單的查找數組不是一個好的解決方案。

我目前使用C++ 11的unordered_map容器來實現這一點。地圖初始化用一個循環：

unordered_map <ParticleId_t, ParticleIndex_t> ParticleHash; 
ParticleHash.rehash(NumberOfParticles); 
ParticleHash.reserve(NumberOfParticles); 
for(ParticleIndex_t i=0;i<NumberOfParticles;i++) 
    ParticleHash[ParticleId[i]]=i; 

的ParticleId_t和ParticleIndex_t只是的typedef-ED整數。 NumberOfParticles可能很大（例如，1e9）。就散列表而言，ParticleId[]數組和NumberOfParticles是const。

目前需要相當多的時間來構建如上所述的unordered_map。我的問題是：

1. 是unordered_map這個問題的最佳選擇？
   • 會map會更快初始化，雖然它可能不是在查找效率？
2. 是否可以加快初始化？
   • 使用ParticleHash.insert()比使用ParticleHash[]=快嗎？或任何其他功能？
   • 鑑於我的密鑰已知爲獨特的整數，有沒有一種方法來優化地圖以及插入？

我正在考慮將英特爾concurrent_unordered_map並行它。但是，這會引起對英特爾TBB庫的依賴，如果可能，我希望避免這種情況。有使用本地STL容器的簡單解決方案嗎？

更新：

現在我已經恢復到一個普通的分類索引表，並依靠bsearch進行查找。至少該表的初始化現在快20倍，並且可以很容易地並行化。

Answer 1

我不認爲有很多你可以用這個做，但這裏有幾件事要嘗試。

首先，由於您打電話給realloc，您無需致電rehash。

insert可能比自operator[]operator[]快將調用insert的元素添加到使用默認值的地圖，那麼你的價值分配給新插入的元素，但優化也許能消除額外的工作。

只是因爲鍵是唯一的，這些鍵的哈希值可能不會是因爲我不認爲語言規範要求整數散列返回該整數（描述散列模板的部分不無論如何說）。

'map'的初始化可能會比較慢，因爲當你插入東西時，它必須不斷重新平衡樹，查找會更慢。如果您的ParticleID矢量可以重新排列，則可以使用map的一種替代方法，即對矢量進行排序，然後執行binary_search以查找ID的位置並計算索引。但它的性能與map類似，需要重新排列矢量。

如果您決定嘗試concurrent_unordered_map由於線程之間的所有內存爭用，在3或4個線程之後您可能看不到很多改進。

Answer 2

看來構建查找表的應用程序似乎是內存綁定，而不是cpu綁定。這可能可以通過分析應用程序的原型來驗證。這個答案的其餘部分假定這是真實的。

構建查找表的過程是對輸入數據進行全局視圖，這可能會導致大量交換內存到/從磁盤進/出。

如果是這樣，該解決方案是一種替代算法，一次處理較小的內存塊。 假設有一百萬個整數。當前進程可能會在此時插入哈希表的低端，接近1，並且在下一時刻它可能插入到接近100萬的高端。這導致了很多交換。

另一種方法是通過一次處理較小的數據塊來避免交換。我們可以從桶/基類中借鑑想法。在這種方法中，構建查找表的步驟將被排序步驟所取代。桶/基數排序應該在線性時間內運行。數據集中所有整數都是唯一的這一事實是使用這些排序算法的另一個原因。 如果可以組合線性時間排序和交換最小化，那可能會提高性能。

Answer 3

鑑於「以隨機順序存儲的大量唯一整數」 - 是否有任何事情取決於該隨機順序？如果不是，只需對原始數組中的唯一整數進行排序，並將唯一整數映射到索引，則可以在數組中執行std::lower_bound。

如果需要保留巨大數組的前置順序，但是在該數組填充後（如說明性代碼所做的那樣）將索引構建爲一次性的步驟，則可以創建它們基於指向的元素（您需要定製的指向值的<比較）的ParticleId*和std::sort類似的巨大數組;之後您可以使用std::lower_bound與<進行比較，以便快速找到特定ParticleId的巨大陣列中的索引。

上述連續陣列方法在緩存友好的方式中使用連續內存，在性能和內存使用方面獲益匪淺。

只有當您有大量新的ParticleId進入或在您需要搜索時才被刪除，您需要考慮std::unordered_map。