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:
- 5
- 1 5
- 1 4 5
- 1 2 4 5
Usuń elementy z losowej pozycji np. dla 1 2 0 0, będzie to:
- 1 2 4 5
- 1 4 5
- 1 4
- 4
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.
