排序列表和结构向量之间的性能差距.C++ [英] Performance gap between sorting a list and a vector of structs. C++
问题描述
我写了一个简单的 C++ 代码来检查排序数据的速度，以列表和向量的形式表示.
I wrote a simple C++ code to check the speed of sorting data , represented in the form of a list and then a vector.
在列表的情况下，我得到的时间为 27 秒.对于向量，我得到 10 秒.为什么会有巨大的性能差距?用于排序列表和向量的算法不是相同的吗?即.归并排序?
In the case of the list I am getting time as 27 seconds. For a vector I get 10 seconds. Why the huge performance gap? Aren't the algorithms used for sorting the list and the vector the same? viz. mergesort?
最后一点我可能错了.据我所知，在理论上描述排序算法时，教科书似乎在std::vector的意义上使用了list这个词.我不知道如何向量的排序算法与列表的排序算法有何不同，所以如果有人能澄清这将非常有帮助.谢谢你.
I may be wrong on the last point. As I know, textbooks when descirbing sorting algorithms theoretically, seem to be use the word list in the sense of a std::vector. I don't know how
how sorting algorithms for vectors would be different from sorting algorithms for lists, so if some one could clarify that would be really helpful. Thank you.
//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;
}
推荐答案
No std::vector 没有使用归并排序进行排序(在大多数实现中；标准没有指定算法).
No a std::vector is not sorted using merge sort (in most implementations; the standard doesn't specify the algorithm).
std::list 没有 O(1) 随机访问，所以它不能使用像 Quick sort* 这样需要 O(1) 随机访问才能快速的算法(这也是为什么 std::sort 不适用于 std::list.)
std::list does not have O(1) random access, so it cannot use algorithms like Quick sort* which requires O(1) random access to be fast (this is also why std::sort doesn't work on std::list.)
有了这个，您将不得不使用前向迭代就足够的算法，例如合并排序**.
With this, you'll have to use algorithms that forward iteration is enough, such as the Merge sort**.
*:libstdc++ 实际上使用了 introsort.
**:libstdc++ 实际上使用了归并排序的一种变体
*: libstdc++ actually uses introsort.
**: libstdc++ actually uses a variant of merge sort
这篇关于排序列表和结构向量之间的性能差距.C++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
