透视集合removeAll方法

Question

我有一个200 K大小的列表.我在过滤列表时面临一些问题。

以下是实现：

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

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

Answer 1

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

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());

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

相反，上面使用的过滤器版本的复杂性将是O(n+m)，因为构建ys中所有值的HashSet是O(m)，然后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那样)。