2

Java 允许通过Collection 接口的和方法计算（集合论）差和两个 Collection 对象的交集。removeAll()retainAll()

这两个方法在Java 6的AbstractCollection 类中的实现是

public boolean removeAll(Collection<?> c) { // Difference
boolean modified = false;
Iterator<?> e = iterator();
while (e.hasNext()) {
    if (c.contains(e.next())) {
    e.remove();
    modified = true;
    }
}
return modified;
}

public boolean retainAll(Collection<?> c) { // Intersection
boolean modified = false;
Iterator<E> e = iterator();
while (e.hasNext()) {
    if (!c.contains(e.next())) {
    e.remove();
    modified = true;
    }
}
return modified;
}

有什么方法可以更快地实现或执行上述（显然很昂贵）操作？

例如，在计算差异或交集之前对集合进行排序是否会带来任何整体性能提升？

是否有任何类别的 Collections 框架更适合使用这些操作（在性能方面）？

4

4 回答 4

1

是的，有一种更快的方法可能。您提供的代码针对 e 的每个元素通过 c 循环。对于两个 100 个元素的数组，它将比较大约 100,000 个元素。

如果先对两个数组进行排序，则只需继续比较前两个元素。这将进行数百次比较。这类似于归并排序。做排序集合的交集left和right：

function intersect(left, right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) == first(right)
            append first(left) to result
            left = rest(left)
            right = rest(right)
        else if first(left) < first(right)
            left = rest(left)
        else
            right = rest(right)
    end while
    return result
于 2012-05-11T07:42:51.887 回答
1

这些实现在AbstractCollection其中，因此它们非常通用，因为在这个抽象级别上，对集合知之甚少，并且可用操作的数量非常有限。Collection仅考虑接口允许的内容并且对集合的类型及其实现细节一无所知，很难有任何更智能的东西。排序可能有效也可能无效，具体取决于所讨论集合的大小和类型，在此级别代码无法知道。

于 2012-05-11T07:44:08.157 回答
1

阅读以下的javadoc AbstractCollection：

要实现一个不可修改的集合，程序员只需要扩展这个类并提供迭代器的实现[...]

因此，我认为您应该检查 Iterator 是如何为特定类实现的，以真正了解这些方法的性能。

于 2012-05-11T07:45:47.113 回答
1

有什么方法可以更快地实现或执行上述（显然很昂贵）操作？

这些操作到底有多昂贵取决于作为参数传递的集合如何实现 contains()。如果它是HashSet,contains是一个常数（预期）时间操作，导致removeAll或retainAll完成线性（预期）时间。

排序会更昂贵。

好吧，集合操作在 a 上完成时最有效是合理的Set，不是吗？

如果集合中的元素是枚举或密集整数，您可以使用 aEnumSet或 a获得更快的速度BitSet。

于 2012-05-12T01:22:17.370 回答