C++：是否有客观通用的方法来比较迭代算法的速度？

Question

我有几个用 C++ 编写的迭代算法来解决同样的问题。当在我的机器上针对非常大的输入集运行这些算法时，很容易根据每个算法对给定输入集花费的时间对它们进行分类。

但是这些运行时是基于我的机器以及当时在我的机器上运行的后台进程的数量。它们似乎不可复制。

是否有任何客观的通用指标来量化这些算法的运行时间和速度？我想找到一种方法，无论运行在什么机器上，都能给出相同的结果，并且是可重现的。

我正在寻找计算 CPU 周期数的方法，但这在现代微处理器上看起来很难做到。

所以我提到的每个算法都有两个主要功能，搜索功能和计算功能。我手动数一下可以接受吗？在这两个函数中完成的操作，然后使用它作为指标来比较我的算法？

Answer 1

您需要的答案有多精确和可靠？您愿意投入多少工作来找到它？

• 如果您只是想运行基准测试并避免它受到系统上其他进程的影响，您可以使用

  std::clock

  ，它只计算该进程的CPU时间。此类基准测试应该成为每个优化工作的一部分，因为理论考虑中的错误假设或不幸的近似可能会导致代码在实践中表现更差。
• 如果您想要更可靠的东西（更少依赖于您的机器和具体输入），您可以尝试确定算法的渐近时间复杂度（或尝试在文献中查找它们）。 （根据我的经验，这个主题很早就教给计算机科学的学生。计算机科学的入门书籍也应该涵盖它。）
• 如果您需要最大精度，是的，理论上您可以尝试估计每个算法所需的最小/最大/平均 CPU 周期数。简单地计算指令数量会导致不完美的结果，因为不同的指令可能占用不同数量的周期（除法通常比加法需要更长的时间；请参阅 CPU 手册），并且周期数量可能会根据输入而变化（

  1 / 1

  可能仍然很快）。然后，您还必须考虑这样一个事实：您的 CPU 可能能够“并行运行多个指令”，用于“分支预测”，还可能用于其他用途。因此，很可能您必须使用近似值来保持其可行性，即使这样也会很麻烦。只有在运行时极其关键的代码中才值得付出努力。 这里是关于这个主题的另一个问题。 对于大多数应用程序来说可能足够的方法是选择具有最佳渐近复杂度的算法，并让编译器优化处理其余的事情。