El título hace referencia a ¿Por qué es más rápido procesar una matriz ordenada que una matriz no ordenada?
¿También es este 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 ordenación de colecciones, ese valor desciende 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 bits), que se ejecuta en Windows 10, prueba JUnit en Eclipse Mars.
ACTUALIZAR
Parece estar relacionado con el acceso a la memoria contigua (objetos dobles a los que se accede en orden secuencial frente a en orden aleatorio). El efecto comienza a desaparecer para mí para longitudes de matriz de alrededor de 10k y menos.
Gracias a Assylias por brindar 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
*/
fuente
System.currentTimeMillis
yassertEquals
. No hay iteraciones de calentamiento, no hay iteraciones en general, confía en una cantidad constante de tiempo y verifica cuánto se hizo en ese tiempo. Lo siento, pero esta prueba es efectivamente inútil.Respuestas:
Parece un efecto de caché / recuperación previa.
La pista es que comparas Dobles (objetos), no dobles (primitivas). Cuando asigna objetos en un subproceso, 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 la misma cantidad de búsquedas de memoria en promedio, pero esta vez el acceso a la memoria será 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
fuente
list.indexOf(list.get(index))
ellist.get(index)
no se beneficia de ninguna manera con la búsqueda previa, ya queindex
es aleatorio. El precio delist.get(index)
es el mismo independientemente del tiempo en que la lista se haya ordenado o no. Lalist.indexOf()
Creo que estamos viendo el efecto de fallas en la memoria caché:
Cuando crea la lista sin clasificar
for (int i = 0; i < LIST_LENGTH; i++) { list.add(r.nextDouble()); }
lo más probable es que todos los dobles estén asignados en un área de memoria contigua. Iterar esto producirá pocas pérdidas 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).
fuente
Como un ejemplo simple que confirma la respuesta de wero y la respuesta de apangin (¡+1!): Lo siguiente hace una comparación simple de ambas opciones:
Tampoco está implementado como un punto de referencia de 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 otros: si se ordenan números aleatorios, la versión ordenada es más lenta. Si se barajan números secuenciales, la versión barajada es más lenta.
fuente