Почему std :: shuffle медленнее (или даже медленнее) std :: sort?

Рассмотрим простой код, который измеряет время выполнения и количество выполненных перестановок:

#include <iostream>

#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

struct A {
    A(int i = 0) : i(i) {}
    int i;
    static int nSwaps;

    friend void swap(A& l, A& r)
    {
        ++nSwaps;
        std::swap(l.i, r.i);
    }

    bool operator<(const A& r) const
    {
        return i < r.i;
    }
};

int A::nSwaps = 0;

using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::milliseconds;


int main()
{
    std::vector<A> v(10000000);

    std::minstd_rand gen(std::random_device{}());
    std::generate(v.begin(), v.end(), [&gen]() {return gen();});

    auto s = high_resolution_clock::now();
    std::sort(v.begin(), v.end());
    std::cout << duration_cast<milliseconds>(high_resolution_clock::now() - s).count() 
        << "ms with " << A::nSwaps << " swaps\n";

    A::nSwaps = 0;
    s = high_resolution_clock::now();
    std::shuffle(v.begin(), v.end(), gen);
    std::cout << duration_cast<milliseconds>(high_resolution_clock::now() - s).count() 
        << "ms with " << A::nSwaps << " swaps\n";
}

Вывод программы зависит от компилятора и машины, но они очень похожи по своей природе. На моем ноутбуке с VS2015 я получаю 1044 мс с ~ 100 млн свопов для сортировки и 824 мс с 10 млн свопов для случайного воспроизведения.

libstdc ++ и libc ++ делают в два раза меньше свопов для сортировки (~ 50M), и результаты следующие. Rextester дает мне похожие результаты: gcc сортировать 854 мс, перемешать 565 мс, clang sort 874ms, shuffle 648ms. Результаты, показанные ideone и coliru, еще более радикальные: ideone sort 1181 мс , перемешайте 1292 мс и coliru сортировка 1157 мс , перемешивание 1461 мс .

Так в чем здесь виновник? Почему с 5-10 раз большим количеством сортировок свопов почти так же быстро или даже быстрее, чем простым перемешиванием? Я даже не принимаю во внимание сравнения и более сложную логику в std::sort, включая выбор алгоритмов вставки, кучи или быстрой сортировки и т. Д. Я сомневаюсь это случайный движок - я даже выбрал самый простой std::minstd_rand, который в основном выполняет целочисленное умножение и по модулю. Из-за промахов в кеше перемешивание происходит относительно медленно?

PS: поведение одинаково для простого std::vector<int>

4 голоса | спросил Rostislav 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 15 Sep 2015 16:02:16 +0300 2015, 16:02:16

2 ответа


0

std::random_shuffle обычно работает следующим образом:

//random(k) generates uniform random from 0 to k-1 inclusive
for (int i = 1; i < n; i++)
  swap(arr[i], arr[random(i + 1)]);

Итак, мы можем видеть два источника неэффективности:

  1. Генераторы случайных чисел часто работают довольно медленно.
  2. Каждый своп использует совершенно случайный элемент из вектора. Когда размер данных велик, весь вектор не помещается в кэш ЦП, поэтому каждый такой доступ должен ждать, пока данные не будут считаны из ОЗУ.

Говоря о пункте 2, алгоритмы сортировки, такие как быстрая сортировка, гораздо более дружественны к кешу: большинство их обращений к памяти обращаются к кешу.

ответил stgatilov 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 15 Sep 2015 16:36:00 +0300 2015, 16:36:00
0

Во-первых, std::sort не требуется использовать неквалифицированное swap. Это не точка настройки, и вы не можете полагаться на собственный определяемый пользователем swap, найденный через ADL. Но даже если бы sort, можно также использовать std::rotate, который может swap, но также memmove. Это не будет учитываться вашей реализацией.

Во-вторых, стандартная библиотека определяет только асимптотическую сложность, которая равна O(N) для std::shuffle и O(N log N) для std::sort. Поэтому вы должны измерить для различных значений N (например, степени 2 от 65K до 65M количеств элементов) и измерить поведение масштабирования. Для маленьких N константа пропорциональности sort может быть намного меньше, чем для shuffle, так как он должен вызывать потенциально дорогой генератор случайных чисел.

Обновление : действительно, кажется, что постоянные факторы и /или эффекты кэша являются виновником (как указал @stgatilov). Смотрите эту демонстрационную версию , где я запускаю std::sort в данных после вызова std::shuffle. Время выполнения для sort составляет примерно половину от времени выполнения shuffle, с еще 5-кратным обменом.

ответил TemplateRex 15 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 15 Sep 2015 16:29:49 +0300 2015, 16:29:49

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132