將散列表映射到磁盤上的最快方法

我有一個Map<byte[], Element>，我想對它進行排序並將其寫入磁盤，以便我有一個文件，其中包含按照Guava的UnsignedBytes.lexicographicalComparator鍵排序的所有元素。將散列表映射到磁盤上的最快方法

我在做什麼現在的問題是：

HashMap<byte[], Element> memory; 

// ... code creating and populating memory ... 

TreeMap<byte[], Element> sortedMap = new TreeMap<byte[], Element>(UnsignedBytes.lexicographicalComparator()); 
sortedMap.putAll(memory.getMap()); 

MyWriter writer = new MyWriter("myfile.dat"); 
for (Element element: sortedMap.values()) 
    writer.write(element); 
writer.close();

它可能很難作出排序快（O（nlogn）），問題是我是否能改善排序列表的導航。理想情況下，我將排序爲ArrayList而不是TreeMap，以便迭代它會非常快。

我想過把HashMap放入一個ArrayList和Collections.sort()它，但這需要比實際解決方案更多的複製。

任何想法？

編輯：

我在這裏添加我的測試與ArrayList這是快兩倍，但我相信它使用更多的內存。也許對這個假設有些評論？

// ArrayList-based implementation 2x faster 
ArrayList<Element> sorted = new ArrayList<Element>(memory.size()); 
sorted.addAll(memory.values()); 

final Comparator<byte[]> lexic = UnsignedBytes.lexicographicalComparator(); 

Collections.sort(sorted, new Comparator<Element>(){ 
    public int compare(Element arg0, Element arg1) { 
     return lexic.compare(arg0.getKey(), arg1.getKey()); 
    } 
}); 
MyWriter writer = new MyWriter(filename); 

for (Element element: sorted) 
    writer.write(element); 
writer.close();

來源

2011-05-16 marcorossi

您需要改進的主要問題是寫入磁盤。這比你做的任何事都要慢100倍。我會用分析器來檢查你在哪裏花時間。 – 2011-05-16 17:53:51

這裏幾乎沒有什麼改進，我已經在使用DataOutputStream和緩衝，這很容易的順序方法。正如我的微基準所示，排序和迭代有所不同。 – marcorossi 2011-05-16 18:30:58

爲什麼你說要製作一個ArrayList >（例如）並對它進行排序需要比構建TreeMap更多的「複製」？ – karmakaze 2011-05-16 18:45:22

您的問題是「任何想法？」。我想我能寫的任何東西都是答案。

我和你有同樣的問題，並廣泛測試了兩種解決方案：使用樹形圖，以便事先對物品進行排序，或在事後對其進行排序。我的基準測試結果與您的基準測試結果相同。根據事實排序更快。

我不會擔心第二種方法需要更多複製的事實。首先，速度更快，對嗎？如果第二種方法需要更少的CPU週期，那麼效果會更好。

如果內存是一個問題，那麼請記住，treemap和hashmaps每個項目的內存數量要比由一個簡單的對象數組支持的ArrayList多得多。樹形圖或散列表中的每個元素至少需要一個對象，通常更多。對象有很多開銷，32或更多字節。在一個平面數組中，每個元素只需要4個字節。

我的基準測試顯示，從內存中分配數組的時間與數組的大小大致成正比，一旦你的數組大小超過了幾十個字節。因此，如果分配ArrayList真的很大，可能會很慢。不過，我認爲這是更好的選擇，只要不存在內存不足的危險。

來源

2011-05-16 19:39:20 ccleve

實際上，我用visualvm檢查內存消耗，並且treemap實現使用更多的內存。我想我有大約500萬個元素，這爲陣列創造了大約20MB的空間。這對我來說非常好。感謝您的洞察力！ – marcorossi 2011-05-16 20:04:42

將散列表映射到磁盤上的最快方法

回答

相關問題