Pourquoi le traitement d'un tableau trié de plus qu'un tableau non trié?

Question

Voici un morceau de C++ le code qui semble très étrange. Pour une raison étrange, le tri des données miraculeusement rend le code près de six fois plus rapide:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

• Sans std::sort(data, data + arraySize);, le code s'exécute dans 11.54 secondes.
• Avec les données triées, le code s'exécute dans 1.93 secondes.

---

Au départ, j'ai pensé que cela pourrait être juste une langue ou le compilateur anomalie.

Donc je l'ai essayé en Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

Avec un peu semblable, mais moins extrême résultat.

---

Ma première pensée a été que le tri regroupe les données dans le cache, mais ma prochaine pensée était de savoir comment stupide que est, car le tableau a été qui vient d'être généré.

• Ce qui se passe?
• Pourquoi un tableau trié de plus qu'un tableau non trié?
• Le code est en résumant certains indépendant et l'ordre ne devrait pas d'importance.