6

我有一个包含 10000 个随机数（mod 100）的向量，我想计算其中两个数字有多少对总和为 100。我写了以下内容：

auto noPairsSumTo100 = 0;
const auto itEnd = end(myNums);
for (auto it1 = begin(myNums); it1 != itEnd ; ++it1) {
  for (auto it2 = it1; it2 != itEnd ; ++it2) {
    if (*it1 + *it2 == 100) {
      noPairsSumTo100 ++;
    }
  }
}

在我的机器上，这大约需要 21.6 秒才能在调试模式下运行。如果我设置 _ITERATOR_DEBUG_LEVEL=0（将 _SECURE_SCL 和 _HAS_ITERATOR_DEBUGGING 都设置为 0），则执行时间将减少到 ~9.5 秒。!=将比较替换为<可将时间进一步缩短至约 8.5 秒。

如果我通过像这样索引向量来实现相同的算法：

auto noPairsSumTo100 = 0;
const auto itEnd = end(myNums);
for (auto index1 = 0; index1 < noTerms; ++index1) {
  for (auto index2 = index1; index2 < noTerms; ++index2) {
    if (myNums[index1] + myNums[index2] == 100) {
      noPairsSumTo100 ++;
    }
  }
}

在调试模式下运行大约需要 2.1 秒。我认为除了使用迭代器之外，我可以使算法尽可能接近。我的问题是，是什么让第一个实现比第二个长约 4 倍？

请注意，两个版本的算法在发布模式下运行大约需要 34 毫秒，因此差异已被优化。

4

2 回答 2

2

除了边界检查之外，STL 代码的调试版本会产生大量的函数调用。一些无辜的行如：

if (a.empty())

可以产生多达 8 个（或更多）函数调用。一些（全部？）STL 实现根本没有针对调试构建进行优化。

STL 的一个常见性能问题是开发人员认为函数内联总是有效的。它没有。如果调用了太多的内联函数，则底部的函数不会被内联，并且仅函数调用开销就会对性能造成巨大影响。这在拥有容器容器时很常见：

map< string, map< int, string>>

外部映射上的操作可能会导致内联函数保持正常功能。

于 2013-11-19T23:29:08.950 回答
0

只需一次更改即可将 21 秒缩短到 3 秒以下。

在您的项目属性配置中，将 C/C++->Code Generation->Basic Runtime Checks 设置为默认值。

比较生成的代码或阅读这篇博文。

（这仍然与 VS 2013/2015 相关。）

于 2016-04-23T10:11:43.967 回答