草庐IT

c++ - 聪明地处理 vector 内存分配

coder 2024-02-13 原文

假设我必须迭代一个可能非常大的数字 vector ，并将偶数和奇数元素复制到新的、单独的 vector 中。 (源 vector 的偶数与奇数的比例可以是任意的；它可以是全偶数、全奇数或介于两者之间。)

为简单起见，push_back 通常用于此类事情:

for (std::size_t Index; Index < Source.size(); Index++)
{
    if (Source[Index] % 2) Odds.push_back(Source[Index]);
    else Evens.push_back(Source[Index]);
}

但是，我担心如果将其用作排序算法等性能至关重要的实现的一部分，这将是低效且有害的。例如，快速排序涉及像这样分离元素。

您可以使用 reserve() 预先分配内存，因此只需要一次分配，但随后您必须遍历整个源 vector 两次 - 一次计算需要多少元素进行整理，并再次进行实际复制。

当然，您可以分配与源 vector 大小相同的空间量，因为两个新 vector 都不需要容纳超过该大小的空间，但这似乎有些浪费。

有没有我缺少的更好的方法？ push_back() 通常可以信任为程序员管理此类事情，还是会成为敏感算法的负担？

最佳答案

我将回答我认为您真正想问的问题，即“是否应该在繁重算法的内部循环中避免使用 push_back()？”而不是其他人似乎已经读到你的帖子，这是“如果我在对大 vector 进行不相关排序之前调用 push_back 有关系吗？”此外，我将根据我的经验来回答，而不是花时间追查引用和同行评审的文章。

您的示例基本上做了两件事，这些事情加起来会增加总 CPU 成本:它读取输入 vector 中的元素并对其进行操作，然后它必须将元素插入输出 vector 。您担心插入元素的成本，因为:

  1. push_back() 是常数时间(瞬时的，真的)当一个 vector 有足够的预留空间用于附加元素时，但当你用完预留空间时速度很慢。
  2. 分配内存是昂贵的(malloc() is just slow，即使学究们假装 new 是不同的)
  3. 在重新分配后将 vector 的数据从一个区域复制到另一个区域 is also slow : 当 push_back() 发现它没有足够的空间时，it has to go and allocate a bigger vector, then copy all the elements . (理论上，对于大小为许多操作系统页面的 vector ，STL 的神奇实现可以使用 VMM 在虚拟地址空间中移动它们而不进行复制——实际上是 I've never seen one that could。)
  4. 过度分配输出 vector 会导致问题:它会导致碎片化，使 future 的分配速度变慢；它会消耗数据缓存，使一切变慢；如果持续存在，它会占用稀缺的可用内存，导致 PC 上的磁盘分页和嵌入式平台上的崩溃。
  5. 分配不足的输出 vector 会导致问题，因为重新分配 vector 是一个 O(n) 操作，因此重新分配 m 次是 O(m×n)。如果 STL 的默认分配器使用指数重新分配(每次重新分配时使 vector 的预留大小是其先前大小的两倍)，这会使您的线性算法 O(n + n log m)。

因此，您的直觉是正确的:始终尽可能为您的 vector 预留空间，不是因为 push_back 很慢，而是因为它会触发一个很慢的重新分配。此外，如果您查看 shr​​ink_to_fit 的实现，您会发现它还会进行复制重新分配，暂时使内存成本翻倍并导致进一步碎片化。

这里的问题是您并不总是确切知道输出 vector 需要多少空间；通常的 react 是使用启发式分配器，也可能使用自定义分配器。默认情况下，为每个输出 vector 保留 n/2+k 的输入大小，其中 k 是一些安全边际。这样一来，您通常就会有足够的空间用于输出，只要您的输入合理平衡，并且 push_back 可以在极少数情况下重新分配。如果你发现 push_back 的指数行为浪费了太多内存(导致你保留 2n 个元素，而实际上你只需要 n+2 )，你可以给它一个自定义分配器，以更小的线性 block 扩展 vector 大小——当然如果 vector 真的不平衡并且你最终会做很多调整大小，那会慢得多。

如果不提前遍历输入元素，就无法始终保留准确的空间量；但是如果您知道平衡通常是什么样子，您可以使用启发式方法对其进行很好的猜测，以便在多次迭代中获得统计性能增益。

关于c++ - 聪明地处理 vector 内存分配，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6804568/

地处ampvectorpush_backcodec++performancememory-managementpush-back

有关c++ - 聪明地处理 vector 内存分配的更多相关文章

  1. ruby-on-rails - Ruby net/ldap 模块中的内存泄漏 - 2

    作为我的Rails应用程序的一部分，我编写了一个小导入程序，它从我们的LDAP系统中吸取数据并将其塞入一个用户表中。不幸的是，与LDAP相关的代码在遍历我们的32K用户时泄漏了大量内存，我一直无法弄清楚如何解决这个问题。这个问题似乎在某种程度上与LDAP库有关，因为当我删除对LDAP内容的调用时，内存使用情况会很好地稳定下来。此外，不断增加的对象是Net::BER::BerIdentifiedString和Net::BER::BerIdentifiedArray，它们都是LDAP库的一部分。当我运行导入时，内存使用量最终达到超过1GB的峰值。如果问题存在，我需要找到一些方法来更正我的代

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

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

  3. Ruby Koans about_array_assignment - 非平行与平行分配歧视 - 2

    通过ruby​​koans.com，我在about_array_assignment.rb中遇到了这两段代码你怎么知道第一个是非并行赋值，第二个是一个变量的并行赋值？在我看来，除了命名差异之外，代码几乎完全相同。4deftest_non_parallel_assignment5names=["John","Smith"]6assert_equal["John","Smith"],names7end45deftest_parallel_assignment_with_one_variable46first_name,=["John","Smith"]47assert_equal'John

  4. ruby-on-rails - Ruby 中的内存模型 - 2

    ruby如何管理内存。例如:如果我们在执行过程中采用C程序，则以下是内存模型。类似于这个ruby如何处理内存。C:__________________|||stack|||------------------||||------------------|||||Heap|||||__________________|||data|__________________|text|__________________Ruby:? 最佳答案 Ruby中没有“内存”这样的东西。Class#allocate分配一个对象并返回该对象。这就是程序

  5. ruby - 在 Ruby 中重新分配常量时抛出异常？ - 2

    我早就知道Ruby中的“常量”(即大写的变量名)不是真正常量。与其他编程语言一样，对对象的引用是唯一存储在变量/常量中的东西。(侧边栏:Ruby确实具有“卡住”引用对象不被修改的功能，据我所知，许多其他语言都没有提供这种功能。)所以这是我的问题:当您将一个值重新分配给常量时，您会收到如下警告:>>FOO='bar'=>"bar">>FOO='baz'(irb):2:warning:alreadyinitializedconstantFOO=>"baz"有没有办法强制Ruby抛出异常而不是打印警告？很难弄清楚为什么有时会发生重新分配。 最佳答案

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

  7. ruby-on-rails - Rails 优雅地处理超时 session ？ - 2

    使用rails4，ruby2。我在rails配置中为我的cookiesession设置了30分钟的超时时间。问题是，如果我转到表单，让session超时，然后提交表单，我会收到此ActionController::InvalidAuthenticityToken错误。如何在Rails中优雅地处理这个错误？比如说，重定向到登录屏幕？ 最佳答案 在您的ApplicationController:rescue_fromActionController::InvalidAuthenticityTokendoredirect_tosome_p

  8. ruby-on-rails - 在 Controller 中干净地处理多个过滤器(参数) - 2

    我有一个名为Post的类，我需要能够适应以下场景:如果用户选择了一个类别，则只显示该类别的帖子如果用户选择了一种类型，则只显示该类型的帖子如果用户选择了一个类别和类型，则只显示该类别中该类型的帖子如果用户没有选择任何内容，则显示所有帖子我想知道我的Controller是否不可避免地会因大量条件语句而显得粗糙...这是我解决此问题的错误方法-有谁知道我如何才能做到这一点？classPostsController 最佳答案 您最好遵循“胖模型，瘦Controller”的惯例，这意味着您应该将这种逻辑放在模型本身中。Post类应该能够报告

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

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

  10. ruby - 使对象的行为类似于 ruby​​ 中并行分配的数组 - 2

    假设您在Ruby中执行此操作:ar=[1,2]x,y=ar然后，x==1和y==2。是否有一种方法可以在我自己的类中定义，从而产生相同的效果？例如rb=AllYourCode.newx,y=rb到目前为止，对于这样的赋值，我所能做的就是使x==rb和y=nil。Python有这样一个特性:>>>classFoo:...def__iter__(self):...returniter([1,2])...>>>x,y=Foo()>>>x1>>>y2 最佳答案 是的。定义#to_ary。这将使您的对象被视为要分配的数组。irb>o=Obje

随机推荐