草庐IT

c++ - 加载带有预排序数据的 STL 集，C++

coder 2024-02-09 原文

我在 Visual Studio 2010 中使用 C++。我有一个 STL 集，我在程序关闭时将其保存到文件中。下次程序启动时，我将(排序的)数据加载回一个集合中。我正在尝试优化加载过程，但遇到了麻烦。我怀疑问题出在频繁的重新平衡上，我正在寻找避免这种情况的方法。

首先，我没有进行任何优化，使用“set->insert (const value_type& x )”

时间: ~5.5 分钟

然后我尝试使用 insert() 版本，您在其中传递 insert() 位置的提示:

iterator insert ( iterator position, const value_type& x );

大致上，我是这样做的:

set<int> My_Set;
set<int>::iterator It;
It = My_Set.insert (0);
for (int I=1; I<1000; I++) {
   It = My_Set.insert (It, I);  //Remember the previous insertion's iterator
   }

时间: ~5.4 分钟

几乎没有任何改进!我认为问题不在于从文件读取的开销——注释掉 insert() 会将时间减少到 2 秒。我认为问题不在于复制我的对象的开销——它是一个带有 int 和 char 的普通旧数据对象。

我唯一能想到的就是这个集合在不断地重新平衡。

1.) 你同意我的猜测吗？

2.) 有没有办法在我加载集合时“暂停”重新平衡，然后在最后重新平衡一次？ (或者……这会有帮助吗？)

3.) 是否有更智能的方法来加载排序后的数据，即不是简单地从最低位移动到最高位？也许交替我的插入，这样它就不必经常平衡？ (示例:插入 1、1000、2、999、3、998，...)

最佳答案

我们谈论的元素有多少？

我用 10.000.000 个整数(在 vector 中准备)做了一个简短的测试，并以三种不同的方式将它们插入到集合中。

准备输入:

  std::vector<int> input;
  for(int i = 0; i < 10*1000*1000; ++i) {
     input.push_back(i);
  }

使用插入项逐项插入到集合中:

发布:2.4 秒/调试:110.8 秒

  std::set<int> mySet;
  std::for_each(input.cbegin(), input.cend(), [&mySet] (int value) {
     mySet.insert(value);
  });

使用 insert(itBegin, itEnd) 插入集合:

发布:0.9 秒/调试:47.5 秒

  std::set<int> mySet;
  mySet.insert(input.cbegin(), input.cend());

  // this is also possible - same execution time:
  std::set<int> mySet(input.cbegin(), input.cend());

因此插入可以大大加快，但即使是慢速方式也应该远离几分钟。

编辑:

我同时使用 Debug模式进行了测试 - 哇 - 我知道调试会降低性能，但它比我想象的要多。对于 50.000.000 个元素，在 Debug模式下分配错误，因此我将我的帖子更新为 10.000.000 个元素并显示了发布和调试构建的时间。

您可以在这里看到巨大的差异 - 使用更快的解决方案是 50 倍。

此外，快速解决方案 (insert(itBegin, itEnd)) 似乎与元素数量呈线性关系(使用预排序数据!)。 previus 测试有五倍多的元素，插入时间从 4.6 减少到 0.9 - 大约五倍。

关于c++ - 加载带有预排序数据的 STL 集，C++，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5411251/

amp43stronginsertcodec++stlsetsorting

有关c++ - 加载带有预排序数据的 STL 集，C++的更多相关文章

  1. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

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

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

  3. ruby - 如何在续集中重新加载表模式？ - 2

    鉴于我有以下迁移:Sequel.migrationdoupdoalter_table:usersdoadd_column:is_admin,:default=>falseend#SequelrunsaDESCRIBEtablestatement,whenthemodelisloaded.#Atthispoint,itdoesnotknowthatusershaveais_adminflag.#Soitfails.@user=User.find(:email=>"admin@fancy-startup.example")@user.is_admin=true@user.save!ende

  4. ruby - RuntimeError(自动加载常量 Apps 多线程时检测到循环依赖 - 2

    我收到这个错误:RuntimeError(自动加载常量Apps时检测到循环依赖当我使用多线程时。下面是我的代码。为什么会这样？我尝试多线程的原因是因为我正在编写一个HTML抓取应用程序。对Nokogiri::HTML(open())的调用是一个同步阻塞调用，需要1秒才能返回，我有100,000多个页面要访问，所以我试图运行多个线程来解决这个问题。有更好的方法吗？classToolsController0)app.website=array.join(',')putsapp.websiteelseapp.website="NONE"endapp.saveapps=Apps.order("

  5. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  6. ruby-on-rails - 使用 config.threadsafe 时从 lib/加载模块/类的正确方法是什么!选项？ - 2

    我一直致力于让我们的Rails2.3.8应用程序在JRuby下正确运行。一切正常，直到我启用config.threadsafe!以实现JRuby提供的并发性。这导致lib/中的模块和类不再自动加载。使用config.threadsafe!启用:$rubyscript/runner-eproduction'pSim::Sim200Provisioner'/Users/amchale/.rvm/gems/jruby-1.5.1@web-services/gems/activesupport-2.3.8/lib/active_support/dependencies.rb:105:in`co

  7. ruby - 我如何添加二进制数据来遏制 POST - 2

    我正在尝试使用Curbgem执行以下POST以解析云curl-XPOST\-H"X-Parse-Application-Id:PARSE_APP_ID"\-H"X-Parse-REST-API-Key:PARSE_API_KEY"\-H"Content-Type:image/jpeg"\--data-binary'@myPicture.jpg'\https://api.parse.com/1/files/pic.jpg用这个:curl=Curl::Easy.new("https://api.parse.com/1/files/lion.jpg")curl.multipart_form_

  8. 世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2

    无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD

  9. 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.你能做的最好的事情是:

  10. FOHEART H1数据手套驱动Optitrack光学动捕双手运动(Unity3D) - 2

    本教程将在Unity3D中混合Optitrack与数据手套的数据流，在人体运动的基础上，添加双手手指部分的运动。双手手背的角度仍由Optitrack提供，数据手套提供双手手指的角度。 01  客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照：https://gitee.com/foheart_1/foheart-h1-data-summary.git02  数据转发打开MotiveBody软件的Streaming，开始向Unity3D广播数据；MotionVenus中设置->选项选择Unit

随机推荐