Original

Вот пример C++ кода, который выглядит очень странно. Почему-то, когда данные отсортированы код выполняется почти в шесть раз быстрее.

<!-- language: lang-cpp -->

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

    int main()
    {
        // Заполнение данными
        const unsigned arraySize = 32768;
        int data[arraySize];

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

        // !!! С этой строкой следующий цикл работает быстрее
        std::sort(data, data + arraySize);

        // Проверка
        clock_t start = clock();
        long long sum = 0;

        for (unsigned i = 0; i < 100000; ++i)
        {
            // Основной цикл
            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;
    }

 - Без `std::sort(data, data + arraySize);`, код выполняется 11.54 секунды.
 - С отсортированными данными - 1.93 секунды.

Сначала, я думал что-то не так с языком или компилятором. Поэтому я попробовал использовать Java.

<!-- language: lang-java -->

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

    public class Main
    {
        public static void main(String[] args)
        {
            // Заполнение данными
            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;

            // !!! С этой строкой следующий цикл работает быстрее
            Arrays.sort(data);

            // Проверка
            long start = System.nanoTime();
            long sum = 0;

            for (int i = 0; i < 100000; ++i)
            {
                // Основной цикл
                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);
        }
    }

В итоге получились похожие результаты, но с меньшим разрывом.

----------

Первая мысль была о том, что при сортировке данные попадают в кэш, но потом я подумал, что это глупо, потому что массив был только что создан.

 - Что происходит?
 - Почему отсортированный массив обрабатывается быстрее, чем не отсортированный?

---
<sub>Перевод вопроса [Why is it faster to process a sorted array than an unsorted array?][1]</sub>


  [1]: http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array