草庐IT

c++ - vector 与 map 性能混淆

coder 2023-05-03 原文

edit:我专门将 std::vector 的 linear 搜索操作与 std::map binary 搜索操作，因为这似乎与 Herb 的声明有关。我知道使用二分搜索会将性能从 O(N) 提高到 O(log N) 但这不会测试 Herb 的主张

Bjarne Stroustrup 和 Herb Sutter 最近都谈到了 std::vector 在人们期望使用 std::list 的情况下是多么的棒，因为链表遍历期间缓存未命中的成本。 (见 http://channel9.msdn.com/Events/Build/2014/2-661 在 48 分钟标记处)

Herb 进一步声明，对有序 vector 的操作甚至比 std::map 还要快(参见 http://i.imgur.com/zX07TZR.png，取自上述 channel9 视频的 51:30 标记)，我发现很难理解。所以我创建了一个小测试来证明这一点，但很难重现这些结果:https://ideone.com/MN7DYK

这是测试代码:

template <typename C>
void test(std::string name, std::vector<int> shuffledInputValues, C & c)
{
   // fill container 'c' with values from 'shuffledInputValues' then erase them all
   {
      std::cout << "testing " << name << "..." << std::endl;
      timer t;

      for (auto val : shuffledInputValues) insert(c, val);
      for (auto val : shuffledInputValues) remove(c, val);
  }
}

// output:
// testing vector...99.189ms
// testing deque...120.848ms
// testing set...4.077ms

注意 std::vector 的执行速度比 std::set 慢一个数量级。当然这是我预期的结果，但我对 Herb 试图提出的说法感到困惑。

我做错了什么？还是我误解了 Herb 的说法？

关于我的测试应用的注意事项:

  • 它必须使用线性运算 - 练习的重点是演示 CPU 缓存魔法，这是 Herb 和 Bjarne 对练习的约束
  • 我没有为 vector 迭代尝试任何棘手的循环解开，但我相信迭代不会对性能产生太大影响
  • 我将循环限制为 10K 项，因为 ideone 在更大的集合上超时，但增加大小不会改变结果

编辑:见 https://ideone.com/916fVd对于仅比较查找性能的修改示例。线性搜索表现出相同的性能。

最佳答案

我找到了 slides为了更容易引用(我看不到图表，但我想这可能是因为专有文件格式)。相关的幻灯片是第 39 号，它描述了正在解决的问题:

§ Generate N random integers and insert them into a sequence so that each is inserted in its proper position in the numerical order.

§ Remove elements one at a time by picking a random position in the sequence and removing the element there.

现在，很明显链表不是解决这个问题的好选择。尽管列表在开头或中间插入/删除比 vector 好得多，但由于需要线性搜索，因此在 随机 位置插入/删除并不好。由于缓存效率更高，使用 vector 进行线性搜索要快得多。

Sutter 建议 map (或一般的树)似乎是该算法的自然选择，因为您得到 O(log n) 搜索。事实上，对于插入部分中较大的 N 值，它确实很容易击败 vector 。

但是来了。您需要删除第 n 个元素(对于随机 n)。这就是我认为您的代码作弊的地方。您可以按照插入的顺序删除元素，有效地将输入 vector 用作查找表，以在“随机”位置查找元素的值，以便您可以在 O(log n) 中搜索它。所以你实际上是在使用集合和 vector 的组合来解决问题。

常规的二叉搜索树，例如用于 std::map 或 std::set(我假设 Sutter 使用)的二叉搜索树没有快速算法用于查找第 n 个元素。 Here's one据称平均为 O(log n)，在最坏的情况下为 O(n)。但是 std::map 和 std::set 不提供对底层树结构的访问，所以对于那些你被按顺序遍历卡住的人(如果我错了)这又是一个线性搜索!实际上，我很惊讶 map 版本与 Sutter 结果中的 vector 版本具有竞争力。

对于 log(n) 复杂度，您需要一个结构，例如 Order statistic tree不幸的是，标准库没有提供。有如图所示的 GNU Policy-Based STL MAP here .

这是我为 vector vs 集合 vs ost 制作的快速测试代码(vs vector 与二进制搜索以获得良好的度量)https://ideone.com/DoqL4H Set 慢得多，而其他基于树的结构比 vector 快，这与 Sutter 的结果不符。

order statistics tree: 15.958ms
vector binary search: 99.661ms
vector linear search: 282.032ms
set: 2004.04ms

(N = 20000，差异只会更大，有利于具有更大值的ost)

简而言之，我得出了相同的结论，即 Sutter 的原始结果看起来很奇怪，但原因略有不同。在我看来，这次更好的渐近复杂度赢得了更低的常数因子。

请注意，问题描述并不排除重复随机值的可能性，因此使用 map/set 而不是 multimap/multiset 有点欺骗 map/set，但我认为只有很小的意义当值域远大于 N 时。此外，预先保留 vector 不会显着提高性能(当 N = 20000 时大约为 1%)。

关于c++ - vector 与 map 性能混淆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24542936/

混淆ampcodevectornoreferrerc++stdvector

有关c++ - vector 与 map 性能混淆的更多相关文章

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

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

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

  3. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  4. ruby - 在 ruby​​ 中使用 .try 函数和 .map 函数 - 2

    我需要从json记录中获取一些值并像下面这样提取curr_json_doc['title']['genre'].map{|s|s['name']}.join(',')但对于某些记录，curr_json_doc['title']['genre']可以为空。所以我想对map和join()使用try函数。我试过如下curr_json_doc['title']['genre'].try(:map,{|s|s['name']}).try(:join,(','))但是没用。 最佳答案 你没有正确传递block。block被传递给参数括号外的方法

  5. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  6. Ruby 的数字方法性能 - 2

    我正在使用Ruby解决一些ProjectEuler问题，特别是这里我要讨论的问题25(Fibonacci数列中包含1000位数字的第一项的索引是多少？)。起初，我使用的是Ruby2.2.3，我将问题编码为:number=3a=1b=2whileb.to_s.length但后来我发现2.4.2版本有一个名为digits的方法，这正是我需要的。我转换为代码:whileb.digits.length当我比较这两种方法时，digits慢得多。时间./025/problem025.rb0.13s用户0.02s系统80%cpu0.190总计./025/problem025.rb2.19s用户0.0

  7. ruby - Ruby 性能中的计时器 - 2

    我正在寻找一个用ruby​​演示计时器的在线示例，并发现了下面的代码。它按预期工作，但这个简单的程序使用30Mo内存(如Windows任务管理器中所示)和太多CPU有意义吗？非常感谢deftime_blockstart_time=Time.nowThread.new{yield}Time.now-start_timeenddefrepeat_every(seconds)whiletruedotime_spent=time_block{yield}#Tohandle-vesleepinteravalsleep(seconds-time_spent)iftime_spent

  8. ruby-on-rails - 如果条件与 &&，是否有任何性能提升 - 2

    如果用户是所有者，我有一个条件来检查说删除和文章。delete_articleifuser.owner?另一种方式是user.owner?&&delete_article选择它有什么好处还是它只是一种写作风格 最佳答案 性能不太可能成为该声明的问题。第一个要好得多-它更容易阅读。您future的自己和其他将开始编写代码的人会为此感谢您。 关于ruby-on-rails-如果条件与&&，是否有任何性能提升，我们在StackOverflow上找到一个类似的问题：

  9. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  10. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

随机推荐