洞察集合removeAll方法
我有一个大小〜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语句中。 非常感谢任何见解/替代解决方案。
问题是x.removeAll(y)操作是O（n×m） ，其中n是集合x的大小， m是集合y的大小（即O（| x |×| y） |） ）。
removeAll方法基本上只是迭代y每个元素的整个列表，检查x每个元素是否恰好相等，如果是，则将其删除。 如果你能在一次通过中做到这一点会更有效率。
假设您使用的是Java 8，那么有一种更有效的方法：
List xs = new ArrayList<>(); // TODO: initialize xs with a bunch of values List ys = new ArrayList<>(); // TODO: initialize ys with a bunch of values Set ysSet = new HashSet<>(ys); List xsPrime = xs.stream() .filter(x -> !ysSet.contains(x)) .collect(Collectors.toList());
对于大小为100k的xs和大小为66k ys ，使用removeAll大约需要5500ms，而使用上述方法只需要大约8ms。 由于removeAll的二次复杂性，当你扩展到200k时，我预计差异会更加明显。
相比之下，上面使用的filter版本的复杂性将是O（n + m） ，因为它是O（m）来构建ys中所有值的HashSet ，然后O（n）迭代所有的xs值以确保新的ysSet不包含任何值。 （这当然假设HashSet查找是O（1） 。）
再次回顾你的问题，我意识到你已经在使用filter …在这种情况下，我建议只是反转你的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 ysSet = new HashSet<>(ys); List xsPrime = new ArrayList<>(); for (Integer x : xs) { if (!ysSet.contains(x)) { xsPrime.add(x); } } return xsPrime;
这个版本在大约7毫秒而不是8毫秒完成。 由于这只比流版本稍微快一点（特别是考虑到使用removeAll的原始版本慢了3个数量级），我会坚持使用流版本 – 特别是因为你可以利用那里的并行性（就像你已经在做的那样） with parallelStream ）。