在Stream reduce方法中,对于sum,标识总是0,对于乘法,1是1吗?
我进行java 8学习。
我发现了有趣的行为:
让我们看看代码示例:
// 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);
和模型类:
public class Person { String name; Integer age; ///... public static Collection getPersons() { List 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
对于序列流,此代码始终返回73(72 + 1),但对于并行,它始终返回76(72 + 4 * 1)。 4 – 流元素计数。
当我看到这个结果时,我认为并行流和序列流返回不同的结果是很奇怪的。
我在某个地方违约吗?
PS
对我来说73是预期的结果,但76 – 不是。
标识值是一个值,使得x op identity = x
。 这是一个并非Java Stream
独有的概念,例如参见Wikipedia 。
它列出了一些身份元素的例子,其中一些可以直接用Java代码表示,例如
-
reduce("", String::concat)
-
reduce(true, (a,b) -> a&&b)
-
reduce(false, (a,b) -> a||b)
-
reduce(Collections.emptySet(), (a,b)->{ Set
s=new HashSet<>(a); s.addAll(b); return s; }) -
reduce(Double.POSITIVE_INFINITY, Math::min)
-
reduce(Double.NEGATIVE_INFINITY, Math::max)
应该清楚的是,当y==0
,只能满足任意x
的表达式x + y == x
,因此0
是加法的标识元素。 类似地, 1
是乘法的标识元素。
更复杂的例子是
-
减少谓词流
reduce(x->true, Predicate::and) reduce(x->false, Predicate::or)
-
减少function流
reduce(Function.identity(), Function::andThen)
是的,你违反了合并器function的合同。 身份是reduce
的第一个元素,必须满足combiner(identity, u) == u
。 引用Stream.reduce
的Javadoc:
标识值必须是组合器函数的标识。 这意味着对于所有
u
,combiner(identity, u)
等于u
。
但是,组合器函数执行加法, 1
不是添加的标识元素; 0
是。
-
将使用的身份更改为
0
,您将不会感到惊讶:两个选项的结果将为72。 -
为了您自己的娱乐,更改组合器function以执行乘法(将标识保持为1),您也会注意到两个选项的相同结果。
让我们构建一个身份既不是0或1的示例。给定您自己的域类,请考虑:
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流减少为最长的人名。
Stream.reduce
的JavaDoc文档明确指出了这一点
标识值必须是组合器函数的标识
1不是加法运算符的标识值,这就是您得到意外结果的原因。 如果您使用0(这是加法运算符的标识值),那么您将从串行和并行流中获得相同的结果。
除了之前发布的优秀答案之外,应该提到的是,如果你想开始用零以外的东西求和,你可以将初始加数移出流操作:
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
。 只需找到您操作的真实身份,将“假身份”移到外面,您将获得顺序和并行案例的正确结果。
最后请注意,有更有效的方法来解决您的问题:
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;
这里总和在每个中间步骤没有装箱的情况下执行,因此它可以更快。
你的问题确实有2个部分。 当你使用连续使用73时,为什么你使用并行为76。 对于Reduce来说,乘法和加法的身份是什么。
回答后者将有助于回答第一部分。 身份是一个数学概念,我会尽量为那些非数学极客保留简单的术语。 标识是应用于自身的值返回相同的值。
附加标识为0.如果我们假设a是任何数字,则数字的标识属性表示加上其标识将返回a 。 (基本上, a + 0 = a )。 乘法身份说b乘以其身份,即1)总是返回自己, b 。
java reduce方法更加可变地使用标识。 如果我们选择的话,让我们有能力说,我们希望通过额外的步骤执行加法和乘法运算。 如果你拿你的例子:并将身份改为0,你将获得72。
Integer summaryAge = Person.getPersons().stream() .reduce(0, (intermediateResult, p) -> intermediateResult + p.age, (ir1, ir2) -> ir1 + ir2); System.out.println(summaryAge);
这简单地将年龄相加并返回该值。 将它改为100,你将返回172.但是当你以并行方式运行时,为什么你的结果会得到76,而在我的例子中会返回472? 这是因为当您使用流时,结果被视为一组,而不是单个元素。 根据流上的JavaDocs:
Streams通过将计算重新定义为聚合操作的流水线而不是作为每个单独元素的命令操作来促进并行执行。
为什么对集合的处理很重要,通过使用标准流(非:parallel或parallelStream),您在示例中所做的是获取总和并处理单个数字。 因此你得到73,并且将身份改为100,我会得到172.但是为什么使用并行,你得到76? 还是在我的例子中472? 因为java现在将集合拆分为较小的(单个)元素,将其标识(您声明为1)加在一起,然后将结果与其余元素相加,后者执行了相同的操作。
如果您的意图是在结果中加1,那么遵循Tagir的建议更安全,并在返回流后添加1。
@holger的答案很好地解释了不同函数的标识是什么,但没有解释为什么我们需要标识以及为什么你有平行或顺序流的不同结果。
你的问题可以减少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个不同的线程(假设4core cpu)然后合并它会怎么样? 我们试试这会给我们L1 = {12}
L2 = {32}
L3 = {10}
L4 = {18}
所以身份= 1
- thread1:do
(1,12) -> 1+12 -> 13
- thread2:do
(1,32) -> 1+32 -> 33
1,32(1,32) -> 1+32 -> 33
- thread3:do
(1,10) -> 1+10 -> 11
- thread4:do
(1,18) -> 1+18 -> 19
并结合(13 + 33 + 11 +19)= 76这解释了为什么误差传播了4次。
在这种情况下,并行可能效率较低。
但是这个结果取决于你的机器而你输入的列表java不会为1000个elts创建1000个线程,并且当输入增长时rror会传播得更慢
尝试运行此代码汇总千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("reduced : " + sum); } }
所以现在你应该理解为什么如果你违反了身份合同,你在并行或顺序之间会有不同的结果。
请参阅Oracle doc以了解编写总和的正确方法
1问题的身份是什么? ;)