Я написал простой код на C++ для проверки скорости сортировки данных, представленных в виде списка, а затем вектора.
В случае со списком я получаю время 27 секунд. Для вектора я получаю 10 секунд. Почему такой большой разрыв в производительности? Разве алгоритмы, используемые для сортировки списка и вектора, не одинаковы, например, mergesort?
EDIT: Возможно, я ошибаюсь в последнем пункте. Как я знаю, в учебниках при теоретическом описании алгоритмов сортировки, кажется, используется слово список
в смысле std::вектор
. Я не знаю, как
чем алгоритмы сортировки для векторов отличаются от алгоритмов сортировки для списков, так что если кто-нибудь сможет прояснить, это было бы очень полезно. Спасибо.
//In this code we compare the sorting times for lists and vectors.
//Both contain a sequence of structs
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
using namespace std;
struct particle
{
double x;
double y;
double z;
double w;
bool operator<(const particle& a) const
{
return x < a.x;
}
};
int main(int argc, char *argv[])
{
int N=20000000;
clock_t start,stop;
vector<particle> myvec(N);
vector<particle>::iterator cii;
//Set vector values
for (cii = myvec.begin(); cii != myvec.end(); ++cii)
{
cii->x =1.0*rand()/RAND_MAX;
cii->y =1.0*rand()/RAND_MAX;
cii->z =1.0*rand()/RAND_MAX;
cii->w =1.0*rand()/RAND_MAX;
}
list<particle> mylist(N);
list<particle>::iterator dii;
//Set list values
for (cii=myvec.begin(),dii = mylist.begin(); dii != mylist.end() && cii!=myvec.end(); ++dii, ++cii)
{
dii->x =cii->x;
dii->y =cii->y;
dii->z =cii->z;
dii->w =cii->w;
}
//Sort the vector
start=clock();
sort(myvec.begin(),myvec.end());
stop=clock();
cout<<"Time for sorting vector "<<(stop-start)/(double) CLOCKS_PER_SEC<<endl;
//Sort the list
start=clock();
mylist.sort();
stop=clock();
cout<<"Time for sorting list "<<(stop-start)/(double) CLOCKS_PER_SEC<<endl;
return 0;
}