Когда выгоднее устойчивая сортировка?

Question

Мое решение

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <iomanip>

using namespace std;

int main(int argc, char * argv[])
{
    vector<int> v(36000000);
    int k = 0;
    for(int i = 1;    i <= 6000; ++i)
        for(int j = 6001; j <= 12000; ++j)
            v[k++] = i*j;
    sort(v.begin(),v.end());
    long long s = 0;
    for(int i = 0; i < 36000000; ++i) s += v[i];
    cout << s;
}

Работало примерно так же, как и лучшее на Python, но чуть медленнее. На моей машине все это считало примерно 2,04±0,01 секунды. Ну не может же быть, чтоб С++ уступал Python'у :) — и я начал по всякому этот код пытаться ускорить.

Оптимизировать не удавалось, все упиралось в sort. С горя заменил его на stable_sort — посмотреть, что будет, и — о чудо! — время упало до 1,30±0,03 секунды.

Вроде бы всегда говорилось, что в силу большей сложности stable_sort (и не только алгоритмической, каковая равна O(N·log(N)²)) в общем случае работает хуже sort. Но, как выясняется, это как минимум не всегда так? Я понимаю, что константа может быть очень разной :), но когда она меньше, чем константа в sort?

Под G++ проверено — разница чуть другая, но в целом то же самое: 1 и 2.

Никто в этом не копался, не может дать свои комментарии, что и когда эффективнее применять, если устраивает и та, и другая функциональность?

Visual C++ 2019, Windows 10

Answer 1

Все лучшие алгоритмы сортировки имеют сложность O(N * log(N)). Python оказался быстрее потому что использует TimSort, а он работает очень быстро когда массив состоит из отсортированых кусков. Именно такой массив и получается в приведенном двойном цикле.

std::sort обычно использует QuickSort на большим массивах. Эта сортировка никак не использует тот факт, что части массива уже отсортированы, на первой же итерации он сломает структуру массива.

std::stable_sort обычно использует MergeSort, который требует O(n) дополнительной памяти в отличии от QuickSort. Именно из-за дополнительной памяти по умолчанию используют нестабильную сортировку.

Возможно внутри С++ имплементаций MergeSort используется оптимизация, которая проверяет а является ли подмассив уже отсортированным. В таком случае может не применятся InsertionSort на маленьких подмассивах (проверка на то что подмассив уже отсортирован занимает O(n), а InsertionSort занимает O(n^2) времени).

Все 3 сортировки (TimSort, QuickSort, MergeSort) используют внутри сортировку вставками если размер подмассива меньше какой-то длины.

Бенчмарк для сравнения sort и stable_sort предоставлен @wololo и немного доделан мной:

#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cstddef>
#include <limits>
#include <vector>

using std::cin;
using std::cout;
using std::endl;

int rand(int bits)
{
    int result = 0;
    while (bits)
    {
        int add = bits >= 15 ? 15 : bits;
        result = (result << add) | (rand() & ((1 << add) - 1));
        bits -= add;
    }
    return result;
}

int main()
{
    typedef std::vector<int> vect_type;
    const unsigned long vect_size = 50000000;
    static_assert(std::numeric_limits<vect_type::size_type>::max() >= vect_size);

    std::vector<int> vect(vect_size), vect_stable(vect_size);

    for (int bits = 1; bits <= 31; bits++)
    {
        cout << "bits: " << bits << endl;

        for (vect_type::size_type i = 0; i < vect_size; ++i)
        {
            volatile int rand_val = rand(bits);
            vect[i] = rand_val;
            vect_stable[i] = rand_val;
        }

        {
            std::clock_t begin = std::clock();
            std::sort(vect.begin(), vect.end());
            std::clock_t end = std::clock();

            cout << "sort: " << double(end - begin) / CLOCKS_PER_SEC << endl;
        }
        {
            std::clock_t begin = std::clock();
            std::stable_sort(vect_stable.begin(), vect_stable.end());
            std::clock_t end = std::clock();

            cout << "stable_sort: " << double(end - begin) / CLOCKS_PER_SEC << endl;
        }

        cout << (vect == vect_stable) << endl;
    }
}

Функция int rand(int bits) генерирует случайное число длиной bits битов. По каким-то причинам длина чисел влияет на скорость сортировок. Вот что получилось у меня (Visual C++ 2019, Windows 10):

╔══════╦═══════╦═════════════╗
║ bits ║ sort  ║ stable_sort ║
╠══════╬═══════╬═════════════╣
║    1 ║ 0.228 ║ 1.14        ║
║    2 ║ 0.381 ║ 1.419       ║
║    3 ║ 0.503 ║ 1.489       ║
║    4 ║ 0.634 ║ 1.618       ║
║    5 ║ 0.807 ║ 1.765       ║
║    6 ║ 0.96  ║ 1.902       ║
║    7 ║ 1.15  ║ 2.043       ║
║    8 ║ 1.319 ║ 2.193       ║
║    9 ║ 1.483 ║ 2.317       ║
║   10 ║ 1.67  ║ 2.452       ║
║   11 ║ 1.847 ║ 2.59        ║
║   12 ║ 2.022 ║ 2.74        ║
║   13 ║ 2.211 ║ 2.88        ║
║   14 ║ 2.398 ║ 2.997       ║
║   15 ║ 2.573 ║ 3.152       ║
║   16 ║ 2.756 ║ 3.279       ║
║   17 ║ 2.942 ║ 3.412       ║
║   18 ║ 3.13  ║ 3.556       ║
║   19 ║ 3.339 ║ 3.681       ║
║   20 ║ 3.567 ║ 3.794       ║
║   21 ║ 3.765 ║ 3.9         ║
║   22 ║ 4.045 ║ 4.092       ║
║   23 ║ 4.262 ║ 4.066       ║
║   24 ║ 4.332 ║ 4.097       ║
║   25 ║ 4.373 ║ 4.105       ║
║   26 ║ 4.408 ║ 4.122       ║
║   27 ║ 4.416 ║ 4.119       ║
║   28 ║ 4.405 ║ 4.121       ║
║   29 ║ 4.407 ║ 4.109       ║
║   30 ║ 4.421 ║ 4.12        ║
║   31 ║ 4.411 ║ 4.122       ║
╚══════╩═══════╩═════════════╝

БЛОГ НА HUSL

Когда выгоднее устойчивая сортировка?

Ответы (1 шт):