std::vector & std::list -porównanie #2

W poprzedni wpisie przyglądaliśmy się charakterystyce dwóch kontenerów z biblioteki standardowej – std::vector oraz std::list. Wykonaliśmy kilka pomiarów, które wskazały, że std::vector powinien być podstawowym kontenerem w C++. Wspomniałem również o tym, że czasami std::list będzie lepszym wyborem. Sprawdźmy więc, jak to jest z wydajnością std::list.

Zagadka

Tak się składa, że trwa grudzień. A w grudniu, jak to w grudniu – każde grzeczne dziecko mniej lub bardziej wyczekuje świąt Bożego Narodzenia. Codziennie zajadając się słodyczami z kalendarza adwentowego.

Programiści również mają swój kalendarz adwentowy. Codziennie o 6 rano – czasu polskiego – pojawia się jedna nowa zagadka, składająca się z dwóch części. Zachęcam Was abyście spróbowali swoich sił w rozwiązaniu różnorakich zagwozdek. Zabawa przednia!

Dziś zajmiemy się jedną z nich. W dniu 9 zagadka polegała na rozwiązaniu problemu “gry w marmurki” – N elfów (graczy) układa L kamieni w cyklu, wedle kilku reguł.
Oto one:

•  zaczynamy od kamienia 0 (dla nie programistów – 1), i iterujemy aż do L-1 (dla nie programistów: L);
•  przed główną pętlą dodajemy pierwszy kamień na pozycję zerową;
  
•  każdy kolejny kamień dodajemy na kolejnej pozycji;
  
•  jeżeli obecny indeks to koniec kontenera, wstawiamy kamień na pozycji drugiej;
•  w przypadku, gdy obecny indeks to size() – 2, to rozszerzamy kontener o nowy element na końcu, ładując go wartością nowego kamieni;
•  gdy numer bieżącego kamienia jest podzielny przez 23 bez reszty, przechodzimy o 7 pozycji w lewo (i-7), wartość spod tej komórki oraz bieżący kamień przypisujemy bieżącemu graczowi, usuwamy to  pole z kontenera, ustawiamy bieżący indeks na element następujący po usuniętym

Chyba nic nie pokręciłem – po szczegóły odsyłam prosto do AoC.

Rozwiązanie naiwne

No to lecimy z implementacją – pamiętacie moją radę, że std::vector jest podstawowym kontenerem? Zastosujmy się do niej:

#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <iterator>
#include <vector>
#include <fstream>
#include <cctype>
#include <numeric>
#include <set>
#include <array>
#include <list>
#include <functional>
#include <cassert>
#include <chrono>
#include <deque>
int main()
{
    constexpr auto players_number = 459u;
    constexpr auto marbles_count = 71790u;
    std::vector marbles(1);
    std::array<unsigned, players_number> players{};
    auto current_marble = 1;
    auto current_player = 0u;
    auto current_index = marbles.begin();
    const auto start = std::chrono::steady_clock::now();
    while (current_marble <= marbles_count)
    {
        if (current_marble % 23 == 0)
        {
            for (auto i = 0; i < 7; ++i)
            {
                if (current_index == marbles.begin())
                    current_index = marbles.end();
                --current_index;
            }
            players[current_player] += current_marble + *current_index;
            current_index = marbles.erase(current_index);
            if (current_index == marbles.end())
                current_index = marbles.begin();
        }
        else
        {
            for (auto i = 0; i < 2; ++i)
            {
                if (current_index == marbles.end())
                    current_index = marbles.begin();
                ++current_index;
            }
            current_index = marbles.insert(current_index, current_marble);
        }
        ++current_marble;
        ++current_player;
        if (current_player == players_number)
        {
            current_player = 0;
        }
    }
    const auto end = std::chrono::steady_clock::now();
    const auto diff = end - start;
    std::cout << "[" << std::chrono::duration_cast<std::chrono::milliseconds>(diff).count() << " ms]: " << current_marble << "\n";
    const auto val = *std::max_element(players.begin(), players.end());
    std::cout << "answer: " << val << std::endl;
    return 0;
}

(całość dostępna tu: https://godbolt.org/z/TlKwK6)

Poza definicjami zmiennych, kilkoma if-ami nie ma tutaj nic odkrywczego. Tak jak widać: std::vector przeznaczony na cykl układanych kamieni, std::array na zliczanie punktów graczy. No i jeszcze cała filozofia obsługi iteratorów, dodawania i usuwania elementów. Dodałem również kod, który umożliwi sprawdzenie ile zajęło obliczenie zagadki.

Sprawdźmy wyniki – dla mojego zestawu danych (w AoC jest kilka zestawów danych):  459 players; last marble is worth 71790 points obliczyłem poprawną odpowiedź (386151) w około 100 ms.

Druga część zagadki była niemal identyczna z pierwszą, z drobną różnicą. Miałem wykonać poszukiwania dla liczby kamieni równej stokrotności. Czyli  71790 * 100;

Szybka zmiana w kodzie, dodajmy również sprawdzenie czasu który upłynął co 100k iteracji – https://godbolt.org/z/TlKwK6

A oto wyniki… nie będę ich tutaj wklejać, bo nie stawiają mnie jak i std::vector w zbyt dobrym świetle. Napiszę po prostu, że wykonanie programu trwało 4365465 ms. Co daje około 4.3k sekund. Niewiele ponad 70 minut. Sumarycznie, daje to mniej więcej jedną godzinę oraz 10 minut.
Nope!
Z całą pewnością gruba przesada – zaraz to naprawimy.

Podejście drugie.. do rozwiązania poprawnego

Zastanówmy się dlaczego wyniki były tak fatalne… Sądzę, że znasz odpowiedź drogi Czytelniku. Tak – usuwanie oraz wstawianie elementów “w środku” std::vector jest kosztowne czasowo. Cholernie kosztowne.

W takim razie wprowadźmy małą zmianę: /s/std::vector/std::list
Dla zainteresowanych pełna implementacja jest dostępna tutaj: https://godbolt.org/z/IZIcnV

Wyniki są powalające – wykonanie całego programu (czyli prawie 7.2kk iteracji) zajęło około 600 ms. W porównaniu do ponad 70 minut w pierwszym rozwiązaniu. Różnica jest wiec na poziomie 4 rzędów wielkości.

Całkiem niezły zysk przy tak małym wysiłku 🙂

Zachęcam, abyście wyniki sprawdzili online http://quick-bench.com/P6Kn4FXRApJq5KZ2x38F0vA47t0 (wykonanie zostało przeprowadzone tylko dla jednej iteracji).

Dodatkowo, analizując kod asemblerowy obu listingów zauważamy, że ten z użyciem std::vector jest dłuższy o około 30%.
Gwoli ścisłości chodzi o dwa linki do Code Compilera.

W tym momencie możemy stwierdzić, że zagadka kończy się cenną lekcją. Zgodnie z tym, co napisałem w poprzednim wpisie std::list może być kontenerem zdecydowanie szybszym niż std::vector. Co więcej, może być szybszy nawet dla typów POD.

Dlatego też drogi czytelniku gdy masowo usuwasz/dodajesz elementy wewnątrz kontenera powinieneś użyć std::list.
A przede wszystkim zawsze testuj swoje rozwiązania pod kątem złożoności czasowej oraz pamięciowej – wszak po to jest C++!