做收集減法的最快方法

我有兩個集合。 Set b是Set a的子集。他們都是非常龐大的集合。我想從b中減去b，做這個常用操作的最佳做法是什麼？我已經寫了很多這樣的代碼，我不認爲它是有效的。你的想法是什麼？做收集減法的最快方法

僞代碼:(這不是Java API）。

for(int i = 0 ; i < a.size(); i++) { 
      for (int j=0 ; j < b.size() ;j++) { 
       // do comparison , if found equals ,remove from a 
       break; 
      } 
}

我想找到一個算法，不僅適用於Sets，也適用於Array。

編輯：這裏設置不是JAVA API，它是一個數據結構。所以我不在乎Java API是否具有removeAll（）方法，我想爲這個問題找到一個通用的解決方案，當我使用Javascript和Actionscript時，遇到了很多像這樣的問題。

來源

2010-03-08 Sawyer

我改變了標籤列表，因爲OP對Java解決方案不感興趣。 – CPerkins 2010-03-08 12:40:46

不，不是。我想找到一個通用算法，而不是Java API。 – Sawyer 2010-03-08 12:48:50

對，所以我刪除了java標籤。 – CPerkins 2010-03-08 13:05:15

我不認爲你會得到更快，但你的代碼會看起來更簡單，不會變慢a.removeAll(b);。 removeAll()是Java-API的一部分。

對於效率分析：你給出的代碼示例是O（n^2），它的尺度不是很好，但也不是世上最恐怖的東西（指數複雜度是你不想要的東西）。只要您不知道集合中數據的內部組織，就不會獲得更好的性能。 removeAll（）由類本身實現並知道內部組織。因此，如果數據組織在散列中，如果數據組織在未排序的數組中，複雜性將會相同，您可能會得到更好的結果。如果一個新項目已經在集合中，一個集合必須有效地查找，所以我懷疑某種哈希作爲內部表示，特別是如果實現被稱爲HashSet。 :-)

編輯： OP改變了它的問題，提到它不僅僅是Java。 removeAll（）是一個Java-API，所以這個（或類似的）可能在其他語言中不可用。如前所述，如果集合是沒有其他限制的未排序數組，則兩個for循環已經是最快的解決方案。但是，如果數據組織不同，則可以選擇更快的選項。如果這兩個集合排序的數據（在我的例子是最小的元素第一），你可以做以下（降低複雜度爲O（n））：如果數據被組織成一個哈希

int bIndex = 0; 
for(int i = 0 ; i < a.size(); i++) { 
      while (a[i] < b[bIndex]) {bIndex++;} 
      if (a[i] == b[bIndex]) {markForRemoval(a[i]);} // I mark this only for removal, as the actual removal would make your index incorrect 
}

這兩個集合你也只需要一個for循環，直接訪問b中的元素。其他可能的數據組織也是可能的。

來源

2010-03-08 12:15:43 Mnementh

您已經看過Set界面中的removeAll方法嗎？

也檢出this stack overflow question。

來源

2010-03-08 12:15:43 extraneon

我相信你會發現java.util.HashSet.removeAll(Collection toRemove)表現不錯。另一方面，如果你沒有集合但是排序的集合，你可能會做得更好。

來源

2010-03-08 12:16:29

事實上，散列表，BST或針對隨機訪問進行優化的其他收集類型的性能應該會更好。 – 2010-03-08 12:19:29

最後，除了逐個比較元素之外沒有太多的選擇，並且刪除了兩者中的一個。

要做到這一點，你必須做一些事情，比如給所有集合成員一個唯一的值索引，然後構造一大堆代表每個集合的布爾值，然後你可以做一些操作來從B中減去B一個。鑑於創建獨特的價值指數和操縱非常大的位掩碼的開銷，我不知道這是否會更快。

我知道你不關心一個Java的解決方案，但因爲其他人都推薦的removeAll（），我想指出的是，它仍然在做基本上是同樣的事情在幕後。檢查HashSet的源代碼。

來源

2010-03-08 12:39:22 CPerkins

但我看不到任何快速排序算法迭代像這樣的集合，只有冒泡排序，它不夠快，有人說它應該被棄用。 – Sawyer 2010-03-08 12:45:19

正確，主要是removeAll（）應該做同樣的事情。但是閱讀代碼更簡單，更容易，而且一些removeAll-implementation可以更好地組織內部數據，特別是在Set中。一個Set應該使用某種快速的隨機訪問，以快速判斷一個元素是否已經存在。最簡單的方法是對條目進行排序，甚至可以將操作的複雜度降低到O（n）（只需要通過兩個集合進行一次迭代）。 – Mnementh 2010-03-08 12:46:14

@Mnementh：可以減少兩個int []數組與O（n）比較的複雜性嗎？ – Sawyer 2010-03-08 12:54:54

如果套被保持，使得元件可在以排序的順序任何給定的時間，然後可以執行在兩個集的單個線性通和創建在O（n）的時間的差值。現在，同樣的，這如果你可以在元素的免費 —的有序列表這是說，維護（即，添加元素和刪除元素的操作）的集支付維持的成本獲得以排序順序提供的元素。

任何一種「的removeAll」的運作，它依賴於執行查找必然要去比爲O（n）要差一些。

（它發生，我認爲差異的建設設定—，也就是說，這兩個列表—從線性構造的傳球可以爲O答案（N log n）的，如果你不是非常小心。）

來源

2010-03-08 12:53:41 Pointy

好吧，正確的想法已經被指出：該集合應該使用散列來實現。散列理想情況下具有O(1)的訪問成本，因此假設您可以確定哪個集合更大（例如在插入/刪除操作期間維護計數器），您可以獲得整體操作的成本O(min(m,n))。

在ActionScript 3，您會使用一個Dictionary。只需使用元素作爲鍵和值。

刪除這個樣子的：在JavaScript

for each (var key:* in set2) {//a simple for-in loop will also do the trick, since keys and values are equal, but for-each-in loops perform faster 
    delete set1[key]; 
}

，你需要給插入時IDS的條目，這樣你就可以使用這些ID作爲一個映射鍵。只需將ID映射到原始值即可。

刪除這個樣子的：

for (var key in set2) { 
    delete set1[key]; 
}

來源

2010-03-08 13:04:34 back2dos

由於b是的一個子集，我不知道爲什麼你的僞代碼有2個循環。煤礦，簡直是：

foreach b in B 
    remove b from A

在實踐中的這一運行時間是如何與你的運行時間比較依賴於，除其他事項外，你是如何實現的設置爲數據結構。

來源

2010-03-08 13:07:37

非常鼓舞人心的。 – Sawyer 2010-03-08 13:27:26

爲你寫它的操作是O（N^2），但如果集合是大，你可能需要使用一個哈希值。

// A is some kind of array, O(1) iteration 
// B is a hash containing elements to remove, O(1) contains(elt) 
List<T> removeAll(List<T> A, Set<T> B) { 
    List<T> result; // empty, could preallocate at |A| 
    for (elt : A) { // for each 'elt' belonging to A, hence O(|A|) 
    if (! B.contains(elt)) { // O(1) thanks to hash 
     C.add(elt) ; // ensure this is O(1) with preallocation or linked list 
    } 
    } 
    return result; 
}

這需要建立索引集B，所以你需要一個哈希函數。在Java中，您可以使用在時間和內存中爲O（| B |）的Set<T> Bh = new HashSet<T>(B);。因此總的來說，我們在內存中獲得了O（| A | + | B |），大致爲O（2 | A | +2 | B |））。確實要比removeAll的二次方，你會感覺到不同（TM）。

將元素複製到新數組中（如僞代碼中所做的）可能會更好，因爲如果保持元素順序（在A中左移元素代價高昂），直接從元素中刪除元素可能會導致開銷。

來源

2015-07-02 20:32:43

做收集減法的最快方法

回答

相關問題