进行收集减法的最快方法

我有两套.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;
          }
 }

我想找一个算法,不仅适用于Sets,也适用于Array.

编辑:这里的Set不是JAVA API,它是一个数据结构.所以我不在乎Java API是否有一个removeAll()方法,我想找到这个问题的常见解决方案,我在使用Javascript和Actionscript时遇到了很多这样的问题.

我不认为你会更快地得到它,但你的代码看起来会更简单,也不会变慢a.removeAll(b);.removeAll()是Java-API的一部分.

为了效率分析:你给出的代码示例是O(n ^ 2),它的扩展性不是很好,但也不是地球上最可怕的东西(指数复杂性是你不想要的东西).只要您不知道Collection中数据的内部组织,就不会获得更好的性能.removeAll()由类本身实现,并了解内部组织.因此,如果数据是在Hash中组织的,那么您可能会获得更好的结果,如果数据是在未排序的数组中组织的,那么复杂性将是相同的.如果一个新项已经在集合中,那么Set必须有效地查找,所以我怀疑某种Hash是内部表示,特别是如果该实现被称为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中的元素.其他可能的数据组织也是可能的.