maximo - ¿Por qué el procesamiento de una matriz ordenada*es más lento*que una matriz no ordenada?(Java''s ArrayList.indexOf)
cual es el tamaño maximo de un arreglo en java (3)
El título hace referencia a ¿Por qué es más rápido procesar una matriz ordenada que una matriz sin clasificar?
¿Es este también un efecto de predicción de rama? Cuidado: ¡aquí el procesamiento de la matriz ordenada es más lento !
Considere el siguiente código:
private static final int LIST_LENGTH = 1000 * 1000;
private static final long SLOW_ITERATION_MILLIS = 1000L * 10L;
@Test
public void testBinarySearch() {
Random r = new Random(0);
List<Double> list = new ArrayList<>(LIST_LENGTH);
for (int i = 0; i < LIST_LENGTH; i++) {
list.add(r.nextDouble());
}
//Collections.sort(list);
// remove possible artifacts due to the sorting call
// and rebuild the list from scratch:
list = new ArrayList<>(list);
int nIterations = 0;
long startTime = System.currentTimeMillis();
do {
int index = r.nextInt(LIST_LENGTH);
assertEquals(index, list.indexOf(list.get(index)));
nIterations++;
} while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
long duration = System.currentTimeMillis() - startTime;
double slowFindsPerSec = (double) nIterations / duration * 1000;
System.out.println(slowFindsPerSec);
...
}
Esto imprime un valor de alrededor de 720 en mi máquina.
Ahora, si activo la llamada de clasificación de colecciones, ese valor se reduce a 142. ¿Por qué?
Los resultados son concluyentes, no cambian si aumento el número de iteraciones / tiempo.
La versión de Java es 1.8.0_71 (Oracle VM, 64 bit), que se ejecuta en Windows 10, prueba JUnit en Eclipse Mars.
ACTUALIZAR
Parece estar relacionado con el acceso contiguo a la memoria (objetos dobles a los que se accede en orden secuencial versus en orden aleatorio). El efecto comienza a desaparecer para mí para longitudes de matriz de alrededor de 10k y menos.
Gracias a Assylias por proporcionar los resultados :
/**
* Benchmark Mode Cnt Score Error Units
* SO35018999.shuffled avgt 10 8.895 ± 1.534 ms/op
* SO35018999.sorted avgt 10 8.093 ± 3.093 ms/op
* SO35018999.sorted_contiguous avgt 10 1.665 ± 0.397 ms/op
* SO35018999.unsorted avgt 10 2.700 ± 0.302 ms/op
*/
Como un ejemplo simple que confirma la respuesta de wero y la respuesta de apangin (+1!): A continuación se realiza una comparación simple de ambas opciones:
- Crear números aleatorios y ordenarlos opcionalmente
- Crear números secuenciales y barajarlos opcionalmente
Tampoco se implementa como un punto de referencia JMH, pero es similar al código original, con solo ligeras modificaciones para observar el efecto:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
public class SortedListTest
{
private static final long SLOW_ITERATION_MILLIS = 1000L * 3L;
public static void main(String[] args)
{
int size = 100000;
testBinarySearchOriginal(size, true);
testBinarySearchOriginal(size, false);
testBinarySearchShuffled(size, true);
testBinarySearchShuffled(size, false);
}
public static void testBinarySearchOriginal(int size, boolean sort)
{
Random r = new Random(0);
List<Double> list = new ArrayList<>(size);
for (int i = 0; i < size; i++)
{
list.add(r.nextDouble());
}
if (sort)
{
Collections.sort(list);
}
list = new ArrayList<>(list);
int count = 0;
int nIterations = 0;
long startTime = System.currentTimeMillis();
do
{
int index = r.nextInt(size);
if (index == list.indexOf(list.get(index)))
{
count++;
}
nIterations++;
}
while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
long duration = System.currentTimeMillis() - startTime;
double slowFindsPerSec = (double) nIterations / duration * 1000;
System.out.printf("Size %8d sort %5s iterations %10.3f count %10d/n",
size, sort, slowFindsPerSec, count);
}
public static void testBinarySearchShuffled(int size, boolean sort)
{
Random r = new Random(0);
List<Double> list = new ArrayList<>(size);
for (int i = 0; i < size; i++)
{
list.add((double) i / size);
}
if (!sort)
{
Collections.shuffle(list);
}
list = new ArrayList<>(list);
int count = 0;
int nIterations = 0;
long startTime = System.currentTimeMillis();
do
{
int index = r.nextInt(size);
if (index == list.indexOf(list.get(index)))
{
count++;
}
nIterations++;
}
while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
long duration = System.currentTimeMillis() - startTime;
double slowFindsPerSec = (double) nIterations / duration * 1000;
System.out.printf("Size %8d sort %5s iterations %10.3f count %10d/n",
size, sort, slowFindsPerSec, count);
}
}
La salida en mi máquina es
Size 100000 sort true iterations 8560,333 count 25681
Size 100000 sort false iterations 19358,667 count 58076
Size 100000 sort true iterations 18554,000 count 55662
Size 100000 sort false iterations 8845,333 count 26536
mostrando muy bien que los tiempos son exactamente los opuestos de otro: si se ordenan números aleatorios, entonces la versión ordenada es más lenta. Si se barajan números secuenciales, la versión barajada es más lenta.
Creo que estamos viendo el efecto de errores de memoria caché:
Cuando crea la lista sin ordenar
for (int i = 0; i < LIST_LENGTH; i++) {
list.add(r.nextDouble());
}
todos los dobles probablemente se asignan en un área de memoria contigua. La iteración a través de esto producirá algunos errores de caché.
Por otro lado, en la lista ordenada, las referencias apuntan a la memoria de manera caótica.
Ahora, si crea una lista ordenada con memoria contigua:
Collection.sort(list);
List<Double> list2 = new ArrayList<>();
for (int i = 0; i < LIST_LENGTH; i++) {
list2.add(new Double(list.get(i).doubleValue()));
}
Esta lista ordenada tiene el mismo rendimiento que la original (mi tiempo).
Parece un efecto de almacenamiento en caché / captación previa.
La pista es que compara dobles (objetos), no dobles (primitivas).
Cuando asigna objetos en un hilo, normalmente se asignan secuencialmente en la memoria.
Entonces, cuando
indexOf
escanea una lista, pasa por direcciones de memoria secuenciales.
Esto es bueno para la heurística de captación previa de caché de CPU.
Pero después de ordenar la lista, todavía tiene que hacer el mismo número de búsquedas de memoria en promedio, pero esta vez el acceso a la memoria estará en orden aleatorio.
ACTUALIZAR
Aquí está el punto de referencia para demostrar que el orden de los objetos asignados es importante.
Benchmark (generator) (length) (postprocess) Mode Cnt Score Error Units
ListIndexOf.indexOf random 1000000 none avgt 10 1,243 ± 0,031 ms/op
ListIndexOf.indexOf random 1000000 sort avgt 10 6,496 ± 0,456 ms/op
ListIndexOf.indexOf random 1000000 shuffle avgt 10 6,485 ± 0,412 ms/op
ListIndexOf.indexOf sequential 1000000 none avgt 10 1,249 ± 0,053 ms/op
ListIndexOf.indexOf sequential 1000000 sort avgt 10 1,247 ± 0,037 ms/op
ListIndexOf.indexOf sequential 1000000 shuffle avgt 10 6,579 ± 0,448 ms/op