在 Stream reduce 方法中，恒等式必须始终为 0 求和和 1 乘法？
In Stream reduce method, must the identity always be 0 for sum and 1 for multiplication?
我继续java8学习
我发现了一个有趣的行为：
让我们看看代码示例：
// identity value and accumulator and combiner
Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return surprising result
.reduce(1,
(intermediateResult, p) -> intermediateResult + p.age,
(ir1, ir2) -> ir1 + ir2);
System.out.println(summaryAge);
和型号class:
public class Person {
String name;
Integer age;
///...
public static Collection<Person> getPersons() {
List<Person> persons = new ArrayList<>();
persons.add(new Person("Vasya", 12));
persons.add(new Person("Petya", 32));
persons.add(new Person("Serj", 10));
persons.add(new Person("Onotole", 18));
return persons;
}
}
12+32+10+18 = 72。对于顺序流，此代码总是 returns 73 即 72 + 1 但对于并行，它总是 returns 76 即 72 + 4*1 （ 4 等于流元素数）。
当我看到这个结果时，我认为并行流和顺序流 return 不同的结果很奇怪。
我是不是哪里违约了？
P.S.
对我来说，73 是预期结果，但 76 不是。
Stream.reduce 的 JavaDoc 文档明确指出
The identity value must be an identity for the combiner function
1 不是加法运算符的标识值，这就是您得到意外结果的原因。如果您使用 0（ 是 加法运算符的标识值），那么您将从串行流和并行流中获得相同的结果。
是的，您违反了 combiner 函数的约定。作为reduce的第一个元素的identity必须满足combiner(identity, u) == u。引用 Stream.reduce 的 Javadoc:
The identity value must be an identity for the combiner function. This means that for all u, combiner(identity, u) is equal to u.
但是，您的组合器函数执行加法，而 1 不是加法的标识元素； 0是。
将用于 0 的标识更改为 0，您不会感到惊讶：两个选项的结果将为 72。
为了您自己的娱乐，更改组合器函数以执行乘法（将身份保持为 1），您还会注意到两个选项的结果相同。
让我们构建一个身份既不是 0 也不是 1 的示例。给定您自己的域 class，考虑：
System.out.println(Person.getPersons().stream()
.reduce("",
(acc, p) -> acc.length() > p.name.length() ? acc : p.name,
(n1, n2) -> n1.length() > n2.length() ? n1 : n2));
这会将 Person 流减少到最长的人名。
身份值是一个值，例如x op identity = x。这不是 Java Stream 所独有的概念，例如参见 [=25=].
列出了一些恒等元素的例子，其中一些可以直接用Java代码表示，例如
reduce("", String::concat)reduce(true, (a,b) -> a&&b)reduce(false, (a,b) -> a||b)reduce(Collections.emptySet(),
(a,b)->{ Set<X> s=new HashSet<>(a); s.addAll(b); return s; })reduce(Double.POSITIVE_INFINITY, Math::min)reduce(Double.NEGATIVE_INFINITY, Math::max)
需要明确的是，表达式x + y == x对于任意x只有在y==0时才成立，因此0是加法的恒等元。同样，1 是乘法的标识元素。
更复杂的例子是
减少谓词流
reduce(x->true, Predicate::and)
reduce(x->false, Predicate::or)
减少函数流
reduce(Function.identity(), Function::andThen)
除了之前发布的优秀答案之外，应该提到的是，如果你想用非零的值开始求和，你可以将初始加数移出流操作：
Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return no surprising result
.reduce(0, (intermediateResult, p) -> intermediateResult + p.age,
(ir1, ir2) -> ir1 + ir2)+1;
其他归约操作也是如此。例如，如果你想计算以2开头的产品而不是做错.reduce(2, (a, b) -> a*b)，你可以做.reduce(1, (a, b) -> a*b)*2。只需找到您的操作的真实标识，将 "false identity" 移到外面，您将获得顺序和并行情况的正确结果。
最后请注意，有更有效的方法可以解决您的问题：
Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return no surprising result
.collect(Collectors.summingInt(p -> p.age))+1;
或者
Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return no surprising result
.mapToInt(p -> p.age).sum()+1;
这里的求和在每个中间步骤都没有装箱，因此可以更快。
您的问题实际上分为两部分。为什么使用顺序得到 73 时使用并行得到 76。就 Reduce 的乘法和加法而言，身份是什么。
回答后一部分将有助于回答第一部分。身份是一个数学概念，对于那些非数学极客，我将尽量使用简单的术语。标识是应用于自身的值 returns 相同的值。
加法恒等式为0。如果我们假设a是任意数，则加法恒等式属性数字表明 a 加上它的身份将 return a. （基本上，a + 0=a）。乘法恒等式表示 b 乘以其恒等式，即 1) 总是 returns 本身，b。
javareduce 方法使用标识的方式更多一些。让我们能够说，如果我们愿意的话，我们希望通过额外的步骤来执行加法和乘法运算。如果你以你的例子为例：并将身份更改为 0，你将得到 72。
Integer summaryAge = Person.getPersons().stream()
.reduce(0, (intermediateResult, p) -> intermediateResult + p.age,
(ir1, ir2) -> ir1 + ir2);
System.out.println(summaryAge);
这只是将年龄相加，return得出该值。把它改成100，你会return 172。但是当你运行平行时，为什么你的结果会得到76，而在我的例子中会return 472？这是因为当您使用流时，结果被视为一个集合，而不是单个元素。根据流上的 JavaDocs：
Streams facilitate parallel execution by reframing the computation as a pipeline of aggregate operations, rather than as imperative operations on each individual element.
为什么集的处理很重要，通过使用标准流（非：并行或并行流），您在示例中所做的是求和并将其视为单个数字。因此你得到 73，并且将身份更改为 100，我会得到 172。但是为什么使用并行，你会得到 76？或者在我的例子中是 472？因为 java 现在正在将集合拆分为更小的（单个）元素，加上它的标识（你声明为 1）求和，然后将结果求和到执行相同操作的其余元素。
如果您的意图是将结果加 1，则更安全的做法是按照 Tagir 的建议，在流的 return 之后的末尾加 1。
很好地解释了不同函数的身份是什么，但没有解释 为什么我们需要身份 以及为什么 之间有不同的结果]并行和顺序流。
您的问题可以简化为对知道如何对 2 个元素求和的元素列表求和。
所以让我们使用一个列表 L = {12,32,10,18} 和一个求和函数 (a,b) -> a + b
就像你在学校学习的那样：
(12,32) -> 12 + 32 -> 44
(44,10) -> 44 + 10 -> 54
(54,18) -> 54 + 18 -> 72
现在假设我们的列表变成L = {12}，如何对这个列表求和？身份 (x op identity = x) 来了。
(0,12) -> 12
所以现在你可以理解为什么如果你用 1 而不是 0，你的总和会得到 +1，那是因为你用错误的值初始化。
(1,12) -> 1 + 12 -> 13
(13,32) -> 13 + 32 -> 45
(45,10) -> 45 + 10 -> 55
(55,18) -> 55 + 18 -> 73
那么现在，我们如何提高速度？ 并行化
如果我们可以拆分我们的列表并将这些拆分后的列表提供给 4 个不同的线程（假设 4 核 cpu），然后将其合并呢？这将为我们提供 L1 = {12}、L2 = {32}、L3 = {10}、L4 = {18}
所以身份 = 1
- 线程 1：
(1,12) -> 1+12 -> 13
- 线程 2：
(1,32) -> 1+32 -> 33
- 线程 3：
(1,10) -> 1+10 -> 11
- 线程 4：
(1,18) -> 1+18 -> 19
然后合并，13 + 33 + 11 +19，等于76，这解释了错误传播 4 次的原因。
在这种情况下，并行可能效率较低。
但这个结果取决于你的机器和输入列表。 Java 不会为 1000 个元素创建 1000 个线程，并且错误会随着输入的增长而传播得更慢。
尝试 运行 这段代码求和一千 1 秒，结果非常接近 1000
public class StreamReduce {
public static void main(String[] args) {
int sum = IntStream.range(0, 1000).map(i -> 1).parallel().reduce(1, (r, e) -> r + e);
System.out.println("sum: " + sum);
}
}
现在你应该明白为什么如果你打破身份契约，并行和顺序会有不同的结果。
请参阅 Oracle doc 以了解正确的写法
问题的本质是什么？
我的观点略有不同。尽管 给出了并行性需要恒等式的合理理由，但这真的有必要吗？我相信不是，因为二元运算符本身的结合性足以让我们并行化 reduce 作业。
给定一个表达式 A op B op C op D，结合律保证它的计算等价于 (A op B) op (C op D)，这样我们就可以并行计算子表达式 (A op B) 和 (C op D)之后合并结果而不改变最终结果。例如，对于加法运算，初始值 = 10，并且 L = [1, 2, 3]，我们想要计算 10 + 1 + 2 + 3 = 16。我们应该可以计算 10 + 1 = 11 和 2 + 3 = 5 并行，最后做 11 + 5 = 16.
Java 要求初始值是我能想到的身份的唯一原因是因为语言开发人员希望使实现简单并且所有并行化的子作业对称。否则，他们可能不得不区分第一个将初始值作为输入的子作业与其他不这样做的子作业。现在，他们只需要将初始值平均分配给每个子作业，它自己也是一个"reduce"。
但是，更多的是关于实施限制，IMO 不应该向语言用户公开这一点。我的直觉告诉我必须存在一个简单的实现，不需要初始值是一个标识。
我继续java8学习
我发现了一个有趣的行为：
让我们看看代码示例：
// identity value and accumulator and combiner
Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return surprising result
.reduce(1,
(intermediateResult, p) -> intermediateResult + p.age,
(ir1, ir2) -> ir1 + ir2);
System.out.println(summaryAge);
和型号class:
public class Person {
String name;
Integer age;
///...
public static Collection<Person> getPersons() {
List<Person> persons = new ArrayList<>();
persons.add(new Person("Vasya", 12));
persons.add(new Person("Petya", 32));
persons.add(new Person("Serj", 10));
persons.add(new Person("Onotole", 18));
return persons;
}
}
12+32+10+18 = 72。对于顺序流，此代码总是 returns 73 即 72 + 1 但对于并行，它总是 returns 76 即 72 + 4*1 （ 4 等于流元素数）。
当我看到这个结果时，我认为并行流和顺序流 return 不同的结果很奇怪。
我是不是哪里违约了？
P.S.
对我来说，73 是预期结果，但 76 不是。
Stream.reduce 的 JavaDoc 文档明确指出
The identity value must be an identity for the combiner function
1 不是加法运算符的标识值，这就是您得到意外结果的原因。如果您使用 0（ 是 加法运算符的标识值），那么您将从串行流和并行流中获得相同的结果。
是的，您违反了 combiner 函数的约定。作为reduce的第一个元素的identity必须满足combiner(identity, u) == u。引用 Stream.reduce 的 Javadoc:
The identity value must be an identity for the combiner function. This means that for all
u,combiner(identity, u)is equal tou.
但是，您的组合器函数执行加法，而 1 不是加法的标识元素； 0是。
将用于
0的标识更改为0，您不会感到惊讶：两个选项的结果将为 72。为了您自己的娱乐，更改组合器函数以执行乘法（将身份保持为 1），您还会注意到两个选项的结果相同。
让我们构建一个身份既不是 0 也不是 1 的示例。给定您自己的域 class，考虑：
System.out.println(Person.getPersons().stream()
.reduce("",
(acc, p) -> acc.length() > p.name.length() ? acc : p.name,
(n1, n2) -> n1.length() > n2.length() ? n1 : n2));
这会将 Person 流减少到最长的人名。
身份值是一个值，例如x op identity = x。这不是 Java Stream 所独有的概念，例如参见 [=25=].
列出了一些恒等元素的例子，其中一些可以直接用Java代码表示，例如
reduce("", String::concat)reduce(true, (a,b) -> a&&b)reduce(false, (a,b) -> a||b)reduce(Collections.emptySet(), (a,b)->{ Set<X> s=new HashSet<>(a); s.addAll(b); return s; })reduce(Double.POSITIVE_INFINITY, Math::min)reduce(Double.NEGATIVE_INFINITY, Math::max)
需要明确的是，表达式x + y == x对于任意x只有在y==0时才成立，因此0是加法的恒等元。同样，1 是乘法的标识元素。
更复杂的例子是
减少谓词流
reduce(x->true, Predicate::and) reduce(x->false, Predicate::or)减少函数流
reduce(Function.identity(), Function::andThen)
除了之前发布的优秀答案之外，应该提到的是，如果你想用非零的值开始求和，你可以将初始加数移出流操作：
Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return no surprising result
.reduce(0, (intermediateResult, p) -> intermediateResult + p.age,
(ir1, ir2) -> ir1 + ir2)+1;
其他归约操作也是如此。例如，如果你想计算以2开头的产品而不是做错.reduce(2, (a, b) -> a*b)，你可以做.reduce(1, (a, b) -> a*b)*2。只需找到您的操作的真实标识，将 "false identity" 移到外面，您将获得顺序和并行情况的正确结果。
最后请注意，有更有效的方法可以解决您的问题：
Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return no surprising result
.collect(Collectors.summingInt(p -> p.age))+1;
或者
Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return no surprising result
.mapToInt(p -> p.age).sum()+1;
这里的求和在每个中间步骤都没有装箱，因此可以更快。
您的问题实际上分为两部分。为什么使用顺序得到 73 时使用并行得到 76。就 Reduce 的乘法和加法而言，身份是什么。
回答后一部分将有助于回答第一部分。身份是一个数学概念，对于那些非数学极客，我将尽量使用简单的术语。标识是应用于自身的值 returns 相同的值。
加法恒等式为0。如果我们假设a是任意数，则加法恒等式属性数字表明 a 加上它的身份将 return a. （基本上，a + 0=a）。乘法恒等式表示 b 乘以其恒等式，即 1) 总是 returns 本身，b。
javareduce 方法使用标识的方式更多一些。让我们能够说，如果我们愿意的话，我们希望通过额外的步骤来执行加法和乘法运算。如果你以你的例子为例：并将身份更改为 0，你将得到 72。
Integer summaryAge = Person.getPersons().stream()
.reduce(0, (intermediateResult, p) -> intermediateResult + p.age,
(ir1, ir2) -> ir1 + ir2);
System.out.println(summaryAge);
这只是将年龄相加，return得出该值。把它改成100，你会return 172。但是当你运行平行时，为什么你的结果会得到76，而在我的例子中会return 472？这是因为当您使用流时，结果被视为一个集合，而不是单个元素。根据流上的 JavaDocs：
Streams facilitate parallel execution by reframing the computation as a pipeline of aggregate operations, rather than as imperative operations on each individual element.
为什么集的处理很重要，通过使用标准流（非：并行或并行流），您在示例中所做的是求和并将其视为单个数字。因此你得到 73，并且将身份更改为 100，我会得到 172。但是为什么使用并行，你会得到 76？或者在我的例子中是 472？因为 java 现在正在将集合拆分为更小的（单个）元素，加上它的标识（你声明为 1）求和，然后将结果求和到执行相同操作的其余元素。
如果您的意图是将结果加 1，则更安全的做法是按照 Tagir 的建议，在流的 return 之后的末尾加 1。
您的问题可以简化为对知道如何对 2 个元素求和的元素列表求和。
所以让我们使用一个列表 L = {12,32,10,18} 和一个求和函数 (a,b) -> a + b
就像你在学校学习的那样：
(12,32) -> 12 + 32 -> 44
(44,10) -> 44 + 10 -> 54
(54,18) -> 54 + 18 -> 72
现在假设我们的列表变成L = {12}，如何对这个列表求和？身份 (x op identity = x) 来了。
(0,12) -> 12
所以现在你可以理解为什么如果你用 1 而不是 0，你的总和会得到 +1，那是因为你用错误的值初始化。
(1,12) -> 1 + 12 -> 13
(13,32) -> 13 + 32 -> 45
(45,10) -> 45 + 10 -> 55
(55,18) -> 55 + 18 -> 73
那么现在，我们如何提高速度？ 并行化
如果我们可以拆分我们的列表并将这些拆分后的列表提供给 4 个不同的线程（假设 4 核 cpu），然后将其合并呢？这将为我们提供 L1 = {12}、L2 = {32}、L3 = {10}、L4 = {18}
所以身份 = 1
- 线程 1：
(1,12) -> 1+12 -> 13 - 线程 2：
(1,32) -> 1+32 -> 33 - 线程 3：
(1,10) -> 1+10 -> 11 - 线程 4：
(1,18) -> 1+18 -> 19
然后合并，13 + 33 + 11 +19，等于76，这解释了错误传播 4 次的原因。
在这种情况下，并行可能效率较低。
但这个结果取决于你的机器和输入列表。 Java 不会为 1000 个元素创建 1000 个线程，并且错误会随着输入的增长而传播得更慢。
尝试 运行 这段代码求和一千 1 秒，结果非常接近 1000
public class StreamReduce {
public static void main(String[] args) {
int sum = IntStream.range(0, 1000).map(i -> 1).parallel().reduce(1, (r, e) -> r + e);
System.out.println("sum: " + sum);
}
}
现在你应该明白为什么如果你打破身份契约，并行和顺序会有不同的结果。
请参阅 Oracle doc 以了解正确的写法
问题的本质是什么？
我的观点略有不同。尽管
给定一个表达式 A op B op C op D，结合律保证它的计算等价于 (A op B) op (C op D)，这样我们就可以并行计算子表达式 (A op B) 和 (C op D)之后合并结果而不改变最终结果。例如，对于加法运算，初始值 = 10，并且 L = [1, 2, 3]，我们想要计算 10 + 1 + 2 + 3 = 16。我们应该可以计算 10 + 1 = 11 和 2 + 3 = 5 并行，最后做 11 + 5 = 16.
Java 要求初始值是我能想到的身份的唯一原因是因为语言开发人员希望使实现简单并且所有并行化的子作业对称。否则，他们可能不得不区分第一个将初始值作为输入的子作业与其他不这样做的子作业。现在，他们只需要将初始值平均分配给每个子作业，它自己也是一个"reduce"。
但是，更多的是关于实施限制，IMO 不应该向语言用户公开这一点。我的直觉告诉我必须存在一个简单的实现，不需要初始值是一个标识。