Сортировка list и forward_list

283

20 декабря 2021, 06:30

Вот столкнулся с ситуацией, которую не могу обьяснить. Решил Я сравнить скорость сортировки list и forward_list (с одинаковым содержимым) и на моё удивление, с миллионом елементов, list сортируется за 60 секунд, а forward_list за 11 секунд. В документации читал, что для list и для forward_list сложность сортировки составляет NlogN. Как такое возможно и почему не сделать такую сортировку для list?

Код, которым проверял (может проблема в нем):

#include <iostream>
#include <list>
#include <forward_list>
#include <ctime>
#include <algorithm>
#include <cstdlib>
int main()
{
    using namespace std;
    srand(time(0));
    cout << "Initializing list...\n";
    list<int> list(1000000);
    generate(list.begin(), list.end(), rand);
    cout << "Initializing forwList...\n";
    forward_list<int> forwList(list.begin(), list.end());
    cout << "Sorting list...\n";
    clock_t start = clock();
    list.sort();
    clock_t finish = clock();
    double listSortTime = (finish - start) / CLOCKS_PER_SEC;
    cout << "Sorting forwList...\n";
    start = clock();
    forwList.sort();
    finish = clock();
    double forwListSortTime = (finish - start) / CLOCKS_PER_SEC;
    cout << "list sort time = " << listSortTime << " secs.\n";
    cout << "forwList sort time = " << forwListSortTime << " secs.\n";
    return 0;
}

Answer 1

Ну как-то мало Данных для анализа ))

Судя по cppreference N log N у обоих единственное что приходит в логову - одноноправлейнный список просто легковеснее и дешевле бегать при малых объемах с головы. Компаратор по умолчанию у них одинаковый!

Немного переделал Ваш код - результаты такие - На мой взгляд все верно ) forward проваливается при увлечении объема данных. (Видимо дорого бегать каждый раз с головы в одну сторону)

env: gcc-9.2.1 (-O2) без фанлупа

Size : 1
Error
Error
----------------------
Size : 5
Container ready for sort!
0.003936 ms
Sorted!
Container ready for sort!
0.000833 ms
Sorted!
----------------------
Size : 25
Container ready for sort!
0.012289 ms
Sorted!
Container ready for sort!
0.003084 ms
Sorted!
----------------------
Size : 125
Container ready for sort!
0.058212 ms
Sorted!
Container ready for sort!
0.013846 ms
Sorted!
----------------------
Size : 625
Container ready for sort!
0.380673 ms
Sorted!
Container ready for sort!
0.157383 ms
Sorted!
----------------------
Size : 3125
Container ready for sort!
2.05303 ms
Sorted!
Container ready for sort!
0.729929 ms
Sorted!
----------------------
Size : 15625
Container ready for sort!
10.3486 ms
Sorted!
Container ready for sort!
5.83922 ms
Sorted!
----------------------
Size : 78125
Container ready for sort!
56.2764 ms
Sorted!
Container ready for sort!
33.7152 ms
Sorted!
----------------------
Size : 390625
Container ready for sort!
325.695 ms
Sorted!
Container ready for sort!
704.157 ms
Sorted!
----------------------
Size : 1953125
Container ready for sort!
2199.14 ms
Sorted!
Container ready for sort!
4821.91 ms
Sorted!
----------------------
Size : 9765625
Container ready for sort!
13591.5 ms
Sorted!
Container ready for sort!
33397.3 ms
Sorted!
----------------------

Сам код:

#include <iostream>
#include <forward_list>
#include <algorithm>
#include <chrono>
#include <random>
#include <list>
#include <forward_list>

class timeCounter {
    public:
        timeCounter() : start(std::chrono::high_resolution_clock().now()),
                        end(std::chrono::high_resolution_clock().now()) {};
        ~timeCounter() {
        end = std::chrono::high_resolution_clock().now();
        auto d = end - start;
        std::cout <<  std::chrono::duration<double, std::ratio_multiply<std::chrono::seconds::period, std::milli>>(d).count() << " ms" << std::endl;
    }
    private:
        std::chrono::time_point<std::chrono::_V2::system_clock> start, end;
 };

std::vector<int64_t> GetVector(int64_t size) {
    std::vector<int64_t> v(size);
    std::mt19937_64 generator(std::random_device{}());
    std::uniform_int_distribution<> uid(-100'000, 100'000);
    auto gen{std::bind(uid, generator)};
    std::generate(std::begin(v), std::end(v), gen);
    if(std::is_sorted(std::begin(v), std::end(v))) {
        std::shuffle(std::begin(v), std::end(v), generator);
    }
    return std::move(v);
}

template<typename T>
void TimeSortTest(T cont) {
    if(!std::is_sorted(std::begin(cont), std::end(cont))) {
        std::cout << "Container ready for sort!" << std::endl;
    } else {
        std::cout << "Error" << std::endl;
        return;
    } 
    {
        timeCounter tc{};
        cont.sort();
    }
    if(std::is_sorted(std::begin(cont), std::end(cont))) {
        std::cout << "Sorted!" << std::endl;
    }    
}

int main()
{
    for (auto i{1}; i < 10'000'000; i *= 5) {
        std::cout << "Size : " << i << std::endl;
        auto v{GetVector(i)};
        std::list<int64_t> list{std::begin(v), std::end(v)};
        std::forward_list<int64_t> forwList{std::begin(v), std::end(v)};
        TimeSortTest(list);
        TimeSortTest(forwList);
        std::cout << "----------------------" << std::endl;
    }

    return 0;
}