哪個工會更有效率：List/HashSet

我正在寫一些算法，我需要使用一個集合，而且他們的主要（也是唯一的）動作就是union。哪個工會更有效率：List/HashSet

我將有大約百萬對象，我需要知道哪些系列有着更高效的工會法 - 列表或HashSet的（OT也許別的東西嗎？）。

在此先感謝。

2017-10-21 user8794683

第一個可能有重複，另一個，沒有。你也應該根據這個標準來選擇。 – davidxxx

我將在列表中使用'distinct'。 – user8794683

列表有很多（可能是無限的）實現，所以做比較是不可能的。你基本上想要添加兩個集合一起消除重複？ Hashset將使用它的.contains方法自動消除重複項，並且hashset具有快速包含。但是，這確實很容易分析，做到這一點，並使用更快的 –

我猜，當你說：「我將使用distinct與List」，你的意思是這樣的：

List l = ... 
    Set result = Collectors.toSet(l.stream().distinct()).union(someOtherSet);

與此相比：

HashSet h = ... 
    Set result = h.union(someOtherSet);

顯然第二版本更有效率。第一個必須從列表中產生一箇中間集合。每次運行它。

第一次保存的唯一東西是一些內存（從長遠來看），因爲使用後中間設置變得無法訪問。

而且第一個版本可以更簡單地寫，更高效地爲：

List l = ... 
    Set result = new HashSet(l).union(someOtherSet);

列表API沒有distinct()方法，沒有union()方法。

如果你實際使用Collection.contains()執行工會，那麼HashSet()會比任何標準的List實現快得多。正如@JBNizet所述：

HashSet.contains是O（1）。 List.contains是O（n）。

例如：

Set result = new HashSet(); 
    for (Integer element: set1) { 
     if (set2.contains(element)) { 
      result.add(element); 
     } 
    } 
    // result now contains the union of set1 and set2.

幾乎相同的代碼適用於列表。但它是太多較慢。

你問：

好吧，是的。但是工會呢？

參見上文。這是關於使用contains調用實施union。

那是什麼？ O（？）

請參見下面的文章：

所以工會的都是相同的O（N）（N - 大小第二集合）？

號

使用HashSet的：N x O(1)是O(N)
使用列表：N x O(N)是O(N^2)

或者更精確地說：

使用HashSet的： min(M, N) x O(1)是O(min(M, N))
使用列表：N x O(M)是O(NM)

其中N和M是兩組/列表的大小。通過迭代兩組中較小的一組，可以調整HashSet大小寫的性能。如上所述。

最後，如果元素類型是Integer然後Bitset可以比任一List或HashSet更有效。它可以使用少兩個數量級的內存！取決於範圍的整數，和密度的集合。

這就是Java分析。我對Scala並不熟悉，但底層的計算和複雜性將是相同的。

來源

2017-10-21 12:50:25

哪個工會更有效率：List/HashSet

回答

相關問題