我写了一个简单的 C++ 代码来检查排序数据的速度,以列表的形式表示,然后是 vector 。
在列表的情况下,我得到的时间为 27 秒。对于 vector ,我得到 10 秒。为什么会有巨大的性能差距?用于对列表和 vector 进行排序的算法不是相同的吗?即。合并排序?
编辑: 最后一点我可能错了。据我所知,教科书在理论上描述排序算法时,似乎是在 std::vector
的意义上使用 list
这个词。我不知道怎么办
vector 的排序算法与列表的排序算法有何不同,所以如果有人可以澄清那将非常有帮助。谢谢你。
//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;
}
最佳答案
std::vector
未使用合并排序进行排序(在大多数实现中;标准未指定算法)。
std::list
没有 O(1) 随机访问,因此它不能使用像 Quick sort* 这样需要 O(1) 随机访问才能快速的算法(这也是为什么 std::sort
不适用于 std::list
。)
有了这个,您将不得不使用前向迭代就足够的算法,例如合并排序**。
另请参阅:what's the difference between list.sort and std::sort?
*: libstdc++ 实际上使用了 introsort。
**: libstdc++ 实际上使用了 a variant of merge sort
关于c++ - 排序列表和结构 vector 之间的性能差距。 C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8481234/