排序列表和结构向量之间的性能差距.C++

Question

我写了一个简单的C++代码来检查数据排序的速度,以列表的形式表示,然后是矢量.

在列表的情况下,我得到时间为27秒.对于矢量,我得到10秒.为什么巨大的性能差距？用于排序列表和向量的算法不一样吗？即 归并排序？

编辑:我可能在最后一点错了.据我所知,教科书在理论上描述排序算法时,似乎是list在一个意义上使用这个词std::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;
}

Answer 1

没有a std::vector不使用合并排序进行排序(在大多数实现中;标准没有指定算法).

std::list没有O(1)随机访问,因此它不能使用像快速排序*这样的算法,它需要O(1)随机访问速度快(这也是为什么std::sort不起作用的原因std::list.)

有了这个,你将不得不使用前向迭代足够的算法,例如合并排序**.

合并排序通常较慢[1] [2].

另请参见:list.sort和std :: sort之间有什么区别？

*:libstdc ++实际上使用了introsort.
**:libstdc ++实际上使用了合并排序的变体

Answer 2

向量在内存中的存储比列表更紧密。这样可以在排序过程中提供对缓存更友好的访问模式。