草庐IT

c++ - 排序列表和结构 vector 之间的性能差距。 C++

coder 2023-11-14 原文

我写了一个简单的 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。)

有了这个，您将不得不使用前向迭代就足够的算法，例如合并排序**。

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

另请参阅: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/

序列表ampvectorcodeltc++stl

有关c++ - 排序列表和结构 vector 之间的性能差距。 C++的更多相关文章

  1. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  2. ruby-on-rails - Rails 应用程序之间的通信 - 2

    我构建了两个需要相互通信和发送文件的Rails应用程序。例如，一个Rails应用程序会发送请求以查看其他应用程序数据库中的表。然后另一个应用程序将呈现该表的json并将其发回。我还希望一个应用程序将存储在其公共(public)目录中的文本文件发送到另一个应用程序的公共(public)目录。我从来没有做过这样的事情，所以我什至不知道从哪里开始。任何帮助，将不胜感激。谢谢! 最佳答案 无论Rails是什么，几乎所有Web应用程序都有您的要求，大多数现代Web应用程序都需要相互通信。但是有一个小小的理解需要你坚持下去，网站不应直接访问彼此

  3. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  4. ruby - RVM 使用列表[0] - 2

    是否有类似“RVMuse1”或“RVMuselist[0]”之类的内容而不是键入整个版本号。在任何时候，我们都会看到一个可能包含5个或更多ruby的列表，我们可以轻松地键入一个数字而不是X.X.X。这也有助于rvmgemset。 最佳答案 这在RVM2.0中是可能的=>https://docs.google.com/document/d/1xW9GeEpLOWPcddDg_hOPvK4oeLxJmU3Q5FiCNT7nTAc/edit?usp=sharing-知道链接的任何人都可以发表评论

  5. ruby - ＃之间？ Cooper 的 *Beginning Ruby* 中的错误或异常 - 2

    在Cooper的书BeginningRuby中，第166页有一个我无法重现的示例。classSongincludeComparableattr_accessor:lengthdef(other)@lengthother.lengthenddefinitialize(song_name,length)@song_name=song_name@length=lengthendenda=Song.new('Rockaroundtheclock',143)b=Song.new('BohemianRhapsody',544)c=Song.new('MinuteWaltz',60)a.betwee

  6. ruby-on-rails - `a ||= b` 和 `a = b if a.nil 之间的区别？ - 2

    我正在检查一个Rails项目。在ERubyHTML模板页面上，我看到了这样几行:我不明白为什么不这样写:在这种情况下，||=和ifnil?有什么区别？ 最佳答案 在这种特殊情况下没有区别，但可能是出于习惯。每当我看到nil?被使用时，它几乎总是使用不当。在Ruby中，很少有东西在逻辑上是假的，只有文字false和nil是。这意味着像if(!x.nil?)这样的代码几乎总是更好地表示为if(x)除非期望x可能是文字false。我会将其切换为||=false，因为它具有相同的结果，但这在很大程度上取决于偏好。唯一的缺点是赋值会在每次运行

  7. ruby - 是否有用于序列化和反序列化各种格式的对象层次结构的模式？ - 2

    给定一个复杂的对象层次结构，幸运的是它不包含循环引用，我如何实现支持各种格式的序列化？我不是来讨论实际实现的。相反，我正在寻找可能会派上用场的设计模式提示。更准确地说:我正在使用Ruby，我想解析XML和JSON数据以构建复杂的对象层次结构。此外，应该可以将该层次结构序列化为JSON、XML和可能的HTML。我可以为此使用Builder模式吗？在任何提到的情况下，我都有某种结构化数据-无论是在内存中还是文本中-我想用它来构建其他东西。我认为将序列化逻辑与实际业务逻辑分开会很好，这样我以后就可以轻松支持多种XML格式。 最佳答案 我最

  8. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  9. [工业相机] 分辨率、精度和公差之间的关系 - 2

    📢博客主页：https://blog.csdn.net/weixin_43197380📢欢迎点赞👍收藏⭐留言📝如有错误敬请指正！📢本文由Loewen丶原创，首发于CSDN，转载注明出处🙉📢现在的付出，都会是一种沉淀，只为让你成为更好的人✨文章预览：一.分辨率（Resolution）1、工业相机的分辨率是如何定义的？2、工业相机的分辨率是如何选择的？二.精度（Accuracy）1、像素精度（PixelAccuracy）2、定位精度和重复定位精度（RepeatPrecision）三.公差（Tolerance）四.课后作业（Post-ClassExercises）视觉行业的初学者，甚至是做了1~2年

  10. ruby-on-rails - 一般建议和推荐的文件夹结构 - Sinatra - 2

    您将如何构建一个简单的Sinatra应用程序？我正在制作，我希望该应用具有以下功能:“应用程序”更像是一个包含所有信息的管理仪表板。然后另一个应用程序将通过REST访问信息。我还没有创建仪表板，只是从数据库中获取东西session和身份验证(尚未实现)您可以上传图片，其他应用可以显示这些图片我已经使用RSpec创建了一个测试文件通过Prawn生成报告目前的设置是这样的:app.rbtest_app.rb因为我实际上只有应用程序和测试文件。到目前为止，我已经将Datamapper用于ORM，将SQLite用于数据库。这是我的第一个Ruby/Sinatra项目，所以欢迎任何和所有建议-我应

随机推荐