java - streams - En el método de reducción de flujo, ¿la identidad debe ser siempre 0 para suma y 1 para multiplicación?

stream() filter java

Question

Procedo java 8 aprendizaje.

He encontrado un comportamiento interesante:

veamos muestra de código:

// 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);

y clase de modelo:

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
Para la secuencia secuencial, este código devuelve 73 (72 + 1) siempre, pero para el paralelo devuelve 76 (72 + 4 * 1) siempre. 4 - recuento de elementos de flujo.

Cuando vi este resultado, pensé que era extraño que la secuencia paralela y las secuencias secuenciales arrojaran resultados diferentes.

¿Estoy rompiendo el contrato en alguna parte?

PD

para mí 73 es el resultado esperado pero 76, no.

Answer 1

Además de las excelentes respuestas publicadas antes, debe mencionarse que si desea comenzar a sumar con algo que no sea cero, simplemente puede mover el agregado inicial fuera de la operación de transmisión:

Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return no surprising result
.reduce(0, (intermediateResult, p) -> intermediateResult + p.age,
(ir1, ir2) -> ir1 + ir2)+1;

Lo mismo es posible para otras operaciones de reducción. Por ejemplo, si desea calcular el producto comenzando con 2 lugar de hacer mal .reduce(2, (a, b) -> a*b) , puede hacer .reduce(1, (a, b) -> a*b)*2 . Simplemente encuentre la identidad real para su operación, mueva la "identidad falsa" afuera y obtendrá el resultado correcto tanto para el caso secuencial como para el caso paralelo.

Finalmente tenga en cuenta que hay una manera más eficiente de resolver su problema:

Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return no surprising result
.collect(Collectors.summingInt(p -> p.age))+1;

o alternativamente

Integer summaryAge = Person.getPersons().stream()
//.parallel() //will return no surprising result
.mapToInt(p -> p.age).sum()+1;

Aquí la suma se realiza sin boxeo en cada paso intermedio, por lo que puede ser mucho más rápido.

Answer 2

El valor de identidad es un valor tal que x op identity = x . Este es un concepto que no es exclusivo de Java Stream s, ver por ejemplo en Wikipedia .

Enumera algunos ejemplos de elementos de identidad, algunos de ellos pueden expresarse directamente en código Java, p. Ej.

• 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)

Debe quedar claro que la expresión x + y == x para x + y == x arbitraria solo se puede cumplir cuando y==0 , por lo tanto 0 es el elemento de identidad para la suma. Del mismo modo, 1 es el elemento de identidad para la multiplicación.

Ejemplos más complejos son

• Reduciendo un flujo de predicados

  reduce(x->true, Predicate::and)
  reduce(x->false, Predicate::or)

• Reduciendo un flujo de funciones

  reduce(Function.identity(), Function::andThen)

Answer 3

La respuesta @holger explica en gran medida cuál es la identidad para diferentes funciones, pero no explica por qué necesitamos identidad y por qué tiene un resultado diferente con flujo paralelo o secuencial .

Su problema se puede reducir a ¹ para sumar una lista de elementos que sepa cómo sumar 2 elementos .

Entonces tomemos una lista L = {12,32,10,18} y una función de suma (a,b)-> a + b

Como aprendes en la escuela, harás:

(12,32) -> 12 + 32 -> 44
(44,10)-> 44 + 10 -> 54
(54,18)-> 54 + 18 -> 72

Ahora imagine que nuestra lista se convierte en L = {12} ¿cómo sumar esta lista? Aquí viene la identidad ( x op identity = x ).

(0,12) -> 12

Observaciones: una lista vacía devuelve identidad

Entonces, ahora puede entender por qué si pone 1 lugar de 0 obtiene +1 en su suma que está inicializando con un valor incorrecto.

(1,12) -> 1 + 12 -> 13
(13,32) -> 13 + 32 -> 45
(45,10)-> 45 + 10 -> 55
(55,18)-> 55 + 18 -> 73

Entonces, ¿cómo podemos mejorar la velocidad? Paralelo a las cosas

¿Qué pasa si podemos dividir nuestra lista y darles esa lista dividida a 4 hilos diferentes (suponiendo una CPU de 4core) y luego combinarla? Intentemos que esto nos dará L1 = {12} L2 = {32} L3 = {10} L4 = {18}

Entonces con identidad = 1

• thread1: do (1,12) -> 1+12 -> 13
• thread2: do (1,32) -> 1+32 -> 33
• thread3: do (1,10) -> 1+10 -> 11
• thread4: do (1,18) -> 1+18 -> 19

y combinar (13 + 33 + 11 +19) = 76 esto explica por qué nuestro error se propaga 4 veces.

En este caso, el paralelo puede ser menos eficiente.

Pero este resultado depende de su máquina y su lista de entrada java no creará 1000 hilos para 1000 elts y el rror se propagará más lentamente a medida que la entrada crezca

Intente ejecutar este código sumando mil 1, el resultado es bastante cercano a 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);
}
}

Entonces, ahora debe comprender por qué tiene un resultado diferente entre paralelo o secuencial si rompe el contrato de identidad.

Consulte el documento de Oracle para conocer la forma correcta de escribir su suma

¹ ¿Cuál es la identidad de un problema? ;)

Answer 4

La documentación de Stream.reduce para Stream.reduce establece específicamente que

El valor de identidad debe ser una identidad para la función de combinación

1 no es un valor de identidad para el operador de adición, por lo que obtiene resultados inesperados. Si usó 0 (que es el valor de identidad del operador de suma), obtendría el mismo resultado de las secuencias en serie y paralelas.

Answer 5

Sí, está incumpliendo el contrato de la función de combinación. La identidad, que es el primer elemento de reduce , debe satisfacer al combiner(identity, u) == u . Citando el Javadoc de Stream.reduce :

El valor de identidad debe ser una identidad para la función del combinador. Esto significa que para todo u , el combiner(identity, u) es igual a u .

Sin embargo, su función de combinador realiza una adición y 1 no es el elemento de identidad para la adición; 0 es.

• Cambie la identidad utilizada a 0 y no se sorprenderá: el resultado será 72 para las dos opciones.

• Para su propia diversión, cambie la función de su combinador para realizar una multiplicación (manteniendo la identidad en 1) y también notará el mismo resultado para ambas opciones.

Creemos un ejemplo donde la identidad no sea 0 o 1. Dada su propia clase de dominio, considere:

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));

Esto reducirá el flujo de Persona al nombre de persona más largo.

Answer 6

Su pregunta realmente tiene 2 partes. ¿Por qué obtienes 76 usando paralelo cuando obtienes 73 usando secuencial? Y cuál es la identidad, en cuanto a multiplicación y suma, va para Reducir.

Contestar lo último ayudará a responder la primera parte. La identidad es un concepto matemático, trataré de mantenerlo en términos simples para esos geeks no matemáticos. La identidad es el valor que se aplica a sí mismo devuelve el mismo valor.

La identidad aditiva es 0. Si asumiéramos que a es cualquier número, la propiedad de identidad de los números indica que a más su identidad devolverá a . (Básicamente, a + 0 = a ). La identidad multiplicativa dice que b multiplicado por su identidad, que es 1) siempre se devuelve, b .

El método java reduce utiliza la identidad un poco más variable. Dándonos la capacidad de decir, nos gustaría realizar las operaciones de suma y multiplicación con un paso adicional, si así lo decidimos. Si tomas tu ejemplo: y cambias la identidad a 0, obtendrás 72.

 Integer summaryAge = Person.getPersons().stream()
.reduce(0, (intermediateResult, p) -> intermediateResult + p.age,
(ir1, ir2) -> ir1 + ir2);
System.out.println(summaryAge);

Esto simplemente suma las edades juntas y devuelve ese valor. Cámbielo a 100, devolverá 172. Pero cuando se ejecuta en paralelo, ¿por qué su resultado obtiene 76, y en mi ejemplo devolvería 472? Es porque cuando usa una secuencia, los resultados se consideran un conjunto, en lugar de elementos individuales. Según los JavaDocs en las transmisiones:

Las secuencias facilitan la ejecución paralela al reformular el cálculo como una canalización de operaciones agregadas, en lugar de como operaciones imperativas en cada elemento individual.

¿Por qué es importante el tratamiento de conjuntos? Al utilizar la secuencia estándar (no: paralela o paralela), lo que está haciendo en su ejemplo es tomar la suma y tratar que es un solo número. Por lo tanto, obtienes 73, y al cambiar la identidad a 100, obtendría 172. Pero, ¿por qué usando el paralelo, obtienes 76? o en mi ejemplo 472? Debido a que Java ahora está dividiendo el conjunto en elementos más pequeños (individuales), agregando su identidad (que usted indicó como 1) sumando eso, y luego sumando el resultado al resto de los elementos, que ha realizado la misma operación.

Si sus intenciones son agregar 1 al resultado, es más seguro seguir la sugerencia de Tagir y agregar 1 al final después del regreso de la transmisión.