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

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

success: function (data) {
    response($.map(data.slice (0,10), function(item) {
    return {
    value: item.nome
    };
    }));
},
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
поделиться
Другие вопросы по тегам:

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