從多個HashMap對象創建SortedSet的最佳方式

我有一些HashMap數據結構包含數百個Comparable對象（比如MyClass），並且需要將所有值（不是鍵）放在一個單獨的數據結構，然後對其進行排序。從多個HashMap對象創建SortedSet的最佳方式

由於MyClass對象的數量和到達率，此過程（每毫秒執行至少一次）需要儘可能高效。

的一種方法是使用SortedSet，大致如下：

HashMap<String, MyClass>[] allMaps = ... // All the HashMaps 

SortedSet<MyClass> set = new TreeSet<MyClass>(); 

Collection<MyClass> c; 

for (HashMap<String, MyClass> m:allMaps) 
{ 
    c = m.values(); 
    set.addAll(c); 
}

它可能更快的有序集合傳遞給set.addAll()，這可能重新排序TreeSet在每次插入，或之後每隔幾插入。然而，爲此，需要將List傳遞給Collections.sort()，這意味着必須發生從Collection到List的轉換，即必須維持另一個性能命中。

此外，可能有另一種更有效的方式來實現相同的目標。

評論？

來源

2012-05-14 PNS

你需要多快？如果你的地圖只包含「數百個」對象，那麼它不應該成爲一個問題，除非你每隔50毫秒調用一次該方法......另外，我相信**首先會創建一個未排序集合值**然後**將未排序的集合傳遞給sortedSet.addAll方法。但我還沒有測試過，所以這只是一個猜測:-) – assylias

你這樣做的方式已經是正確的路要走。 TreeSet並不是完全依賴於每一個插入;它將元素插入正確的排序位置。每個'add'調用都是'O（log n）'。 –

是的，我的理解 - 創建一個未排序的大集合，然後對其進行排序。那樣，這種排序只能進行一次。在未排序的集合上調用Collections.sort（）可能會比將未排序的集合傳送到已排序的集合的速度更快（稍快）。它可能會也可能不會被優化出來，但我會避免代碼示例中的中間集合，並執行set.addAll（m.values）; – GreyBeardedGeek

我認爲答案有點取決於MyClass數據如何變化。例如，如果每個時間幀都有一些新值，那麼您可能需要考慮保留最後返回的有序集和前一個鍵的副本，以便在下一次運行時，您可以執行更改的增量（即在地圖中查找新的鍵，並手動將它們插入上次返回的有序集中）。

如果MyClass對象可能從地圖中刪除，此算法會有所不同。但一般的想法是讓它更快，你必須找到一種方法來執行增量更改，而不是每次都重新處理整個集合。

來源

2012-05-14 11:52:18 mprivat

MyClass數據通常每輪完全不同，因此進行增量並不是很有幫助。 :-) – PNS

哦，哇。好的。在使用HashMap []方面你有多少自由度？您可以將整個數組重新實現爲單個數據結構，以便在插入值時跟蹤排序值。 – mprivat

正如我在上面的評論中寫的，我必須對一堆HashMap 對象進行操作，所以我正在考慮將它們作爲可變參數數組傳遞給處理方法。但是目前無法避免單個HashMap 數據結構。 – PNS

從多個HashMap對象創建SortedSet的最佳方式

回答

相關問題