在 reduce 操作中使用 StringBuilder(...) 作为标识值会产生不可预测的结果

Question

问题很直接：为什么我们不能在 java8 流的 reduce(...) 操作中使用 StringBuilder(...) 作为 identity function，而是 string1.concat(string2) 可以用作 identity function?

string1.concat(string2) 可以看作与 builder.append(string) 相似（虽然据了解这些操作几乎没有区别），但我无法理解 reduce 操作中的区别。考虑以下示例：

  List<String> list = Arrays.asList("1", "2", "3"); 
  
  // Example using the string concatenation operation
  System.out.println(list.stream().parallel()
            .reduce("", (s1, s2) -> s1 + s2, (s1, s2)->s1 + s2));

  // The same example, using the StringBuilder
  System.out.println(list.stream() .parallel()
            .reduce(new StringBuilder(""), (builder, s) -> builder
                    .append(s),(builder1, builder2) -> builder1
                    .append(builder2)));
 
 // using the actual concat(...) method
 System.out.println(list.stream().parallel()
            .reduce("", (s1, s2) -> s1.concat(s2), (s1, s2)->s1.concat(s2)));

这是执行以上几行后的输出：

 123
 321321321321   // output when StringBuilder() is used as Identity
 123

builder.append(string) 和 str1.concat(str2) 一样是一个关联运算。那么为什么 concat 有效而 append 无效呢？

Answer 1

当已经有一个实现时不要使用 .reduce()（或者像 Sweeper 的回答一样拥有 .collect()）。

List<String> list = Arrays.asList("1", "2", "3"); 
  
// Example using the string concatenation operation
System.out.println(list.stream()
   .parallel()
   .collect(Collectors.joining())
);
// prints "123"

编辑（这不适用于并行流）

取决于 .joining() 的实施：

final List<String> list = Arrays.asList("1", "2", "3");
System.out.println(list.stream().reduce(new StringBuilder(), 
    StringBuilder::append, 
    StringBuilder::append)
    .toString()
);
// prints "123"

Answer 2

是的，append是确实是关联的，但这不是作为累加器和组合器传递的函数的唯一要求。根据 docs，它们必须是：

关联
Non-interfering
无国籍

append 不是无状态的。它是 有状态的。当您执行 sb.append("Hello") 时，它不仅会 return 一个 StringBuilder 并在末尾附加 Hello， 它还会更改内容（即状态）的 sb.

也来自 docs:

Stream pipeline results may be nondeterministic or incorrect if the behavioral parameters to the stream operations are stateful. A stateful lambda (or other object implementing the appropriate functional interface) is one whose result depends on any state which might change during the execution of the stream pipeline.

也因此，一旦应用了累加器或组合器，new StringBuilder() 就不是有效身份。空字符串生成器中添加了一些东西，并且不再满足以下所有身份必须满足的等式：

combiner.apply(u, accumulator.apply(identity, t)) == accumulator.apply(u, t)

并行流在调用累加器 and/or 组合器后可能会使用旧的字符串构建器，并希望它们的内容不会更改。但是，累加器和组合器会改变字符串构建器，导致流产生不正确的结果。

另一方面，concat满足以上三个条件。它是无状态的，因为它不会更改调用它的字符串。它只是重新调整一个新的连接字符串。（String 无论如何都是不可变的，无法更改 :D）

无论如何，这是 mutable reduction 与 collect:

的用例

System.out.println((StringBuilder)list.stream().parallel()
    .collect(
        StringBuilder::new, 
        StringBuilder::append, 
        StringBuilder::append
    )
);

Answer 3

在阅读了文档并做了很多测试之后，我认为 reduce 类似于以下步骤：

会有多个线程做reduce，每个线程做一个部分减少；
对于身份，只有一个实例。每个累加器都将使用这个标识实例；
首先用标识实例和字符串元素进行累加以获得字符串生成器；
合并所有这些 StringBuilder；

所以问题是每次使用标识实例和字符串元素进行累积都会导致标识更改。第一次后积累的身份不再是身份

例如，我们考虑一个包含 2 个元素 {"1","2"} 的列表。将有 2 个线程，每个线程进行 1 次累积，其中一个进行最后合并。线程A用元素“1”累积身份，然后结果是一个内容为“1”的StringBuilder（仍然是身份，因为StringBuilder.append的return对象本身），但身份也改为内容“1”。然后线程 B 确实积累了元素“2”的身份，结果是“12”，不再是“2”。然后做combine就是这两个accumulate result的结果，它们都是identity instance本身，所以结果会是“1212”。它喜欢下面的代码片段：

StringBuilder identity = new StringBuilder();
StringBuilder accumulate1 = identity.append("1");
StringBuilder accumulate2 = identity.append("2");
StringBuilder combine = accumulate1.append(accumulate2);
// combine and accumulate1 and accumulate2 are all identity instance and result is "1212"
return combine;

更多元素，由于线程运行随机，每次结果都会不同。

知道原因后，如果我们将累加器固定如下

new StringBuilder(builder).append(s)

全行代码如下：

System.out.println(list.stream().parallel().reduce(new StringBuilder(), (builder, s) -> new StringBuilder(builder).append(s),
        (builder1, builder2) -> new StringBuilder(builder1).append(builder2)));

那么就不会再有问题了，因为累加器不会每次都更改身份实例和 return 新的 StringBuilder。但是不值得这样做，因为与 String concat 方法相比没有任何好处。

编辑：感谢@Holger 的示例，似乎如果有过滤功能，则可能会跳过一些累加器。所以combiner函数也需要改成

new StringBuilder(builder1).append(builder2)

在 reduce 操作中使用 StringBuilder(...) 作为标识值会产生不可预测的结果

Using StringBuilder(...) as an identity value in the reduce operations gives unpredictable outcome

java

parallel-processing

reduce

java-8

java-stream

编辑（这不适用于并行流）