instead - Java Streams: ¿Cómo hacer un eficiente "distinto y ordenado"?

stream vs foreach

Question

Supongamos que tengo un Stream<T> y quiero obtener solo elementos distintos y ordenados.

El enfoque ingenuo sería hacer lo siguiente:

Stream.of(...)
.sorted()
.distinct()

O, tal vez al revés:

Stream.of(...)
.distinct()
.sorted()

Dado que la implementación de ambos no es realmente accesible por el código fuente del JDK, me preguntaba sobre el posible consumo de memoria y las implicaciones de rendimiento.

¿O sería aún más eficiente escribir mi propio filtro como el siguiente?

Stream.of(...)
.sorted()
.filter(noAdjacentDuplicatesFilter())
public static Predicate<Object> noAdjacentDuplicatesFilter() {
final Object[] previousValue = {new Object()};
return value -> {
final boolean takeValue = !Objects.equals(previousValue[0], value);
previousValue[0] = value;
return takeValue;
};
}

Answer 1

Cuando encadena una operación distinct() después de sorted() , la implementación utilizará la naturaleza ordenada de los datos y evitará la creación de un HashSet interno, que se puede demostrar con el siguiente programa

public class DistinctAndSort {
static int COMPARE, EQUALS, HASHCODE;
static class Tracker implements Comparable<Tracker> {
static int SERIAL;
int id;
Tracker() {
id=SERIAL++/2;
}
public int compareTo(Tracker o) {
COMPARE++;
return Integer.compare(id, o.id);
}
public int hashCode() {
HASHCODE++;
return id;
}
public boolean equals(Object obj) {
EQUALS++;
return super.equals(obj);
}
}
public static void main(String[] args) {
System.out.println("adjacent sorted() and distinct()");
Stream.generate(Tracker::new).limit(100)
.sorted().distinct()
.forEachOrdered(o -> {});
System.out.printf("compareTo: %d, EQUALS: %d, HASHCODE: %d%n",
COMPARE, EQUALS, HASHCODE);
COMPARE=EQUALS=HASHCODE=0;
System.out.println("now with intermediate operation");
Stream.generate(Tracker::new).limit(100)
.sorted().map(x -> x).distinct()
.forEachOrdered(o -> {});
System.out.printf("compareTo: %d, EQUALS: %d, HASHCODE: %d%n",
COMPARE, EQUALS, HASHCODE);
}
}

que se imprimirá

adjacent sorted() and distinct()
compareTo: 99, EQUALS: 99, HASHCODE: 0
now with intermediate operation
compareTo: 99, EQUALS: 100, HASHCODE: 200

La operación intermedia, tan simple como el map(x -> x) , no puede ser reconocida por la implementación de Stream , por lo tanto, debe asumir que los elementos podrían no ordenarse con respecto al resultado de la función de mapeo.

No hay garantía de que ocurra este tipo de optimización, sin embargo, es razonable suponer que los desarrolladores de la implementación de Stream no eliminarán esa optimización e incluso intentarán agregar más optimizaciones, por lo que su implementación evitará que su código se beneficie. optimizaciones futuras.

Además, lo que ha creado es un "predicado de estado", que está muy desaconsejado y, por supuesto, se romperá cuando se utilice con una transmisión paralela.

Si no confía en que Stream API realice esta operación de manera suficientemente eficiente, es mejor que implemente esta operación en particular sin la API de Stream.

Answer 2

Descargo de responsabilidad: sé que las pruebas de rendimiento son difíciles y, especialmente, en la JVM que requiere calentamiento y un entorno controlado sin otros procesos en ejecución.

Si lo pruebo, obtengo estos resultados, así que parece que su implementación beneficia la ejecución paralela. (Ejecutando en i7 con 4 núcleos + hyperthreading).

Así que " .distinct().sorted() " parece ser más lento. Según lo previsto / explicado por Holger

Round 1 (Warm up?)
3938
2449
5747
Round 2
2834
2620
3984
Round 3 Parallel
831
4343
6346
Round 4 Parallel
825
3309
6339

Utilizando Código:

package test.test;
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.function.Predicate;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SortDistinctTest {
public static void main(String[] args) {
IntStream range = IntStream.range(0, 6_000_000);
List<Integer> collect = range.boxed().collect(Collectors.toList());
Collections.shuffle(collect);
long start = System.currentTimeMillis();
System.out.println("Round 1 (Warm up?)");
collect.stream().sorted().filter(noAdjacentDuplicatesFilter()).collect(Collectors.counting());
long fst = System.currentTimeMillis();
System.out.println(fst - start);
collect.stream().sorted().distinct().collect(Collectors.counting());
long snd = System.currentTimeMillis();
System.out.println(snd - fst);
collect.stream().distinct().sorted().collect(Collectors.counting());
long end = System.currentTimeMillis();
System.out.println(end - snd);
System.out.println("Round 2");
collect.stream().sorted().filter(noAdjacentDuplicatesFilter()).collect(Collectors.counting());
fst = System.currentTimeMillis();
System.out.println(fst - end);
collect.stream().sorted().distinct().collect(Collectors.counting());
snd = System.currentTimeMillis();
System.out.println(snd - fst);
collect.stream().distinct().sorted().collect(Collectors.counting());
end = System.currentTimeMillis();
System.out.println(end - snd);
System.out.println("Round 3 Parallel");
collect.stream().parallel().sorted().filter(noAdjacentDuplicatesFilter()).collect(Collectors.counting());
fst = System.currentTimeMillis();
System.out.println(fst - end);
collect.stream().parallel().sorted().distinct().collect(Collectors.counting());
snd = System.currentTimeMillis();
System.out.println(snd - fst);
collect.stream().parallel().distinct().sorted().collect(Collectors.counting());
end = System.currentTimeMillis();
System.out.println(end - snd);
System.out.println("Round 4 Parallel");
collect.stream().parallel().sorted().filter(noAdjacentDuplicatesFilter()).collect(Collectors.counting());
fst = System.currentTimeMillis();
System.out.println(fst - end);
collect.stream().parallel().sorted().distinct().collect(Collectors.counting());
snd = System.currentTimeMillis();
System.out.println(snd - fst);
collect.stream().parallel().distinct().sorted().collect(Collectors.counting());
end = System.currentTimeMillis();
System.out.println(end - snd);
}
public static Predicate<Object> noAdjacentDuplicatesFilter() {
final Object[] previousValue = { new Object() };
return value -> {
final boolean takeValue = !Objects.equals(previousValue[0], value);
previousValue[0] = value;
return takeValue;
};
}
}