jjzjj

c++ - Bjarne Stroustrup 说我们必须避免链表

coder 2023-11-16 原文

我在 YouTube 上看到了这个视频:https://www.youtube.com/watch?v=YQs6IC-vgmo 其中 Bjarne 说最好使用 vector ，而不是链表。我无法掌握全部内容，所以谁能通俗地解释一下他在说什么？

P.S:我是一名高中生，可以轻松处理链表，但我很难自学 vector 。你能推荐任何学习 vector 的资源吗？

最佳答案

vector 与链表的优势

vector 相对于链表的主要优势是内存局部性。

通常，链表中的每个元素都是单独分配的。因此，这些元素在内存中可能并不相邻。 (内存中元素之间的间隙。)

vector 保证连续存储所有包含的元素。 (项目彼此相邻，没有间隙；)

注意:可能会出现过度简化...;)

Imo，关于连续存储数据存储模式与非连续存储模式的优越性能的简化关键点是

1。缓存未命中

现代 CPU 不会从内存中获取单个字节，而是获取稍大的 block 。因此，如果您的数据对象大小小于这些 block 的大小并且存储是连续的，您一次可以获得多个元素，因为多个元素可能在一个 block 中。

示例:

一个 64 字节的 block (通常的缓存行大小)一次适合 16 个 32 位整数。因此，缓存未命中(数据尚未在缓存中 -> 需要从主内存加载)最早发生在从第一个元素被带到缓存的那一刻起处理完 16 个元素之后。如果使用链表，第一个元素很可能是 64 字节 block 中的唯一元素。理论上，列表的每个元素都可能发生缓存未命中。

具体例子:

std::vector<std::uint32_t> v;
// somehow fill 64 values into v
std::uint32_t s{};
for(std::size_t i{0}; i<v.size(); ++i)
{
  s += v[i];
}

想象一下 v 的内容还没有被缓存。

在 for 循环中处理数据的过程中会发生什么？

1)Check whether element v[0] is in cache. --> Nope

2)Fetch 64 bytes starting at the address of v[0] from main memory into a cache line

3)Load v[0] from cache and process by adding its value to s

4)Is element v1 in cache? --> Yes loaded with previous fetch because neighbouring v[0]

5)Load v1 from cache and process by adding its value to s

6)Is element v[2] in cache? --> Yes ...

7) Load v[2] from cache and process by adding its value to s

... etc...

34)Is element v[16] in cache? --> Nope

35) Fetch 64 bytes starting at the address of v[16] from main memory into a cache line

36)Load v[16] from cache and process by adding its value to s

37)Is element v[17] in cache? --> Yes loaded with previous fetch because neighbouring v[16]

etc...

从主内存中获取数据到缓存中比将数据从缓存中加载到处理器寄存器中并执行简单的操作要花费更多的时间。因此，多个值可能驻留在单个缓存行中这一事实可以显着提高性能。

链表不提供连续存储保证，您不能指望获得这种性能提升。这也是为什么对于连续容器，随机迭代(随机访问元素)比前向迭代(按顺序访问元素)表现更差的原因。

2。预取

上述效果被称为“预取器”的 CPU 功能放大。

如果一个 block 已经从主内存加载，预取器准备加载下一个 block /已经将它放入缓存，显着减少从主内存的那部分加载东西的惩罚。

当且仅当您实际上需要下一个准备好的 block 中的数据时，这当然有效。

vector 通常如何工作(内部)？

参见:c++ Vector, what happens whenever it expands/reallocate on stack?

关于c++ - Bjarne Stroustrup 说我们必须避免链表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34170566/

Stroustrupampvectorcachesectionc++linked-list

有关c++ - Bjarne Stroustrup 说我们必须避免链表的更多相关文章

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

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

  2. ruby-on-rails - RSpec:避免使用允许接收的任何实例 - 2

    我正在处理旧代码的一部分。beforedoallow_any_instance_of(SportRateManager).toreceive(:create).and_return(true)endRubocop错误如下:Avoidstubbingusing'allow_any_instance_of'我读到了RuboCop::RSpec:AnyInstance我试着像下面那样改变它。由此beforedoallow_any_instance_of(SportRateManager).toreceive(:create).and_return(true)end对此:let(:sport_

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

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

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

  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 - 为什么必须明确指定 2 个参数才能 curry :> - 2

    考虑这个，它工作正常::>.to_proc.curry(2)[9][8]#=>true,because9>8然而，即使>是一个二元运算符，如果没有指定的元数，上面的代码将无法工作::>.to_proc.curry[9][8]#=>ArgumentError:wrongnumberofarguments(0for1)为什么两者不等价？注意:我特别想用提供的一个参数创建中间柯里化(Currying)函数，然后然后调用然后用第二个参数调用它。 最佳答案 curry必须知道传入的过程的数量，对吧？:-1来自arity的负值令人困惑，但基本上

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

  9. ruby-on-rails - 为什么用户必须输入 7 位数的 Twitter PIN 才能授予我的应用程序访问权限？ - 2

    我正在为我的用户实现一些ruby​​onrails代码推特内容。我正在创建正确的oauth链接...类似http://twitter.com/oauth/authorize?oauth_token=y2RkuftYAEkbEuIF7zKMuzWN30O2XxM8U9j0egtzKv但在我的测试帐户授予对twitter的访问权限后，它会弹出一个页面，上面写着“您已成功授予对.我不知道用户应该在哪里输入此PIN以及他们为什么必须这样做。我认为这不是必要的步骤。Twitter应该将用户重定向到我在应用程序设置中提供的回调URL。有谁知道为什么会这样？更新我找到了thisarticle声明我需

  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

随机推荐