12.11　流和过滤器的性能

新的 Stream 设施是 Java 8 的另一个关键特性，而且经常与 Lambda 表达式配合使用。在性能方面，流有一个很重要的特性，即它们可以自动并行化代码。关于并行流的信息可参见第 9 章；本节将探讨流和过滤器的一般性能特性。

延迟遍历（Lazy Traversal）

Stream 的第一个性能优势是它们被实现为了延迟的数据结构。举个例子，有一组股票代码，我们想从其中找到第一个不含字母 A 的代码。通过流实现该功能的代码看上去就像下面这样：

  1. public String findSymbol(ArrayList<String> al) {
  2.     Optional<String> t = al.stream().
  3.             filter(symbol -> symbol.charAt(0) != 'A').
  4.             filter(symbol -> symbol.charAt(1) != 'A').
  5.             filter(symbol -> symbol.charAt(2) != 'A').
  6.             filter(symbol -> symbol.charAt(3) != 'A').
  7.                findFirst();
  8.     return t.get();
  9. }

很明显，用一个过滤器实现会更好，不过我们还是稍后讨论。现在先思考一下，对例子中的这个流而言，实现为延迟数据结构有何意义？每个 filter() 方法都会返回一个新流，所以这里实际上有 4 个逻辑流。

其实除了设置一系列指针，filter() 方法什么都没做。其作用是，当在这个流上调用 findfirst() 方法时，不会执行任何的数据处理，也不会拿数据去跟字符 A 作比较。

相反，findfirst() 会向前面的流（从第 4 个过滤器返回的那个）要一个元素。而那个流还没有元素，于是又向后调用由第 3 个过滤器生成的流，以此类推。第 1 个过滤器将从 ArrayList（从技术上讲，就是从原始的流中）抓到第一个元素，并测试它的第一个字符是否不为 A。如果确实不是，它会完成回调，并将该股票代码向后返回；否则，它会继续迭代数组，直到找到一个匹配的股票代码（或者找遍整个数组）。第 2 个过滤器行为类似——当对第 1 个过滤器的回调返回时，它会测试第二个字符是否不为 A。如果确实不是，它会完成回调，并将该股票代码向后传递；否则，调用第 1 个过滤器获得下一个股票 代码。

这么多回调听上去效率很低，那就考虑一个替代方案。尽早处理流的算法类似这样：

  1. private <T> ArrayList<T> calcArray(ArrayLisr<T> src, Predicate<T> p) {
  2.     ArrayList<T> dst = new ArrayList<>();
  3.     for (T s : src) {
  4.         if (p.test(s))
  5.             dst.add(s);
  6.         }
  7.     return dst;
  8. }
  10. private static long calcEager(ArrayList<String> a1) {
  11.     long then = System.currentTimeMillis();
  12.     ArrayList<String> a2 = calcArray(a1, (String s) -> s.charAt(0) != 'A');
  13.     ArrayList<String> a3 = calcArray(a2, (String s) -> s.charAt(1) != 'A');
  14.     ArrayList<String> a4 = calcArray(a3, (String s) -> s.charAt(2) != 'A');
  15.     ArrayList<String> a5 = calcArray(a4, (String s) -> s.charAt(3) != 'A');
  16.     answer = a5.get(0);
  17.     long now = System.currentTimeMillis();
  18.     return now - then;
  19. }

与 Java 实际采用的延迟实现相比，这一替代方案效率要差些，原因有二。第一，它需要创建大量临时的 ArrayList 实例。第二，在延迟实现中，一旦 findfirst() 方法得到一个元素，处理就可以停止了。这意味着实际通过过滤器传递的只是所有元素的一个子集。而另一方面，在尽早处理的实现方案中，则必须多次处理整个 ArrayList，一直到最后一个创建。

因此，在这个例子中延迟实现比上面的替代方案性能更好，也就不足为奇了。具体而言，测试中所处理的 ArrayList 包含 456 976 个元素，每个元素都是 4 字母股票代码，元素按字母顺序排列。就延迟实现而言，在遇到 BBBB 之前，只处理了 18 278 个元素，到 BBBB 就可以停止了。迭代器实现所花的时间要比延迟实现长两个数量级，如表 12-10 所示。

表12-10：延迟处理与尽早处理的时间对比

实现 所用时间（秒）
过滤器/findFirst 0.359
迭代器/findFirst 48.706

为什么过滤器解决方案比迭代器快这么多呢？一个原因是，过滤器有机会使用算法优化：当完成需要做的任务时，就可以停下来，因此处理的数据较少。

如果必须处理整组数据，过滤器和迭代器的性能相比又会如何呢？对于这个例子，我们稍微修改一下测试。前面的例子很好地演示了多个过滤器如何工作，但是很明显，如果用一个过滤器处理，性能有望变得更好：

  1. public int countSymbols(ArrayList<String> al) {
  2.     int count = 0;
  3.     t = al.stream().
  4.             filter(symbol -> symbol.charAt(0) != 'A' &&
  5.                              symbol.charAt(1) != 'A' &&
  6.                              symbol.charAt(2) != 'A' &&
  7.                              symbol.charAt(3) != 'A').
  8.                forEach(symbol -> count++);
  9.     return count;
  10. }

这个例子也修改了最终代码，会计算股票代码的个数，这样就会处理整个列表了。另一方面，尽早处理的方案也可以稍作修改，直接使用迭代器：

  1. public int countSymbols(ArrayList<String> al) {
  2.     int count = 0;
  3.     for (String symbol : al) {
  4.         if (symbol.charAt(0) != 'A' &&
  5.             symbol.charAt(1) != 'A' &&
  6.             symbol.charAt(2) != 'A' &&
  7.             symbol.charAt(3) != 'A')
  8.             count++;
  9.     return count;
  10. }

即使在这种情况下，延迟过滤器的实现还是要比迭代器快（参见表 12-11）。

表12-11：使用一个过滤器与一个迭代器的时间

实现 所用时间（秒）
多个过滤器 18.0
单个过滤器 6.5
迭代器 / 计数 6.8

出于比较的目的，表 12-11 的第一行是使用 4 个独立的迭代器处理整个列表的情况。和只用一个过滤器这种最优情况相比，使用一个过滤器还是要比使用一个迭代器稍微快些。

12.11　流和过滤器的性能 - 图1　快速小结

1. 过滤器因为支持在迭代过程中结束处理，所以有很大的性能优势。

2. 即使都要处理整个数据集，一个过滤器还是要比一个迭代器稍微快些。

3. 多个过滤器有些开销，所以要确保编写好用的过滤器。