25698 votes

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

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.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X