logo标签列表

做集合差的最快方法

javascriptactionscript-3performance
5
我有两个集合。Set b是Set a的子集，它们都非常大。 我想从a中减去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;
          }
 }

我希望找到一个算法，不仅适用于集合，也适用于数组。

编辑：这里的集合不是指JAVA API，而是一种数据结构。所以我不关心Java API是否有removeAll()方法，我想找到一个通用的解决方案，因为当我使用Javascript和Actionscript时，遇到了很多类似的问题。

我更改了标签列表，因为OP对Java解决方案不感兴趣。 - CPerkins
不，不是。我想找一个通用的算法，而不是Java API。 - Sawyer
好的，我已经移除了Java标签。 - CPerkins
8个回答
8
我认为使用 a.removeAll(b); 不会让你的代码更快，但它会使你的代码看起来更简单，并且不会变慢。 removeAll() 是Java-API的一部分。
就效率分析而言：您提供的代码示例是O(n^2)，这不是很好的扩展方式，但也不是最糟糕的事情（指数复杂度是您不想要的）。只要您不知道集合中数据的内部组织方式，就不会获得更好的性能。 removeAll() 是由类本身实现的，知道内部组织方式。因此，如果数据是以哈希方式组织的，则可能会获得更好的结果；如果数据是以未排序的数组方式组织的，则复杂度将保持不变。Set必须有效地查找新项目是否已经在集合中，因此我怀疑某种哈希作为内部表示，特别是如果实现称为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中的元素即可。数据的其他可能组织方式也是可以的。

1

好的，正确的想法已经指出：应该使用哈希实现集合。哈希理想情况下具有O(1)的访问成本，因此假设您可以确定哪个集合更大（例如在插入/删除操作期间维护计数器），则可以获得O(min(m,n))的总体操作成本。

在ActionScript 3中，您可以使用Dictionary。只需将元素用作键和值即可。

删除看起来像这样：

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];
}

在JavaScript中，插入时需要为条目分配ID，因此您可以将这些ID用作映射中的键。只需将ID映射到原始值即可。
删除操作如下：
for (var key in set2) {
    delete set1[key];
}
1
最后，除了一个一个比较元素并删除两个集合中都有的元素外，没有太多选择。
换另一种方式，你需要做一些花哨的事情，比如给所有集合成员分配唯一值索引，并构建一个表示每个集合的巨大布尔数组，然后可以进行位运算来从A中减去B。我不知道是否更快，考虑到创建唯一值索引和操作非常大的位掩码的开销。
我知道您不关心Java解决方案，但是既然其他人推荐了removeAll()，我想指出，在覆盖下，它仍然在做基本相同的事情。请检查HashSet的源代码。
正确，大多数情况下removeAll()应该做同样的事情。但在代码中，使用它更简单易读，并且一些removeAll实现可以更好地组织内部数据，特别是在Set中。Set应该使用某种快速随机访问的方法，以便快速确定元素是否已经存在。最简单的方法是对条目进行排序，即可将操作的复杂度降至O(n)（只需要通过两个集合进行一次迭代）。 - Mnementh
@Mnementh：将两个int []数组的比较复杂度降低到O（n）是可能的吗？ - Sawyer
@Tony：如果数组中的元素已经排序，你可以在一个循环中遍历两个数组。 - Mnementh
@CPerkins：非常期待看到您使用位掩码实现int[]比较的代码。 :) - Sawyer
@CPerkins：我猜你要使用的方法是这样的： http://www.ugrad.cs.ubc.ca/~cs490/sec202/notes/intro/bitmask.pdf - Sawyer
显示剩余2条评论
1

如果集合被维护得使元素在任何给定时间都按顺序可用，那么您可以对两个集合执行单个线性遍历，并在O(n)时间内创建差异。现在，重点是 如果 您可以免费获得元素的排序列表 - 这就是说，集合的维护（即添加元素和删除元素操作）支付了保持元素按排序顺序可用的成本。

任何依赖于执行查找的“removeAll”操作都必然比O(n)更糟。

（我想到了差异集合的构建 - 也就是从两个列表上的线性遍历构建的答案 - 如果不非常小心，可能会是O(n log n)。）

1

鉴于 b 是 a 的子集，我不确定你的伪代码为什么有两个循环。我的代码会更简单：

foreach b in B
    remove b from A

实际上，这个程序的运行时间与你的程序的运行时间相比取决于许多因素，其中包括你如何将集合实现为数据结构。
1

您目前编写的操作的时间复杂度为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中，您可以使用Set<T> Bh = new HashSet<T>(B);，它的时间和空间复杂度均为O（|B|）。 因此，总体上我们得到O（|A|+|B|）的时间复杂度和大约O（2|A|+2|B|）的空间复杂度。 肯定比removeAll的平方复杂度要好，您会感受到巨大的差异（TM）。
最好将元素复制到新数组中（如伪代码所示），因为直接从A中移除元素可能会导致开销，如果保持元素顺序（左移A中的元素是昂贵的）。
0
0

我相信你会发现java.util.HashSet.removeAll(Collection toRemove)表现良好。 另一方面，如果您没有使用集合而是使用排序的集合，您可能能够做得更好。

实际上，如果使用哈希表、二叉搜索树或其他针对随机访问进行优化的集合类型，性能应该会更好。 - Bart van Heukelom
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接