for - Java 8 findFirst y orden de encuentro

jdk 11

Question

Los JavaDocs para findFirst dicen que si el flujo tiene un orden de encuentro, el primer elemento siempre será devuelto, pero si el flujo no tiene un orden de encuentro, se puede devolver cualquier elemento.

Intento demostrar cómo funciona esto en una transmisión sin un orden de encuentro, pero no puedo conseguir que devuelva nada más que el primer elemento real.

Traté de agregar los elementos a un Set , que no tiene un orden de encuentro definido:

    Set<String> words = new HashSet<>();
    words.addAll(Arrays.asList("this", "is", "a", "stream", "of", "strings"));
    Optional<String> firstString = words.stream()
            .findFirst();
    System.out.println(firstString);

Cada vez que corro, obtengo a como la primera cadena. Luego intenté hacer un Collections.shuffle en la List antes de agregarlo al Set , pero eso no cambió nada.

    List<String> wordList = Arrays.asList("this", "is", "a", "stream", "of", "strings");
    words = new HashSet<>();
    words.addAll(wordList);
    firstString = words.stream()
            .findFirst();
    System.out.println(firstString);

Aún recibo la palabra a todo el tiempo.

Luego traté de utilizar el método unordered de BaseStream , que afirma devolver una secuencia sin orden de encuentro, pero sin diferencia:

    firstString = Stream.of("this", "is", "a", "stream", "of", "strings")
            .unordered()
            .findFirst();
    System.out.println(firstString);

Ahora entiendo la palabra todo el tiempo. ¿Me estoy perdiendo de algo? ¿Hay alguna forma de demostrar que findFirst en un flujo desordenado devuelve valores diferentes?

Answer 1

Al marcar el flujo como no ordenado, en realidad no lo hace como tal (no ha hecho que el pedido en su Conjunto sea diferente), sino que está eliminando cualquier restricción que de otro modo podría imponer un flujo ordenado.

La forma de probar que esto arrojará resultados diferentes es usar una transmisión paralela.

 Set<String> words = new HashSet<>();
    words.addAll(Arrays.asList("this", "is", "a", "stream", "of", "strings"));
    Optional<String> firstString = words.stream().parallel()
            .findFirst();
    System.out.println(firstString);

Ejecutando esto algunas veces, muestra:

  Optional[strings] and then Optional[this]

Cambiar su conjunto a una lista y ejecutarlo en paralelo preservará el orden:

 List<String> words = new ArrayList<>();
    words.addAll(Arrays.asList("this", "is", "a", "stream", "of", "strings"));
    Optional<String> firstString = words.stream().parallel()
            .findFirst();
    System.out.println(firstString); // always Optional[this]

El absoluto debe leer aquí es la gran respuesta de Holger

Answer 2

Bueno, "cualquiera" incluye la posibilidad de "primero". Por supuesto, la implementación de Stream no desperdicia esfuerzos en aleatorizar los datos, por lo que para muchos casos, especialmente con la ejecución secuencial, seguirá siendo el primer elemento, si podemos llamarlo de esa manera (ya que sin un orden, hay ningún primer elemento distinguido).

Sus mejores posibilidades de exhibir resultados diferentes para findFirst son con Streams paralelos. Pero incluso allí, no todas las combinaciones de operaciones son adecuadas para exhibir la falta de orden.

Un punto es que en la implementación actual , la operación findFirst() no cambia su comportamiento cuando Stream está desordenado, es decir, no intenta ser como findAny() . Todavía puede exhibir un comportamiento impredecible debido a la fuente del flujo, pero si su fuente es Stream.of("this", "is", "a", "stream", "of", "strings") , es decir, un secuencia inmutable de un tamaño conocido, ya tiene el mejor rendimiento paralelo posible, por lo que simplemente no hay forma de obtener un beneficio del encadenado unordered() , por lo tanto, la implementación actual no cambia su comportamiento.

Puede sorprender, pero esto incluso se aplica a un HashSet hasta cierto punto. Si bien tiene un orden no especificado, habrá un orden real dentro de su matriz de respaldo en algún punto del tiempo y siempre que no modifique el Set , no habrá ninguna razón para mezclar estas entradas, por lo que para un HashSet particular Por ejemplo, puede obtener repetidamente el mismo "primer" elemento, aunque no se especifica cuál e incluso dentro de un único tiempo de ejecución, otra instancia de HashSet represente los mismos contenidos, pero que tenga un historial diferente, puede tener un orden diferente.

Un ejemplo de una operación que se sabe que saca un beneficio de las características desordenadas es distinct . Si bien tiene que clasificar los duplicados, tiene que mantener el primero encontrado de elementos iguales, si hace una diferencia notable. Esto puede degradar significativamente el rendimiento, por lo tanto, la implementación intentará obtener un beneficio de inmediato si la transmisión no está ordenada. P.ej

List<String> equal=IntStream.range(0, 100)
    .mapToObj(i->new String("test")) // don''t do this in normal code
    .collect(Collectors.toList());
Map<String, Integer> map = IntStream.range(0, equal.size())
    .collect(IdentityHashMap::new, (m,i)->m.put(equal.get(i),i), Map::putAll);

equal.parallelStream().distinct().map(map::get)
     .findFirst().ifPresent(System.out::println);

Esto crea un grupo de instancias String equal pero distinguibles (que normalmente no debería hacer), las registra con su número posicional en IdentityHashMap , para que podamos averiguar qué instancia distinct ha conservado. Como el código anterior utiliza una secuencia ordenada creada por una List , imprime de forma consistente 0 , independientemente de la frecuencia con que lo ejecute.

A diferencia de,

equal.parallelStream().unordered().distinct().map(map::get)
     .findFirst().ifPresent(System.out::println);

imprimirá números arbitrarios del rango, ya que hemos liberado el contrato ordenado y le permitimos elegir cualquiera de las cadenas iguales.

Como ya se señaló anteriormente, esta es toda la implementación específica . Nunca debe suponer que una operación puede obtener un beneficio y, por lo tanto, cambiará su comportamiento para las secuencias desordenadas. La explicación anterior solo pretendía ilustrar por qué, a veces, el comportamiento de una implementación particular podría no cambiar para la transmisión desordenada. Sin embargo, todavía podría ser en la próxima versión o en una implementación JRE diferente.

Answer 3

Como @Eugene ya mencionó, llamar unordered no necesariamente cambia el orden físico real de los elementos. No olvide que unordered es una operación intermedia que no hace nada hasta que se invoca una operación de terminal.

Por lo tanto, tiendo a pensarlo de esta manera:

1. Al crear un Set contiene los elementos "this", "is", "a", "stream", "of", "strings" , sucede que el primer elemento en el Set al iterar sobre él es "a" , entonces findFirst simplemente devuelve ese valor.

2. Cuando crea una secuencia usando Stream.of("this", "is", "stream", "of", "strings") , devuelve una secuencia con una restricción de pedido que será respetada por findFirst . La llamada unordered elimina esa restricción, pero el elemento "this" sigue siendo físicamente el primer elemento porque no unordered no necesariamente cambia el orden en la matriz de origen.

Un ejemplo un poco mejor podría ser el siguiente:

Set<String> words = new HashSet<>();
words.addAll(Arrays.asList("this", "is", "stream", "of", "strings"));

Optional<String> firstString1 = words.stream().findFirst();
// Optional[strings]
System.out.println(firstString1);

Optional<String> firstString2 = words.stream()
                                     .sorted().findFirst();
// Optional[is]
System.out.println(firstString2);

Optional<String> firstString3 = Stream.of("this", "is", "stream", "of", "strings")
                                      .findFirst();
// Optional[this]
System.out.println(firstString3);

Optional<String> firstString4 = Stream.of("this", "is", "stream", "of", "strings")
                                      .unordered().findFirst();
// Optional[this]
System.out.println(firstString4);

Observe cómo el método sorted() cambia el resultado porque impone la restricción de ordenación, a diferencia del método unordered que no tuvo ningún efecto.

Answer 4

Holger ya ha explicado hábilmente la situación. (+1) Me gustaría ofrecer una demostración de HashSet instancias de HashSet que tienen los mismos contenidos pero que tienen un orden de iteración diferente. Primero creamos un conjunto como antes:

    List<String> wordList = Arrays.asList("this", "is", "a", "stream", "of", "strings");
    Set<String> words = new HashSet<>(wordList);

Creamos otro conjunto de palabras, agregamos un montón de cosas (no importa exactamente qué es) y luego las eliminamos:

    Set<String> words2 = new HashSet<>(wordList);
    IntStream.range(0, 50).forEachOrdered(i -> words2.add(String.valueOf(i)));
    words2.retainAll(wordList);

Si inspeccionamos los resultados de la siguiente manera:

    System.out.println(words.equals(words2));
    System.out.println(words);
    System.out.println(words2);

podemos ver en el resultado que los conjuntos son iguales pero se repiten en un orden diferente:

true
[a, strings, stream, of, this, is]
[this, is, strings, stream, of, a]

Como se indicó en otra parte, si obtienes un flujo de estos y llamas a findFirst() , el resultado es el primer elemento en orden de iteración, que claramente difiere entre estos conjuntos.

Lo que sucedió es que al agregar y eliminar un conjunto de elementos, hemos causado que el conjunto aumente su tamaño de tabla interna, lo que requiere que los elementos se vuelvan a generar. Los elementos originales terminan en diferentes posiciones relativas en la nueva tabla, incluso después de que los nuevos elementos hayan sido eliminados.

Aunque los HashSets no tienen un orden de iteración especificado, es probable que el orden sea repetible (e incluso predecible) si el conjunto se inicializa con los mismos contenidos de la misma manera todo el tiempo. Por lo tanto, decimos que la transmisión de un conjunto no tiene un orden de encuentro definido, aunque el orden suele ser el mismo cada vez.

Tenga en cuenta que en JDK 9, los nuevos conjuntos inmutables (y los mapas) están realmente aleatorizados, por lo que sus órdenes de iteración cambiarán de ejecución a ejecución, incluso si se inicializan de la misma manera todo el tiempo.