我一直在解决 UVA 问题 #100 - "The 3n + 1 problem" .这是他们的“示例”问题，时间限制非常宽容(限制为 3 秒，他们的 sample solution 在 0.738 秒内完全没有缓存运行，我迄今为止最好的解决方案在 0.016 秒内运行)，所以我认为我用代码进行试验，我应该总是适合这个限制。好吧，我错了。
问题说明很简单:每行输入有两个数字i和j，输出应该打印这些数字后跟Collatz序列的最大长度其开头介于 i 和 j 之间。
我准备了四种解决方案。它们非常相似，都能产生很好的答案。
The first solution在 vector 中缓存最多 0x100000 序列长度。 0 的长度表示尚未计算从该特定数字开始的序列的长度。它运行速度足够快 - 0.03 秒。
The second solution非常相似，只是它将每个长度缓存在一个用 unordered_map 实现的稀疏数组中。它的运行速度比以前的解决方案慢得多，但仍符合限制:0.28 秒。
作为练习，我还写了the third solution ，它基于第二个。目标是使用 max_element 函数，它只接受迭代器。我不能使用 unordered_map::iterator，因为据我所知，递增这样的迭代器在 map 大小上是线性的；因此，我编写了一个自定义迭代器，在一个抽象“容器”上运行，该“容器”“保存”每个可能数字的序列长度(但实际上只在需要时计算它们并缓存它们)。在它的核心中，它实际上是相同的 unordered_map 解决方案 - 只是在顶部添加了一个额外的迭代器层。该解决方案不适合 3 秒。限制。
现在我无法理解的事情来了。虽然显然第三种解决方案故意过于复杂，但我很难相信额外的迭代器层会产生这样的减速。为了检查这一点，我向 vector 解决方案添加了一个相同的迭代器层。这是 my fourth solution .从这个迭代器的想法对我的 unordered_map 解决方案的影响来看，我预计这里也会有相当大的放缓；但奇怪的是，这根本没有发生。此解决方案的运行速度几乎与普通 vector 解决方案一样快，仅需 0.035 秒。
这怎么可能？究竟是什么导致了第三种解决方案的放缓？以完全相同的方式将两个相似的解决方案过度复杂化，怎么可能会大大减慢其中一个的速度，而对另一个几乎没有伤害呢？为什么将迭代器层添加到 unordered_map 解决方案会导致它无法及时适应，而对 vector 解决方案执行相同操作却几乎不会减慢它的速度？
编辑:
我发现如果输入包含许多重复行，问题似乎最为明显。我在我的机器上针对 1 1000000 的输入测试了所有四种解决方案，重复了 200 次。带有纯 vector 的解决方案在 1.531 秒内处理了所有这些。包含 vector 和附加迭代器层的解决方案耗时 3.087 秒。使用普通无序映射的解决方案耗时 33.821 秒。使用无序映射和管理的附加迭代器层的解决方案花费了超过半小时 - 我在 31 分 0.482 秒后停止了它!我在 Linux mint 17.2 64 位、g++ 版本 Ubuntu 4.8.4-2ubuntu1~14.04 上测试了它，带有标志 -std=c++11 -O2，处理器 Celeron 2955U @1.4 GHz x 2
最佳答案
它appears to be GCC 4.8 中的一个问题。它不会出现在 4.9 up 中。出于某种原因，后续的外部循环(使用填充的 unordered_map 缓存)运行速度逐渐变慢，而不是变快。我不确定为什么，因为 unordered_map 没有变大。
如果您点击该链接并将 GCC 4.8 切换到 4.9，那么您将看到预期的行为，即在相同数值范围内的后续运行增加的时间很少，因为它们利用了缓存。
总而言之，“保守”编译器更新的理念已经过时很长时间了。今天的编译器经过严格测试，您应该使用最新(或至少最近的)版本进行日常开发。
对于一个在线评委来说，让你面对长期修复的错误是很残忍的。
关于c++ - 计算 Collatz 序列的长度 - 自定义迭代器会产生减速？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31556254/