funciona - treeset java example

TreeSet vs Java 8 Streams rendimiento

Question

¿De qué manera es más eficiente procesar una colección distinta y ordenada?

1. Bucle mejorado con TreeSet

Set<MyObj> ret = new TreeSet<>();
for (Foo foo : foos)
ret.add(new MyObj(foo));

2. Sencillo Stream

List<MyObj> ret = foos.stream().map(MyObj::new)
.distinct().sorted()
.collect(Collectors.toList());

3. TreeSet Stream

Set<MyObj> ret = foos.stream().map(MyObj::new)
.collect(Collectors.toCollection(TreeSet::new));

La primera forma parece ser la menos elegante y fácil de leer. La segunda forma me hace temer que distinct y sorted procesarán la transmisión dos veces. La última forma se siente bien, pero ¿cuál es la sobrecarga del TreeSet en una transmisión?

¿Alguna pista? Gracias.

Answer 1

Analisis inicial

A juzgar por el código fuente de Stream API, mi conjetura inicial sería: para muchos elementos, el flujo simple (2) debería ser el más rápido, superando significativamente a la versión TreeSet (1), luego el flujo TreeSet (3) debería seguir un poco más atrás. Para conjuntos de datos cortos (1) probablemente sería mejor que (2), que es mejor que (3), porque la creación de Stream agrega cierta sobrecarga. La secuencia distinta ordenada funciona aproximadamente así:

Set<MyObj> set = new HashSet<>();
List<MyObj> result = new ArrayList<>();
for (Foo foo : foos) {
MyObj myObj = new MyObj(foo);
if(set.add(myObj))
result.add(myObj);
}
result.sort(null);
return result;

Agreguemos esta implementación como (4). Utiliza HashSet para verificar si los resultados son distintos, los agrega al contenedor intermedio y luego los ordena. Esto debería ser más rápido que mantener TreeSet ya que no necesitamos mantener el orden después de cada inserción (lo que hace TreeSet , posiblemente rebalanceando el árbol). La implementación real de Stream sería algo menos eficiente, ya que no puede ordenar la lista resultante en el lugar. En su lugar, crea un contenedor intermedio, lo ordena y luego vuelca el resultado en la lista final utilizando una serie de llamadas list.add .

El resultado podría depender del número de elementos en la colección inicial de foos y también del número de elementos distintos. Lo llamo diversidad: diversidad = 1 significa que aproximadamente cada elemento es diferente; diversidad = 0.5 significa que cada elemento se repite aproximadamente dos veces. Además, el resultado puede depender en gran medida del orden inicial de los elementos: los algoritmos de clasificación podrían ser un orden de magnitud más rápido cuando los datos de entrada están preconfigurados o casi preestablecidos.

Configuración experimental

Así que vamos a parametrizar nuestras pruebas de la siguiente manera:

• Tamaño (número de elementos en foos ): 10, 1000, 100000
• Diversidad (fracción de diferentes): 1, 0.5, 0.2
• preclasificado: verdadero, falso

Supongo que Foo solo contiene un campo int . Por supuesto, el resultado puede depender en gran medida de compareTo , equals y hashCode implementación de la clase Foo , porque las versiones (2) y (4) usan equals y hashCode mientras que las versiones (1) y (3) usan compareTo . Lo haremos simplemente:

@Override
public int hashCode() {
return x;
}
@Override
public boolean equals(Object o) {
return this == o || (o != null && getClass() == o.getClass() && x == ((Foo) o).x);
}
@Override
public int compareTo(Foo o) {
return Integer.compare(x, o.x);
}

Los elementos preclasificados se pueden generar a través de:

foos = IntStream.range(0, size)
.mapToObj(x -> new Foo((int)(x*diversity)))
.collect(Collectors.toList());

Se pueden generar elementos aleatorios a través de:

foos = new Random().ints(size, 0, (int) (size * diversity))
.mapToObj(Foo::new)
.collect(Collectors.toList());

Usando JMH 1.13 y JDK 1.8.0_101, VM 25.101-b13 64bit para realizar mediciones

Resultados

Presorted (todos los tiempos están en μs):

diversity size (1) (2) (3) (4)
1 10 0.2 0.5 0.3 0.2
1 1000 48.0 36.0 53.0 24.2
1 100000 14165.7 4759.0 15177.3 3341.6
0.5 10 0.2 0.3 0.2 0.2
0.5 1000 36.9 23.1 41.6 20.1
0.5 100000 11442.1 2819.2 12508.7 2661.3
0.2 10 0.1 0.3 0.2 0.2
0.2 1000 32.0 13.0 29.8 16.7
0.2 100000 8491.6 1969.5 8971.9 1951.7

No preclasificado:

diversity size (1) (2) (3) (4)
1 10 0.2 0.4 0.2 0.3
1 1000 72.8 77.4 73.6 72.7
1 100000 21599.9 16427.1 22807.8 16322.2
0.5 10 0.2 0.3 0.2 0.2
0.5 1000 64.8 46.9 69.4 45.5
0.5 100000 20335.2 11190.3 20658.6 10806.7
0.2 10 0.1 0.3 0.2 0.2
0.2 1000 48.0 19.6 56.7 22.2
0.2 100000 16713.0 5533.4 16885.0 5930.6

Discusión

Mis conjeturas iniciales fueron en general correctas. Para datos preclasificados (2) y (4) son tiempos mejores cuando tenemos 100,000 elementos. La diferencia se hace aún mayor cuando tenemos muchos duplicados, ya que no aumentan el tiempo de clasificación y la inserción duplicada en HashSet es mucho más eficiente que la inserción duplicada en TreeSet . Para los datos aleatorios, la diferencia es menos llamativa ya que el rendimiento de TreeSet depende mucho menos del orden de los datos de entrada que el algoritmo de TimSort (que Java utiliza para ordenar listas y matrices). Para conjuntos de datos pequeños, TreeSet es rápido, pero el uso de la versión (4) también podría ser competitivo.

Un código fuente de referencia junto con resultados en bruto está disponible here .

Answer 2

Es difícil dar una buena respuesta sin analizar la entrada. De todos modos voy a compartir mis resultados:

Le hice a Foo un contenedor para un solo long , y MyObj un contenedor para un solo Foo . También hice que todas las pruebas terminaran con la copia de datos en una matriz simple. También he añadido dos enfoques:

4). Matriz simple

@Benchmark
public void simpleArray(Blackhole bh) {
MyObj[] ret = new MyObj[foos.size()];
for (int i=0;i<foos.size();i++)
ret[i] = new MyObj(foos.get(i));
Arrays.sort(ret);
int lastDistinct = 0;
for (int i = 1; i < ret.length; i++) {
if (ret[i].equals(ret[lastDistinct])) {
continue;
}
lastDistinct++;
ret[lastDistinct] = ret[i];
}
MyObj[] ret2 = new MyObj[lastDistinct + 1];
System.arraycopy(ret, 0, ret2, 0, lastDistinct + 1);
bh.consume(ret2);
}

5). Orden inverso de distinct y order de (2):

@Benchmark
public void simpleStream_distinctAfterSort(Blackhole bh) {
List<MyObj> ret = foos.stream().map(MyObj::new)
.sorted().distinct()
.collect(Collectors.toList());
bh.consume(ret.toArray(new MyObj[ret.size()]));
}

Configuración de pruebas:

public static final int MAX_SIZE = 10_000;
public static final long ELEM_THRESHOLD = MAX_SIZE * 10;
private List<Foo> foos;
@Setup
public void init() throws IOException, IllegalAccessException, InstantiationException {
foos = new ArrayList<>(MAX_SIZE);
for (int i = 0; i < MAX_SIZE; i++) {
foos.add(new Foo(ThreadLocalRandom.current().nextLong(ELEM_THRESHOLD)));
}
}

Ahora los resultados con diferente tamaño y umbral:

Size=10_000
Threshold=Size*10
Benchmark Mode Cnt Score Error Units
StreamBenchmark5.enhancedLoop_TreeSet thrpt 2 478,978 ops/s
StreamBenchmark5.simpleArray thrpt 2 591,287 ops/s
StreamBenchmark5.simpleStream thrpt 2 407,556 ops/s
StreamBenchmark5.simpleStream_distinctAfterSort thrpt 2 533,091 ops/s
StreamBenchmark5.treeSetStream thrpt 2 492,709 ops/s
Size=10_000
Threshold=Size/10
StreamBenchmark5.enhancedLoop_TreeSet thrpt 2 937,908 ops/s
StreamBenchmark5.simpleArray thrpt 2 593,983 ops/s
StreamBenchmark5.simpleStream thrpt 2 3344,508 ops/s
StreamBenchmark5.simpleStream_distinctAfterSort thrpt 2 560,652 ops/s
StreamBenchmark5.treeSetStream thrpt 2 1000,585 ops/s
Size=500_000
Threshold=Size*10
Benchmark Mode Cnt Score Error Units
StreamBenchmark5.enhancedLoop_TreeSet thrpt 2 1,809 ops/s
StreamBenchmark5.simpleArray thrpt 2 4,009 ops/s
StreamBenchmark5.simpleStream thrpt 2 2,443 ops/s
StreamBenchmark5.simpleStream_distinctAfterSort thrpt 2 4,141 ops/s
StreamBenchmark5.treeSetStream thrpt 2 2,040 ops/s
Size=500_000
Threshold=Size/10
Benchmark Mode Cnt Score Error Units
StreamBenchmark5.enhancedLoop_TreeSet thrpt 2 5,724 ops/s
StreamBenchmark5.simpleArray thrpt 2 4,567 ops/s
StreamBenchmark5.simpleStream thrpt 2 19,001 ops/s
StreamBenchmark5.simpleStream_distinctAfterSort thrpt 2 4,840 ops/s
StreamBenchmark5.treeSetStream thrpt 2 5,407 ops/s
Size=1_000_000
Threshold=Size/100
Benchmark Mode Cnt Score Error Units
StreamBenchmark5.enhancedLoop_TreeSet thrpt 2 4,529 ops/s
StreamBenchmark5.simpleArray thrpt 2 2,402 ops/s
StreamBenchmark5.simpleStream thrpt 2 35,699 ops/s
StreamBenchmark5.simpleStream_distinctAfterSort thrpt 2 2,232 ops/s
StreamBenchmark5.treeSetStream thrpt 2 4,889 ops/s

Como se puede ver, dependiendo de la cantidad de duplicados, es posible que haya cambios de algoritmo. El enfoque más equilibrado es TreeSet (3), sin embargo, el más rápido es casi siempre el flujo simple (con order y ubicación distinct correspondientes a los datos de entrada).

Aquí está la fuente de prueba si estás dispuesto a jugar un poco. Necesitarás JMH .

Answer 3

Si solo necesita una serie ordenada de Foo y desea hacerlo rápido, no debe usar TreeSet. Es sobreingeniería. El uso de flujos cuando se necesita una alta velocidad tampoco es una buena idea.

Promover. Existe un método List.sort que funciona de manera efectiva para ArrayList (de forma predeterminada, copia los elementos en una matriz temporal y los ordena, pero ArrayList ya tiene una matriz dentro).

Así que el código efectivo es una variación de la primera:

List<MyObj> ret = new ArrayList<>(foos.size());
for (Foo foo : foos) {
ret.add(new MyObj(foo));
}
ret.sort();

Lo siento por no tener puntos de referencia, hazlo tú mismo