4

假设我必须遍历一个可能非常大的数字向量，并将偶数和奇数元素复制到新的单独向量中。（源向量可能具有任何比例的偶数与赔率；它可能是所有偶数、所有赔率或介于两者之间的某个位置。）

为简单起见，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()预先分配内存，因此只需要一次分配，但随后您必须对整个源向量进行两次迭代 - 一次计算需要排序的元素数量，再一次用于实际复制。

当然，您可以分配与源向量大小相同的空间，因为新向量都不需要容纳更多空间，但这似乎有点浪费。

我错过了更好的方法吗？通常可以信任为push_back()程序员管理这类事情，还是会成为敏感算法的负担？

4

5 回答 5

9

我将回答我认为您真正想问的问题，即“应该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 个元素），您可以给它一个自定义分配器，将向量大小扩展为更小，

There's no way to always reserve the exact right amount of space without walking the input elements in advance; but if you know what the balance usually looks like, you can use a heuristic to make a good guess at it for a statistical performance gain over many iterations.

于 2011-07-25T01:41:59.283 回答
2

当然，您可以分配与源向量大小相同的空间，因为新向量都不需要容纳更多空间，但这似乎有点浪费。

然后打电话跟进shrink_to_fit

但是，我担心这会效率低下并损害排序算法之类的东西。... push_back() 通常被信任来为程序员管理这类事情，或者它会成为敏感算法的负担吗？

是的，push_back 是可信的。虽然老实说我不明白你的担忧是什么。据推测，如果您在向量上使用算法，您已经将元素放入向量中。您在谈论哪种算法，向量元素如何push_back到达那里很重要，无论是它还是其他？

于 2011-07-24T02:28:35.400 回答
2

用一个将所有偶数放在所有赔率之前的自定义谓词对原始向量进行排序怎么样？

bool EvenBeforeOdd(int a, int b)
{
  if ((a - b)  % 2 == 0) return a < b;

  return a % 2 == 0;
}

std::sort(v.begin(), v.end(), EvenBeforeOdd);

然后你只需要找到最大的偶数，你可以用它来做upper_bound一个非常大的偶数或类似的东西。一旦你发现了这一点，你就可以制作非常便宜的范围副本。

更新：std::partition正如@Blastfurnace 评论的那样，使用它而不是更有效sort，因为我们实际上并不需要在每个分区中排序的元素：

bool isEven(int a) { return 0 == a % 2; }
std::vector<int>::const_iterator it =  std::partition(v.begin(), v.end(), isEven);

std::vector<int> evens, odds;
evens.reserve(std::distance(v.begin(), it);
odds.reserve(std::distance(it, v.end());

std::copy(v.begin(), it, std::back_inserter(evens));
std::copy(it, v.end(), std::back_inserter(odds));
于 2011-07-24T02:33:01.473 回答
1

如果您的对象是动态创建的，那么向量实际上只是存储指针。这使得向量的效率大大提高，尤其是在内部重新分配方面。如果相同的对象存在于多个位置，这也将节省内存。

std::vector<YourObject*> Evens;

注意：不要从函数上下文中推送指针，因为这会导致该帧之外的数据损坏。相反，需要动态分配对象。

这可能无法解决您的问题，但也许它是有用的。

于 2011-07-24T02:28:46.517 回答
1

如果您的子向量正好是一半（奇数/偶数），那么只需为每个子向量分配 50% 的原始向量。这样可以避免浪费和shrink_to_fit.

于 2011-07-24T02:30:21.137 回答