提高Java/Stream/filter的响应时间

Question

我正在使用流（filter/anyMatch）对两个对象列表进行比较。两个列表的大小最多可达一百万个对象。

我用下面的代码进行了测试。通常两个列表的大小很接近。

如何提高下面代码的响应时间？

List<String> listDifferences = list1.stream()
            .filter(o1 -> list2.stream()
                    .noneMatch(o2 -> o2.getValue().equals(o1.getValue())))
            .map(ObjectValue::getValue).collect(Collectors.toList());

每个列表 699839 个对象的时间响应：

Fri May 10 16:14:09 CEST 2024
processing ....
Fri May 10 16:33:30 CEST 2024

Answer 1

这不是性能的意义所在。

事实上，您将问题集中在“流”/“过滤器”上，这表明您正在考虑“如何”迭代集合，从而对性能产生可衡量的影响。或者，更糟糕的是，您认为流“更好”，特别是“更快”。 这都是错误的。

这与你如何迭代这些东西无关。一切都同样快（或者，在本例中，同样慢）。如果有的话，流速度会更慢。它与可读性有关（它们通常可读性较差。它是工具箱中的一个工具。在适当的时候使用它。通常，它是不合适的。如果您认为“流......那些是......更好......因为......它们是流！” - 这是一个非常有害的思维过程。好的代码之所以好，是因为它是可读/可理解的（意思是：不太熟悉的读者会得出关于它的作用以及比其他编写方式更快的结论） ，这个结论是

正确

），易于测试，并且灵活（面对可预期的变更请求，它很容易适应以满足这些请求）。

如果

用流编写它会在这些因素上产生更好的“分数”，那么流会更好。如果不是，那么他们就不是。对于任何风格来说，从来都不是“这种风格比那种风格更好”。当然不是“使用流”。 那么它是关于什么的：算法复杂性

您实际寻找的内容与流无关。这与数据结构的设计方式有关。您正在寻找算法复杂性的概念。通常用“大 O 表示法”来表示 - 您可能听说过这个术语。

给定一个对未知但可数数量的条目进行操作的算法，让我们处理如此多的条目，它需要多长时间（或完成该工作消耗多少内存）的性能特征开始形成相对于多少条目的数学关系我们处理的条目。大 O 表示法表达了这种数学关系。它只是涉及“假设有一个足够大的输入集，当您相对而言增加或缩小该输入集时，需要多长时间”。它没有声明特定于 CPU 的性能，事实上，计算机的工作方式，对于给定的算法，您可以提供适用于任何体系结构和任何操作系统的特定数学关系。

例如，您的算法是

O(n*m)

，其中

n

代表输入列表 1 的大小，而

m

是输入列表 2。为了简化问题，我们可以假设两个列表的大小大致相等，使得

O(n^2)

。换句话说，如果您发现在

n=10,000

需要 10 秒，那么对于

n=20,000

，预期需要 10*10 = 100 秒左右。随着处理的元素数量线性增长，所需时间呈平方增长。这可不太好。如何处理数据（使用 for 循环或列表）并不重要。在什么 CPU 上运行它，或者用什么编程语言编写它并不重要。

O(n^2)

的特点就是这个算法的特点。

解决办法是使用不同的算法！

正确的算法：集合

这要快几个数量级，因为它具有非常不同的性能特征 - 它的特征是

O(n+m)

，如果我们说列表大约同样大，则可以归结为简单的

O(n)

。因为算法复杂性与相对度量有关，所以常数因子是无关紧要的（因此，

O(2n)

只是

O(n)

）。那是因为首先我们将列表 1 中的所有元素添加到一个集合中（这需要

O(n)

时间 - 输入大小加倍会使处理时间加倍；与您的算法相反，其中输入大小加倍会呈指数增加处理时间）。然后，对于第二个列表中的每个元素，我们询问集合是否包含该元素

O(1)

。因此，这个操作是

O(m)

。按顺序运行它们，我们得到

O(n+m)

，它简化为

O(n)

:

var set1 = new HashSet<String>(list1); // O(n)
var set2 = new HashSet<String>(list2); // O(m)
set1.removeAll(set2); // O(n)

... and I gues if you must have your answer in list form:
return new ArrayList<String>(set1); // O(n)

这是一个序列中的一堆 

O(n)

，所以总共只有

O(n)

。请注意，这些都不使用流。如果你愿意的话也可以。没什么区别。除此之外，它的可读性会变得较差。

您的代码实际上使用了子属性（

.getValue()

），而不是对象本身。这不是特别问题。

var set1 = new HashSet<String>();
for (MyObj o1 : list1) set1.add(o1.getValue());
var set2 = new HashSet<String>();
for (MyObj o2 : list2) set2.add(o2.getValue());
set1.removeAll(set2);
return new ArrayList<String>(set1);

注意：只要集合的元素具有适当的哈希分布，集合就具有

---

O(1)

性能。没有理由认为您会在这个问题上遇到麻烦。