Wszechstronny wektor vs porównawcza lista porównawcza dla randomizowanych wstawień/usunięć

Question

Tak więc jestem świadomy pytania this i innych dotyczących SO, które zajmują się problemem, ale większość z nich dotyczy złożoności struktur danych (wystarczy skopiować tutaj, połączone to teoretycznie ma o (

rozumiem złożoność wydaje się wskazywać, że lista będzie lepiej, ale jestem bardziej zainteresowany realną wydajność światowej

. Uwaga: ta kwestia była inspirowana przez slides 45 and 46 of Bjarne Stroustrup's presentation at Going Native 2012 gdzie opowiada o tym, jak pamięć podręczna procesora i lokalizacja odniesienia naprawdę pomagają wektory, ale nie t w ogóle (lub wystarczająco) z listami.

Pytanie: Czy jest to dobry sposób, aby przetestować to przy użyciu czasu procesora, w przeciwieństwie do ściany czasu, a uzyskanie godnej sposób „losowo” wstawianie i usuwanie elementów, które mogą być wykonane z wyprzedzeniem, tak aby nie wpływać na czasy ?

Byłoby miło móc zastosować to do dwóch dowolnych struktur danych (np. Mapy wektorowe i hash lub coś w tym stylu), aby znaleźć "rzeczywisty świat" na niektórych urządzeniach.

Answer 1

Chyba gdybym zamiar przetestować coś takiego, to bym chyba zacząć z kodem coś w tej kolejności:

#include <list> 
#include <vector> 
#include <algorithm> 
#include <deque> 
#include <time.h> 
#include <iostream> 
#include <iterator> 

static const int size = 30000; 

template <class T> 
double insert(T &container) { 
    srand(1234); 
    clock_t start = clock(); 
    for (int i=0; i<size; ++i) { 
     int value = rand(); 
     T::iterator pos = std::lower_bound(container.begin(), container.end(), value); 
     container.insert(pos, value); 
    } 
// uncomment the following to verify correct insertion (in a small container). 
// std::copy(container.begin(), container.end(), std::ostream_iterator<int>(std::cout, "\t")); 
    return double(clock()-start)/CLOCKS_PER_SEC; 
} 


template <class T> 
double del(T &container) { 
    srand(1234); 
    clock_t start = clock(); 
    for (int i=0; i<size/2; ++i) { 
     int value = rand(); 
     T::iterator pos = std::lower_bound(container.begin(), container.end(), value); 
     container.erase(pos); 
    } 
    return double(clock()-start)/CLOCKS_PER_SEC; 
}  

int main() { 
    std::list<int> l; 
    std::vector<int> v; 
    std::deque<int> d; 

    std::cout << "Insertion time for list: " << insert(l) << "\n"; 
    std::cout << "Insertion time for vector: " << insert(v) << "\n"; 
    std::cout << "Insertion time for deque: " << insert(d) << "\n\n"; 

    std::cout << "Deletion time for list: " << del(l) << '\n'; 
    std::cout << "Deletion time for vector: " << del(v) << '\n'; 
    std::cout << "Deletion time for deque: " << del(d) << '\n'; 

    return 0; 
} 

Ponieważ używa clock, powinno to dać czas procesora nie ściennych czasu (choć niektóre kompilatory takie jak MS VC++ źle to rozumieją). Nie próbuje zmierzyć czasu wstawienia poza czasem, aby znaleźć punkt wstawienia, ponieważ 1) wymagałoby nieco więcej pracy i 2) nadal nie mogę się dowiedzieć, co by to miało miejsce. Z pewnością jest to bardzo dokładne, ale biorąc pod uwagę różnicę, jaką widzę z tego, byłbym nieco zaskoczony, widząc znaczącą różnicę w porównaniu z bardziej uważnym testowaniem. Na przykład, z MS VC++, dostaję:

Insertion time for list: 6.598 
Insertion time for vector: 1.377 
Insertion time for deque: 1.484 

Deletion time for list: 6.348 
Deletion time for vector: 0.114 
Deletion time for deque: 0.82 

z gcc uzyskać:

Insertion time for list: 5.272 
Insertion time for vector: 0.125 
Insertion time for deque: 0.125 

Deletion time for list: 4.259 
Deletion time for vector: 0.109 
Deletion time for deque: 0.109 

Faktoring się czas wyszukiwania byłoby nieco nietrywialne, ponieważ trzeba by raz każda iteracja osobno . Aby uzyskać znaczące wyniki, potrzebujesz czegoś bardziej precyzyjnego niż clock (więcej informacji na temat zamówienia lub odczytywania rejestru cyklu zegara). Możesz to zmienić, jeśli uznasz to za stosowne - jak wspomniałem powyżej, brakuje mi motywacji, ponieważ nie widzę, jak to jest rozsądne.

Answer 2

To jest program napisany po obejrzeniu tej rozmowy. Próbowałem uruchomić każdy test czasowy w oddzielnym procesie, aby upewnić się, że podzielniki nie robią nic podstępnego, aby zmienić wydajność. Zmieniłem test, aby umożliwić odliczanie losowego generowania liczb. Jeśli obawiasz się, że ma to znaczący wpływ na wyniki, możesz je odmierzać i odjąć czas spędzony w nim od reszty czasu. Ale dostaję zerowy czas spędzony tam na coś innego niż bardzo duży N. Użyłem getrusage(), co do którego jestem pewien, że nie jest przenośne dla Windows, ale byłoby łatwo zastąpić coś za pomocą zegara() lub cokolwiek chcesz.

#include <assert.h> 
#include <algorithm> 
#include <iostream> 
#include <list> 
#include <vector> 
#include <stdlib.h> 
#include <time.h> 
#include <sys/time.h> 
#include <sys/resource.h> 


void f(size_t const N) 
{ 
    std::vector<int> c; 
    //c.reserve(N); 
    for (size_t i = 0; i < N; ++i) { 
     int r = rand(); 
     auto p = std::find_if(c.begin(), c.end(), [=](int a) { return a >= r; }); 
     c.insert(p, r); 
    } 
} 

void g(size_t const N) 
{ 
    std::list<int> c; 
    for (size_t i = 0; i < N; ++i) { 
     int r = rand(); 
     auto p = std::find_if(c.begin(), c.end(), [=](int a) { return a >= r; }); 
     c.insert(p, r); 
    } 
} 

int h(size_t const N) 
{ 
    int r; 
    for (size_t i = 0; i < N; ++i) { 
     r = rand(); 
    } 
    return r; 
} 

double usage() 
{ 
    struct rusage u; 
    if (getrusage(RUSAGE_SELF, &u) == -1) std::abort(); 
    return 
     double(u.ru_utime.tv_sec) + (u.ru_utime.tv_usec/1e6) + 
     double(u.ru_stime.tv_sec) + (u.ru_stime.tv_usec/1e6); 
} 


int 
main(int argc, char* argv[]) 
{ 
    assert(argc >= 3); 
    std::string const sel = argv[1]; 
    size_t const N = atoi(argv[2]); 

    double t0, t1; 
    srand(127); 

    if (sel == "vector") { 
     t0 = usage(); 
     f(N); 
     t1 = usage(); 
    } else if (sel == "list") { 
     t0 = usage(); 
     g(N); 
     t1 = usage(); 
    } else if (sel == "rand") { 
     t0 = usage(); 
     h(N); 
     t1 = usage(); 
    } else { 
     std::abort(); 
    } 

    std::cout 
     << (t1 - t0) 
     << std::endl; 

    return 0; 
} 

Aby uzyskać zestaw wyników, skorzystałem z poniższego skryptu powłoki.

seq=`perl -e 'for ($i = 10; $i < 100000; $i *= 1.1) { print int($i), " "; }'` 
for i in $seq; do 
    vt=`./a.out vector $i` 
    lt=`./a.out list $i` 
    echo $i $vt $lt 
done