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

Question

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
 */

Answer 1

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.

Answer 2

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).

Answer 3

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