草庐IT

c++ - 最快的插入 C++

coder 2024-02-15 原文

鉴于数组/vector 非常大，有没有办法在数组/vector 的任何位置快速插入数据？

如果我使用 vector::insert vector 将移动我的项目之后的所有项目，这将花费很多时间，例如，如果 vector 有 1b 个项目并且这是在 vector 中间执行的，则 vector 将移动 500m 项目。

有没有什么有效的方法可以用 C 风格/C++ 数组或 Vector 来做到这一点？

最佳答案

理论(特别是大 O 表示法)说，由于删除/插入所需的容器移位，链表的插入和删除复杂度为 O(1)，而动态数组的复杂度为 O(n)。

但那是理论。计算机不仅仅是理论。在实践中它大不相同 .

现代计算机的内存排列在所谓的内存层次结构中，即一组不同类型的内存设备，按其速度排序:

+---------------+
| CPU registers |   ^
+---------------+   |
|   L1 cache    |   |
|      ...      |   |   Less apacity
|   LN cache    |   |   Faster access
+---------------+   |   More expensive hardware
|      RAM      |   |
+---------------+   
|      HDD      |
+---------------+

如图所示，层次结构是通过内存访问速度来组织的。但请注意，更高的速度意味着更昂贵的硬件，因此这意味着 许多慢速内存和一些快速内存 .
因此，提高程序性能的一种方法是 将经常使用的数据保存在快速内存中 , 并且只在需要时才进入慢速内存(例如，程序请求未加载到快速内存中的数据)。

这正是硬件所做的，假设有两种行为:
  • 如果请求了一条数据，将来可能会请求它附近的数据。这被称为 Locality of reference .例如，考虑我们如何使用数组。
  • 如果请求了一条数据，将来可能会再次请求它。这就是所谓的时间局部性。同样，一次又一次地迭代和数组就是一个例子。

    • 当然，内存是有限的，因此在层次结构的某个级别中加载新数据的请求会丢弃之前存在的数据。

    所以，为什么这对不同容器的性能很重要？

    记住链表(std::list 是链表)是如何工作的:
    链表是通过指针在它们之间连接的分离节点链:
    +---+     +---+             +---+
| 1 | --> | 2 | --> ... --> | N |
+---+     +---+             +---+

    另一方面，动态数组(std::vector 是动态数组)是 一块连续的内存 :
    +---+---+-----+---+
| 1 | 2 | ... | N |
+---+---+-----+---+

    正如我上面所说，该理论认为链表插入/删除具有 O(1) 复杂度，因为“只是在更改指针”。但是考虑一下如何访问内存来做到这一点。 您是否注意到该过程不满足空间局部性规则？ .所以这个有很多未命中(cache misses)，也就是请求快内存之外的新内存，性能下降。
    事实上，即使理论上说遍历链表的复杂度为 O(n)，但实际上与复杂度一起是由于缓存未命中而导致的连续性能下降。

    现在考虑动态数组的工作原理:插入/删除确实具有 O(n) 复杂度，因为您必须将数组的一侧移动一个位置以便为新元素留下间隙，或者如果要删除则消除该间隙.
    但是请记住，数组是一个连续的内存块，因此如果您正在使用它，可能该数组已完全(或几乎部分)加载到快速内存(空间局部性)中，因此 换档过程真的很快 .

    如您所见，动态数组比现代架构中的链表快得多 .

    一般来说，std::vector与std::list相比有很多优点:
  • 它的缓存友好。正如我们所讨论的，std::list不是，而且“缓存友好性”对于当今的性能非常重要。这导致快速插入/删除、快速随机访问和快速复制。
  • 链表在每次插入/删除时执行一次动态内存操作。调用 malloc()/free() (也就是说，调用操作系统来检索/离开堆内存)需要很多时间。另一方面，动态数组仅以 O(logn) 平均值进行解除/分配。

    • 但这还不是全部:在少数情况下，std::list必须是首选，在 的情况下复制/移动元素的成本非常高 . std::vector的点性能基于在缓存中完成的廉价移位过程，但如果 vector 的元素具有某些昂贵的复制/移动语义，则根本没有任何好处和 列表比 vector 表现更好 .

    阅读 this article有关该主题的更多信息。

    关于c++ - 最快的插入 C++，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20960936/

    amp43strongcodebrc++arraysvector

    有关c++ - 最快的插入 C++的更多相关文章

    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 字符串中插入项目符号字符？ - 2

      我正在尝试创建一个带有项目符号字符的Ruby1.9.3字符串。str="•"+"helloworld"但是，当我输入它时，我收到有关非ASCII字符的语法错误。我该怎么做？ 最佳答案 你可以把Unicode字符放在那里。str="\u2022"+"helloworld" 关于ruby-如何在Ruby字符串中插入项目符号字符？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/1195

    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能够做这样的事情？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=

    7. ruby - 在 ruby​​ 中使用自动创建插入数组 - 2

      我想知道是否可以通过自动创建数组来插入数组，如果数组不存在的话，就像在PHP中一样:$toto[]='titi';如果尚未定义$toto，它将创建数组并将“titi”压入。如果已经存在，它只会推送。在Ruby中我必须这样做:toto||=[]toto.push('titi')可以一行完成吗？因为如果我有一个循环，它会测试“||=”，除了第一次:Person.all.eachdo|person|toto||=[]#with1billionofperson,thislineisuseless999999999times...toto.push(person.name)你有更好的解决方案吗？

    8. ruby-on-rails - 在方法调用中插入 Ruby？ - 2

      在我的用户模型中，我有一堆属性，例如is_foos_admin和is_bars_admin，它们决定允许用户编辑哪些类型的记录。我想干掉我的编辑链接，目前看起来像这样:'edit'ifcurrent_user.is_foos_admin?%>...'edit'ifcurrent_user.is_bars_admin?%>我想做一个帮助程序，让我传入一个foo或bar并返回一个链接来编辑它，就像这样:助手可能看起来像这样(这不起作用):defedit_link_for(thing)ifcurrent_user.is_things_admin?link_to'Edit',edit_poly

    9. 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

    10. ruby - Ruby 中字符串运算符 + 和 << 的区别 - 2

      我是Ruby和这个网站的新手。下面两个函数是不同的，一个在函数外修改变量，一个不修改。defm1(x)x我想确保我理解正确-当调用m1时，对str的引用被复制并传递给将其视为x的函数。运算符当调用m2时，对str的引用被复制并传递给将其视为x的函数。运算符+创建一个新字符串，赋值x=x+"4"只是将x重定向到新字符串，而原始str变量保持不变。对吧？谢谢 最佳答案 String#+::str+other_str→new_strConcatenation—ReturnsanewStringcontainingother_strconc

    随机推荐