10

我目前正在使用带有 C++ 的向量制作应用程序。

我知道预优化是万恶之源。

但我真的忍不住好奇。

我正在将其他向量的一部分添加到另一个向量中。
我们会说向量的大小永远不会改变 300。

因为我总是附加到向量的末尾

这样做是否更快：
a.reserve(300);
a.insert(a.end(), b.begin(), b.end());

或者循环遍历我想要附加的向量并使用push_backor单独添加每个项目（同时仍然预先保留）会更快吗emplace？（不确定哪个更快）

任何人都可以帮助我吗？

4

3 回答 3

10

这是一个一般原则：当一个库同时提供do_x_once和do_x_in_batch时，后者应该至少与do_x_once在简单循环中调用一样快。如果不是，那么该库的实现非常糟糕，因为一个简单的循环足以获得更快的版本。通常，此类批处理函数/方法可以执行额外的优化，因为它们具有数据结构内部的知识。

所以，insert应该至少和循环一样快push_back。在这种特殊情况下，智能实现可以为您要插入的所有元素insert执行一次。每次都必须检查向量的容量。不要试图智取图书馆:)reservepush_back

于 2013-02-21T18:31:00.410 回答
5

我想这真的取决于编译器（库实现）、编译选项和架构。在 VS2005 中进行快速基准测试，无需在 Intel Xeon 上进行优化 (/Od)：

std::vector<int> a;
std::vector<int> b;

// fill 'a' with random values for giggles

timer.start()
// copy values from 'a' to 'b'
timer.stop()

我使用这些不同的“复制值...”方法获得了 10 000 000 个项目的这些结果：

  1. 为“b”保留空间，然后使用 for 循环b.push_back(a[i]);：0.808 秒
  2. 调整“b”的大小，然后使用索引分配进行 for 循环b[i] = a[i];：0.264 秒
  3. 无需重新调整“b”的大小，只需b.insert(b.end(), a.begin(), a.end());：0.021 秒（与先保留没有显着差异）
  4. std::copy(a.begin(), a.end(), std::back_inserter(b));: 0.944 秒（0.871 保留优先）
  5. 调整“b”的大小，然后在基指针上进行内存复制memcpy(&(b[0]), &(a[0]), 10000000*sizeof(int));：0.061 秒

然而，启用优化 (/Ox) 后，情况就不同了。我不得不将大小增加到 100 000 000 以获得更多差异化：

  1. push_back 循环：0.659 秒
  2. 索引循环：0.482 秒
  3. 插入：0.210 秒（与先保留没有显着差异）
  4. std::copy: 0.422 秒，先保留。没有它有一个 bad_alloc。
  5. 内存：0.329 秒

值得注意的是，无论有没有优化，插入方法都是线性缩放的。其他方法在没有优化的情况下显然效率低下，但使用它们仍然不能那么快。正如 James Kanze 所指出的，它在 g++ 上有所不同。使用您自己的平台运行测试以进行验证。

于 2013-03-22T14:56:23.720 回答
4

正如 larsmans 所说，你在单个库调用中做的越多，它就越有可能变得更有效率。在insert 进入向量的情况下，库通常最多会进行一次重新分配，并且最多复制每个移位的元素一次。如果您使用循环 and push_back，它可能会重新分配多次，这可能会明显变慢（例如一个数量级）。

但是，根据类型的不同，执行以下操作也可能更快：

a.resize( 300 );
std::copy( b.begin(), b.end(), a.end() - 300 );

我发现这对于 int在英特尔机器上使用 g++ 的简单标量类型（如 ）更快。

于 2013-02-21T18:40:26.020 回答