2

我今天在一些编码过程中发现了containsAll()（一种List接口方法），它看起来很漂亮。有谁知道这在性能/迭代方面的成本是多少？

文档在这方面没有提供太多信息。

4

4 回答 4

3
  • 首先，它迭代所提供集合的每个元素
  • 然后它迭代列表的所有元素并使用它们将当前元素与它们进行比较.equals(..)（注意：这是关于列表，正如您在问题中指定的那样。其他集合的行为不同）

所以它是 O(n*m)，其中 n 和 m 是两个集合的大小。

public boolean containsAll(Collection<?> c) {
    Iterator<?> e = c.iterator();
    while (e.hasNext())
        if (!contains(e.next()))
        return false;
    return true;
}
于 2012-04-17T21:59:46.123 回答
3

使用来源，卢克:)

编辑：正如 Bozho 指出的那样，您在询问List.containsAll()哪些 overrides Collection.containsAll()。下面的漫谈主要是与后者有关：

大多数Collection类将使用from的实现containsAllAbstractCollection，它是这样的：

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

但是，不能保证某些实现会完全不同——这可能会导致更好或更差的运行时行为。

上面的实现containsAll将至少为 O(n)，其中 n 是您传入的Collection参数中的项目数，加上所需的时间contains：

  • 对于 a HashSet/HashMap这可能是 O(1) （最好的情况，没有冲突），所以总运行时间containsAll仍然是 O(n)
  • 对于 an ArrayList，contains将采用 O(m) 其中 m 是列表中的项目数（不是参数），因此总时间为containsAllO(n*m)
于 2012-04-17T22:00:01.883 回答
1

如果您正在调用 A.containsAll(B)

openjdk 迭代 B 调用 A.contains(b) 的所有元素。

A.contains(b) 迭代 A 调用 a.equals(b) 的所有元素

这取自open jdk 7的源代码

于 2012-04-17T22:04:08.717 回答
0

考虑

n.ContainsAll(m)

最好的情况是 O(m)，如果 n 是一个完美的哈希集。

考虑到未排序的列表，我可以提出一个 O(n*log(n) + m*log(m)) 算法

于 2012-04-17T22:01:03.457 回答