做收集减法的最快方法

我有两个集合。 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

做收集减法的最快方法

回答

相关问题