java - 深入了解Collections的removeAll方法

Question

我有一个大小约为 200k 的列表..我在过滤列表时遇到一些问题。

这里是实现:

public List<> filterList(List<> listToBeFiltered){
List<> removeElementsFromList = listToBeFiltered.parallelStream()
                                    .filter(//some filtering logic)
                                    .collect(Collectors.toList());
listToBeFiltered.removeAll(removeElementsFromList);
return listToBeFiltered;
}

我在代码中面临的问题是，当removeElementsFromList接近listToBeFiltered的大小时，程序将停留在removeAll语句处。非常感谢任何见解/替代解决方案。

Answer 1

问题是 x.removeAll(y) 操作是 O(n×m)，其中 n 是集合x，m是集合y的大小(即O(|x|×|y|) )。

removeAll 方法基本上只是迭代 y 中每个元素的整个列表，检查 x 中的每个元素是否恰好是相等，如果相等则将其删除。如果您可以一次性完成此操作，效率会更高。

假设您使用的是 Java 8，有一种更有效的方法可以做到这一点:

List<Integer> xs = new ArrayList<>();
// TODO: initialize xs with a bunch of values
List<Integer> ys = new ArrayList<>();
// TODO: initialize ys with a bunch of values
Set<Integer> ysSet = new HashSet<>(ys);
List<Integer> xsPrime = xs.stream()
    .filter(x -> !ysSet.contains(x))
    .collect(Collectors.toList());

对于大小为 100k 的 xs 和大小为 66k 的 ys，使用 removeAll 大约需要 5500ms，而使用上述方法只需要大约8ms。由于 removeAll 的二次复杂度，我预计当扩展到 200k 时，差异会更加明显。

相比之下，上面使用的过滤器版本的复杂度将为 O(n+m)，因为构建 O(m)>HashSet 中的所有值 ys，然后 O(n) 迭代 xs 中的所有值确保新的 ysSet 中不包含任何内容。 (当然，这是假设 HashSet 查找的时间为 O(1)。)

<小时/>

再次回顾您的问题，我意识到您已经在使用 filter...在这种情况下，我建议只需反转您的过滤器逻辑，然后将传入列表的值重置为过滤后的值:

public List<> filterList(List<> listToBeFiltered){
    List<> filteredList = listToBeFiltered.parallelStream()
        .filter(/* some inverted filtering logic */)
        .collect(Collectors.toList());
    listToBeFiltered.clear();
    listToBeFiltered.addAll(filteredList);
    return listToBeFiltered;
}

如果你不需要改变原始列表，那么你可以直接返回filteredList。 (无论如何，这将是我的首选解决方案。)

<小时/>

我刚刚再次运行测试，这次我添加了另一个使用循环而不是流的版本:

Set<Integer> ysSet = new HashSet<>(ys);
List<Integer> xsPrime = new ArrayList<>();
for (Integer x : xs) {
    if (!ysSet.contains(x)) {
        xsPrime.add(x);
    }
}
return xsPrime;

这个版本用了大约 7 毫秒而不是 8 毫秒完成。由于这仅比流版本快一点(特别是考虑到使用 removeAll 的原始版本慢了 3 个数量级)，因此我会坚持使用流版本 - 特别是因为您可以利用那里的并行性(正如您已经使用 parallelStream 所做的那样)。