java - procesamiento - Comportamiento Stream.skip con operación de terminal desordenada

stream java ejemplos

Question

Ya he leído this y this preguntas, pero aún dudo si el comportamiento observado de Stream.skip fue pensado por los autores de JDK.

Tengamos una entrada simple de los números 1..20:

List<Integer> input = IntStream.rangeClosed(1, 20).boxed().collect(Collectors.toList());

Ahora creemos una secuencia paralela, combine el unordered() con skip() de diferentes maneras y recopile el resultado:

System.out.println("skip-skip-unordered-toList: "
        + input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .skip(1)
            .unordered()
            .collect(Collectors.toList()));
System.out.println("skip-unordered-skip-toList: "
        + input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .unordered()
            .skip(1)
            .collect(Collectors.toList()));
System.out.println("unordered-skip-skip-toList: "
        + input.parallelStream().filter(x -> x > 0)
            .unordered()
            .skip(1)
            .skip(1)
            .collect(Collectors.toList()));

El paso de filtrado no hace esencialmente nada aquí, pero agrega más dificultad para el motor de transmisión: ahora no conoce el tamaño exacto de la salida, por lo que algunas optimizaciones están desactivadas. Tengo los siguientes resultados:

skip-skip-unordered-toList: [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
// absent values: 1, 2
skip-unordered-skip-toList: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20]
// absent values: 1, 15
unordered-skip-skip-toList: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20]
// absent values: 7, 18

Los resultados están completamente bien, todo funciona como se esperaba. En el primer caso, pedí omitir los dos primeros elementos y luego recopilarlos en la lista sin ningún orden en particular. En el segundo caso, pedí omitir el primer elemento, luego convertirlo en desordenado y omitir un elemento más (no me importa cuál). En el tercer caso, pasé al modo desordenado primero, luego omito dos elementos arbitrarios.

Salteamos un elemento y recopilemos a la colección personalizada en modo desordenado. Nuestra colección personalizada será un HashSet :

System.out.println("skip-toCollection: "
        + input.parallelStream().filter(x -> x > 0)
        .skip(1)
        .unordered()
        .collect(Collectors.toCollection(HashSet::new)));

El resultado es satisfactorio:

skip-toCollection: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
// 1 is skipped

Entonces, en general, espero que mientras se ordene la secuencia, skip() los primeros elementos, de lo contrario, omite los arbitrarios.

Sin embargo, usemos una operación de terminal desordenada equivalente collect(Collectors.toSet()) :

System.out.println("skip-toSet: "
        + input.parallelStream().filter(x -> x > 0)
            .skip(1)
            .unordered()
            .collect(Collectors.toSet()));

Ahora la salida es:

skip-toSet: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20]
// 13 is skipped

Se puede lograr el mismo resultado con cualquier otra operación de terminal desordenada (como forEach , findAny , anyMatch , etc.). Eliminar el paso unordered() en este caso no cambia nada. Parece que si bien el paso unordered() hace que el flujo esté desordenado comenzando desde la operación actual, la operación de terminal desordenado hace que todo el flujo esté desordenado comenzando desde el principio a pesar de que esto puede afectar el resultado si se usa skip() . Esto me parece completamente engañoso: espero que usar el recolector desordenado sea lo mismo que convertir la secuencia en modo desordenado justo antes de la operación del terminal y usar el colector ordenado equivalente.

Entonces mis preguntas son:

1. ¿Se pretende este comportamiento o es un error?
2. En caso afirmativo, ¿está documentado en alguna parte? He leído la documentación de Stream.skip() : no dice nada sobre operaciones de terminal desordenadas. También la documentación de Characteristics.UNORDERED no es muy comprensiva y no dice que se perderá el pedido para toda la secuencia. Finalmente, la sección de Ordering en el resumen del paquete tampoco cubre este caso. ¿Probablemente me estoy perdiendo algo?
3. Si se pretende que la operación de terminal desordenada desordene todo el flujo, ¿por qué el paso unordered() desordena solo desde este punto? ¿Puedo confiar en este comportamiento? ¿O tuve la suerte de que mis primeras pruebas funcionen bien?

Answer 1

@ Rubén, probablemente no entiendas mi pregunta. Aproximadamente el problema es: por qué unordered (). Collect (toCollection (HashSet :: new)) se comporta de manera diferente que collect (toSet ()). Por supuesto, sé que toSet () no está ordenado.

Probablemente, pero, de todos modos, lo intentaré por segunda vez.

Echando un vistazo a los Javadocs de Collectors toSet y toCollection , podemos ver que toSet ofrece un recopilador desordenado

Este es un colector {@link Collector.Characteristics # UNORDERED desordenado}.

es decir, un CollectorImpl con la característica SIN ORDENAR . Echando un vistazo al Javadoc de Collector. Características # SIN ORDENAR podemos leer:

Indica que la operación de recopilación no se compromete a preservar el orden de encuentro de los elementos de entrada

En los Javadocs de Collector también podemos ver:

Para los recolectores concurrentes, una implementación es libre de implementar (aunque no es obligatorio) la reducción al mismo tiempo. Una reducción concurrente es aquella en la que la función del acumulador se llama simultáneamente desde múltiples subprocesos, utilizando el mismo contenedor de resultados modificable simultáneamente, en lugar de mantener el resultado aislado durante la acumulación. Una reducción concurrente solo debe aplicarse si el recopilador tiene las características {@link Characteristics # UNORDERED} o si los datos de origen no están ordenados

Esto significa para mí que, si establecemos la característica SIN ORDENAR , no nos importa en absoluto el orden en que los elementos de la corriente pasan al acumulador y, por lo tanto, los elementos se pueden extraer de la tubería en cualquier orden .

Por cierto, obtienes el mismo comportamiento si omites el desordenado () en tu ejemplo:

    System.out.println("skip-toSet: "
            + input.parallelStream().filter(x -> x > 0)
                .skip(1)
                .collect(Collectors.toSet()));

Además, el método skip () en Stream nos da una pista:

Si bien {@code skip ()} es generalmente una operación barata en tuberías de flujo secuencial, puede ser bastante costoso en tuberías paralelas ordenadas

y

El uso de una fuente de flujo no ordenada (como {@link #generate (Proveedor)}) o la eliminación de la restricción de pedidos con {@link #unordered ()} puede dar lugar a aceleraciones significativas

Cuando usas

Collectors.toCollection(HashSet::new)

está creando un recopilador "ordenado" normal (uno sin la característica SIN ORDENAR), lo que para mí significa que le importa el orden y, por lo tanto, los elementos se extraen en orden y obtiene el comportamiento esperado.

Answer 2

Recuerde que el objetivo de los indicadores de flujo (ORDENADO, CLASIFICADO, TAMAÑO, DISTINTO) es permitir que las operaciones eviten realizar trabajos innecesarios. Ejemplos de optimizaciones que involucran banderas de flujo son:

• Si sabemos que la secuencia ya está ordenada, sorted() es un no-op;
• Si conocemos el tamaño de la secuencia, podemos preasignar una matriz del tamaño correcto en toArray() , evitando una copia;
• Si sabemos que la entrada no tiene un orden de encuentro significativo, no necesitamos tomar medidas adicionales para preservar el orden de encuentro.

Cada etapa de una tubería tiene un conjunto de banderas de flujo. Las operaciones intermedias pueden inyectar, preservar o borrar banderas de flujo. Por ejemplo, el filtrado conserva la ordenación / distinción pero no el tamaño; el mapeo conserva el tamaño pero no el orden o la distinción. La ordenación inyecta la ordenación. El tratamiento de las banderas para operaciones intermedias es bastante sencillo, porque todas las decisiones son locales.

El tratamiento de las banderas para operaciones terminales es más sutil. ORDERED es el indicador más relevante para operaciones terminales. Y si una operación terminal NO ESTÁ ORDENADA, entonces propagamos hacia atrás lo desordenado.

¿Por qué hacemos esto? Bueno, considere esta tubería:

set.stream()
   .sorted()
   .forEach(System.out::println);

Dado que forEach no está obligado a operar en orden, el trabajo de ordenar la lista es un esfuerzo completamente desperdiciado. Entonces, propagamos esta información (hasta que llegamos a una operación de cortocircuito, como el limit ), para no perder esta oportunidad de optimización. Del mismo modo, podemos usar una implementación optimizada de secuencias distinct en secuencias no ordenadas.

¿Se pretende este comportamiento o es un error?

Sí :) Se pretende la propagación hacia atrás, ya que es una optimización útil que no debería producir resultados incorrectos. Sin embargo, la parte del error es que estamos propagando más allá de un skip anterior, que no deberíamos. Entonces, la propagación hacia atrás de la bandera UNORDERED es demasiado agresiva, y eso es un error. Publicaremos un error.

En caso afirmativo, ¿está documentado en alguna parte?

Debe ser solo un detalle de implementación; si se implementara correctamente, no lo notarías (excepto que tus transmisiones son más rápidas).