Почему обработка отсортированного массива быстрее, чем обработка несортированного массива?

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

#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;
}
  • Без std::sort(data, data + arraySize); код выполняется за 11,54 секунды.
  • С отсортированными данными код запускается за 1,93 секунды.

Изначально я думал, что это может быть просто аномалией языка или компилятора, поэтому я попробовал 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);
    }
}

с похожим, но менее экстремальным результатом.


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

  • Что происходит?
  • Почему обработка отсортированного массива быстрее, чем обработка несортированного массива? Код суммирует некоторые независимые термины, поэтому порядок не должен иметь значения.
23397
задан Palec 1 July 2019 в 15:01
поделиться

3 ответа

Как упомянуто таким количеством людей передо мной с большим количеством детали; однако проще говоря это следующим образом

, можно принять решение быстрее вначале, взять, например, поиск числа, в этом случае, если Вы ищете цифру меньше, чем что-то существующее в массиве, с тех пор, массив отсортирован, Вы устранили бы половину поиска, это будет O (1/2).

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

0
ответ дан 22 November 2019 в 19:37
поделиться

Этот вопрос базирован в Моделях Предсказания ветвлений на центральных процессорах. Я рекомендовал бы читать этот отчет:

Увеличение Уровня Вызова команды через Несколько Предсказание ветвлений и Кэш Адреса Ответвления

при сортировке элементов IR не мог быть побеспокоен для выборки всех инструкций ЦП, снова и снова, Это выбирает их от кэша.

4
ответ дан 22 November 2019 в 19:37
поделиться

Ответ Bjarne Stroustrup к этому вопросу:

, Который походит на вопрос об интервью. Действительно ли это верно? Как Вы знали бы? Это - плохая идея ответить на вопросы об эффективности без первого выполнения некоторых измерений, таким образом, важно знать, как иметь размеры.

Так, я попробовал вектором миллиона целых чисел и добрался:

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

я выполнил это несколько раз, чтобы быть уверенным. Да, явление реально. Мой код клавиши был:

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1 — t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

, По крайней мере, явление реально с этим компилятором, стандартной библиотекой и настройками оптимизатора. Различные реализации могут и действительно давать различные ответы. На самом деле кто-то действительно делал более систематическое исследование (быстрый веб-поиск найдет его), и большинство реализаций показывает тот эффект.

Одной причиной является предсказание ветвлений: ключевая операция в алгоритме сортировки “if(v[i] < pivot]) …” или эквивалентна. Для отсортированной последовательности, что тест всегда верен, тогда как для случайной последовательности выбранное ответвление варьируется случайным образом.

Другая причина состоит в том, что, когда вектор уже отсортирован, мы никогда не должны перемещать элементы в их правильное положение. Эффект этих небольших деталей является фактором пять или шесть, что мы видели.

Quicksort (и сортирующий в целом) является сложным исследованием, которое притянуло некоторые самые большие умы информатики. Хорошая функция вида является результатом и выбора хорошего алгоритма и уделения внимания аппаратной производительности в ее реализации.

, Если Вы хотите написать эффективный код, необходимо знать немного об архитектуре машины.

16
ответ дан 22 November 2019 в 19:37
поделиться
Другие вопросы по тегам:

Похожие вопросы: