关于矢量记忆分配的聪明才智

Question

假设我必须迭代一个可能非常大的数字向量,并将偶数和奇数元素复制到新的单独向量中.(源向量可以有任何比例的均衡;它可以是所有均匀,所有可能性,或介于两者之间.)

为简单起见,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]);
}

但是,我担心如果它被用作类似排序算法的实现的一部分,这将是低效的并且是有害的,其中性能是最重要的.例如,QuickSort涉及像这样分离元素.

您可以使用reserve()先前分配内存,因此只需要一次分配,但是您必须迭代整个源向量两次 - 一次计算需要整理的元素数量,再次进行实际复制.

当然,你可以分配与源向量大小相同的空间量,因为新的向量都不需要保留更多,但这似乎有些浪费.

有没有更好的方法让我失踪？是push_back()平时信任来管理这样的事情对于程序员,或者它可以为敏感的算法成为负担？

Answer 1

我将回答我认为你真正要问的问题,"应该push_back()避免在重算法的内循环中？" 而不是其他人似乎已经阅读了你的帖子,这是"如果我在对大型向量进行无关排序之前调用push_back,这是否重要？" 此外,我将回答我的经验,而不是花时间追查引文和同行评审的文章.

你的榜样,基本上是做两件事情,加起来的总CPU成本:它的阅读和输入向量元素操作,然后它插入元素融入到输出向量.您担心插入元素的成本是因为:

1. push_back()是一个常量时间(瞬时,真的),当一个向量有足够的空间为一个额外的元素预先保留时,但是当你的预留空间用完时,它会很慢.
2. 分配内存是昂贵的(malloc()只是慢,即使当学生假装new是不同的东西)
3. 在重新分配后将向量的数据从一个区域复制到另一个区域也很慢:当push_back()发现它没有足够的空间时,它必须去分配一个更大的向量,然后复制所有元素.(理论上,对于大量OS页面的向量,STL的神奇实现可以使用VMM在虚拟地址空间中移动它们而无需复制 - 实际上我从未见过可能的.)
4. 过度分配输出向量会导致问题:它会导致碎片化,使得将来的分配更慢; 它会烧毁数据缓存,使一切变慢; 如果持续存在,它会占用稀缺的可用内存,导致PC上的磁盘分页和嵌入式平台上的崩溃.
5. 分配输出向量导致问题,因为重新分配向量是O(n)操作,因此重新分配m次是O(m×n).如果STL的默认分配器使用指数重新分配(每次重新分配时使向量的保留两倍于其先前的大小),则会使您的线性算法为O(n + n log m).

你的本能,因此,正确的是:你永远载体预先预留空间如果可能的话,不是因为的push_back是缓慢的,但因为它可以触发一个重新分配这是缓慢的.另外,如果你看一下它的实现shrink_to_fit,你会发现它也会进行复制重新分配,暂时使你的内存成本加倍并导致进一步的碎片化.

这里的问题是你并不总是确切知道输出向量需要多少空间; 通常的反应是使用启发式和自定义分配器.默认情况下,为每个输出向量保留n/2 + k的输入大小,其中k是某个安全范围.这样你通常会有足够的空间用于输出,只要你的输入是合理平衡的,并且push_back可以在极少数情况下重新分配.如果你发现push_back的指数行为浪费了太多的内存(当你真正只需要n + 2时你就会保留2n个元素),你可以给它一个自定义的分配器,以较小的线性块扩展矢量大小 - 当然如果向量真的不平衡并且你最终做了很多调整大小,这将会慢得多.

如果不提前行走输入元件,就无法始终保留足够的空间; 但是如果您知道平衡通常是什么样的,那么您可以使用启发式方法对其进行很好的猜测,以获得多次迭代的统计性能提升.