Na tegorocznej konferencji GovingNative 2012 Bjarne Stroustrup, przedstawił kilka ciekawostek dotyczących nowości w C++:
Jednym z punków była wyższość wektora na listą. Lista góruje nad wektorem, w takich operacjach jak wstawianie oraz usuwanie elementów, jednak proces wyszukania odpowiedniego elementu w kontenerze okazuje się być naprawdę wąskim gardłem. Wektor z kolei lepiej radzi sobie z wyszukiwaniem, gorzej natomiast z usuwaniem i wstawianiem. Dzięki współczesnym procesorem korzystającym z mechanizmu dedukcji skoku, wektor okazuje się zyskiwać ogromną przewagę. Mimo iż wykonuje znacznie więcej operacji w pamięci to będą one odbywały się w cache procesora, gdzie są naprawdę szybkie.
Opis testu.
Wygeneruj N losowych liczb i wstaw je tak by zachowana została posortowana kolejność np. 5 1 4 2:
Usuń elementy z losowej pozycji np. dla 1 2 0 0, będzie to:
Na początek kilka funkcji pomocniczych. Pierwsza łączy nasz generator z rozkładem jednorodnym
TRnd get_rnd(const int max)
{
const int seed = 858446;
TBaseGeneratorType generator(seed);
boost::uniform_int<> uni_dist(0, max);
TRnd rnd(generator, uni_dist);
return rnd;
}
Pierwsza część testu - generyczna funkcja do wstawiania, zachowując posortowaną kolejność.
template <typename T>
void insert_sort(T& con, const int size, TRnd& rnd)
{
for (int i = 0; i < size; ++i) {
const int value = rnd();
typename T::iterator it = std::find_if(con.begin(), con.end(),
value < _1);
con.insert(it, value);
}
}
Druga część testu - usuwanie wartości z losowej pozycji.
template <typename T>
void erase_by_rand_pos(T& con, TRnd& rnd)
{
while (not con.empty()) {
const int pos = rnd() % con.size();
typename T::iterator it = con.begin();
std::advance(it, pos);
con.erase(it);
}
}
Ciało testu:
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <boost/lambda/lambda.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/date_time/posix_time/posix_time.hpp>
using namespace std;
using namespace boost::lambda;
using namespace boost::posix_time;
typedef boost::mt19937 TBaseGeneratorType;
typedef boost::variate_generator<TBaseGeneratorType,
boost::uniform_int<> > TRnd;
int main(int argc, char **argv)
{
if (argc < 2) {
cout << "Missing size argument" << endl;
return -1;
}
TRnd rnd = get_rnd(std::numeric_limits<int>::max());
const int size = boost::lexical_cast<int>(argv[1]);
const ptime time_start = microsec_clock::local_time();
cout << "Start at: " << time_start << ", size = "<< size << endl;
// vector<int> container;
list<int> container;
insert_sort(container, size, rnd);
const ptime time_insert = microsec_clock::local_time();
cout << "Inserted sort: " << time_insert - time_start << endl;
erase_by_rand_pos(container, rnd);
const ptime time_remove = microsec_clock::local_time();
cout << "Erase at random pos: " << time_remove - time_insert << endl;
cout << "Whole process: " << time_remove - time_start << endl;
return 0;
}
Wyniki. Wszystkie testy były kompilowane za pomocą
g++ (4.6.3) z flagą
-O2. Bjarne musiał korzystać z bardziej wyrafinowanego algorytmu niż mój, bo w jego wersji cały proces dla 200000 elementów zajął ok. 500 sekund, w moim przypadku było to już 1116 sekund (sic!), dlatego też nie testowałem powyżej tej wartości. Nie testowałem też "preallocated list" bo nie jestem pewien co to dokładnie jest.
I jeszcze jeden wykres, przedstawiający jak czasowo wyglądały poszczególne operacje, czyli wstawianie z wyszukiwaniem i usuwanie z wyszukiwaniem. Porównując dane, widać, że w przypadku listy, najwolniejszą operacją jest usuwanie z wyszukiwaniem, w przypadku wektora wstawianie z wyszukiwaniem. Usuwanie i wstawianie na wektorze powinny być jego słabym punktem, ale okazują się, że
w połączeniu z wyszukiwaniem, są znacznie szybsze od tego co oferuje lista.
