Por que o processamento de uma matriz classificada é*mais lento*que uma matriz não classificada?(ArrayList.indexOf de Java)




performance (2)

O título é em referência a Por que é mais rápido processar uma matriz ordenada do que uma matriz não classificada?

Este é um efeito de predição de ramo também? Cuidado: aqui o processamento para o array ordenado é mais lento !!

Considere o seguinte 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);

    ...
}

Isso imprime um valor de cerca de 720 na minha máquina.

Agora, se eu ativar a chamada de ordenação de coleções, esse valor cairá para 142. Por que?!?

Os resultados são conclusivos, eles não mudam se eu aumentar o número de iterações / tempo.

A versão do Java é 1.8.0_71 (Oracle VM, 64 bits), em execução no Windows 10, teste JUnit no Eclipse Mars.

ATUALIZAR

Parece estar relacionado ao acesso contíguo à memória (objetos duplos acessados ​​em ordem seqüencial vs. ordem aleatória). O efeito começa a desaparecer para mim por comprimentos de array de cerca de 10k e menos.

Graças a assylias para fornecer os 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 um exemplo simples que confirma a resposta por wero e a resposta por apangin (+1!): O seguinte faz uma comparação simples de ambas as opções:

  • Criando números aleatórios e classificando-os opcionalmente
  • Criando números sequenciais e embaralhando-os opcionalmente

Também não é implementado como um benchmark JMH, mas semelhante ao código original, com apenas pequenas modificações para observar o efeito:

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);
    }

}

A saída da minha máquina é

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

bem mostrando que os tempos são exatamente os opostos de outro: se números aleatórios são classificados, então a versão ordenada é mais lenta. Se os números sequenciais forem embaralhados, a versão embaralhada será mais lenta.


Eu acho que estamos vendo o efeito de erros no cache de memória:

Quando você cria a lista não classificada

for (int i = 0; i < LIST_LENGTH; i++) {
    list.add(r.nextDouble());
}

todos os duplos provavelmente estão alocados em uma área de memória contígua. Iterar por meio disso produzirá poucas falhas de cache.

Por outro lado, na lista ordenada, as referências apontam para a memória de maneira caótica.

Agora, se você criar uma lista classificada com memória contígua:

Collection.sort(list);
List<Double> list2 = new ArrayList<>();
for (int i = 0; i < LIST_LENGTH; i++) {
    list2.add(new Double(list.get(i).doubleValue()));
}

essa lista classificada tem o mesmo desempenho que a original (meu tempo).







arraylist