测量一段代码的运行时复杂度的最佳实践 [英] Best practices for measuring the run-time complexity of a piece of code

问题描述

我有一段粗糙的代码，我想衡量它的时间效率.由于从代码本身估计这种复杂性很困难，我想把它放在一个循环中并对结果计时.一旦收集到足够多的数据点(大小 -> 时间)，我就可以看出哪条曲线最适合.

I have a gnarly piece of code whose time-efficiency I would like to measure. Since estimating this complexity from the code itself is hard, I want to place it in a loop and time the results. Once enough data-points (size -> time) are gathered, I can see which curve fits best.

使用给定大小的随机输入数据重复操作多次可以消除由于操作系统决定在糟糕的时刻执行多任务而产生的波动，从而产生更精确的时间.增加问题的规模会提供更多点，理想情况下间隔良好.

Repeating operations a number of times with random input data of a given size can smooth out fluctuations due to the OS deciding to multitask at bad moments, yielding more precise times. Increasing the size of the problem provides more points, ideally well spaced.

我的测试代码工作正常(初始的、非定时的预热循环以减少加载时间；然后，从 10 的大小开始，以 10% 的系数为增量扩展到 1000000，重复运行直到 5 秒过去或 5 次完整运行完成).然而，我通过猜测得出了这些数字.

My test-code works fine (initial, non-timed warm-up loop to decrease load-times; and then, starting from a size of 10, scaling up to 1000000 in increments of a factor of 10%, repeating runs until 5s have elapsed or 5 full runs have finished). However, I arrived at these numbers by guess-work.

是否有一种公认的科学"方法来缩放重复和问题大小，以实现更快、更准确的时间与大小图? 是否有可以搭建脚手架的代码(或库)所有无聊的部分，在自己动手之前我应该​​知道哪些?特别是，我可以认为，当发现时间上的颠簸时，可能需要采取更多措施——而相对平稳的读数可以简单地被认为足够好".

Is there an accepted, "scientific" way to scale repetitions and problem size to achieve faster, more accurate time-vs-size plots? Is there code out there (or libraries) that can scaffold all the boring bits, and which I should have been aware of before rolling-my-own? In particular, I can think that, when bumps in timings are found, more measures could be warranted -- while relatively smooth readings could simply be considered "good enough".

编辑

我知道计算 big-O 复杂度的经典方法.它适用于具有良好代表性操作(例如比较"或交换")的自包含算法.当这些条件不满足时，它不会像宣传的那样工作(例如:LLVM 的编译时 C++ 模板实例化成本，这是一个庞大而复杂的，我不知道相关的代表性操作是什么).这就是为什么我将其视为一个黑匣子，并试图从外部而不是通过代码检查来测量时间.

I am aware of the classical method of calculating big-O complexity. It works fine for self-contained algorithms with a nice representative operation (say, "comparisons" or "swaps"). It does not work as advertised when those conditions are not met (example: the compile-time C++ template instantiation costs of LLVM, which is a large and complex and where I do not know what the relevant representative operation would be). That is why I am treating it as a black box, and trying to measure times from the outside instead of by code inspection.

推荐答案

测量时间复杂度可能非常困难(如果可能的话)，我从未在算法论文中看到过这一点.如果您无法从(伪)代码或算法描述中计算出时间复杂度，那么也许您可以使用启发式算法来简化分析.

Measuring the time complexity can be very difficult (if it is possible at all) and I never saw this in algorithm papers. If you cannot calculate the time-complexity from (pseudo-) code or the algorithm description, then maybe you can use a heuristic to simplify the analysis.

也许您还可以计算算法某些部分的复杂度，而如果其他部分的复杂度明显要小得多，则可以忽略它们.

Maybe you can also calculate the complexity of some parts of the algorithm and ignore some other parts if they have obviously a much smaller complexity.

如果没有任何帮助，正常的方法是显示算法如何在机器上扩展，就像你写的那样.但是有很多事情会影响结果.只是注意到其中一些:

If nothing helps, the normal way would to show how the algorithm scales on an machine, just as you wrote. But there are many things that effect the results. Just to notice some of them:

• 内存类型:如果您的输入小到足以放入 L1 缓存，那么您的算法运行得非常快，因为内存很快.如果您的输入变大，因此不再适合 L1 缓存，则将其存储在 L2 缓存中，如果输入更大，则将其存储在 RAM 中.并且每次您的程序都会因一个巨大的因素而变慢(除了不断增长的输入因素).最糟糕的是，当它变得如此之大以至于算法不得不在您的硬盘上存储一些细小的输入时.
• 多任务处理:如果您的操作系统决定将 CPU 交给其他程序，您的算法似乎会变慢.这也很难处理.
• 硬件:在 big-O 中，每个操作都计为 1 个时间单位.如果您的算法执行大量操作，而您的 CPU 已针对这些操作进行了优化，这也会影响您的测量.
• 软件:软件可以像硬件一样影响您的测量.例如.如果您使用库进行大量大整数运算，则可以通过使用 GMP 大幅加快程序速度.
• 预热:如果开始测量，必须先预热 CPU.首先在更大的输入上运行算法(不进行测量).
• 输入案例:您只能在某些选定或随机生成的特定长度的输入案例上运行您的程序.在大多数情况下，很难判断(或根本不可能)输入是否会导致更短或更长的运行时间.所以也许你测试了错误的例子.如果你使用随机输入，你会得到更多不同的结果.

总而言之:我认为您只能获得一个想法，即您的算法如何扩展，但您无法通过测量运行时间来准确地获得复杂性的上限.也许这适用于非常小的示例，但对于较大的示例，您将无法获得正确的结果.

All in all: I think you can only get an idea, how your algorithm scales, but you cannot exactly get an upper bound of the complexity by measuring the run-time. Maybe this works for really small examples, but for bigger ones you will not get correct results.

你能做的最好的事情是:

The best you can do would be:

• 写下您用于测量的计算机的确切硬件和软件.
• 多次重复测试(以不同的顺序)
• 如果您更改硬件或软件，则应从头开始.
• 仅使用所有存储在相同内存类型中的输入，因此跳过适合缓存的所有情况.

通过这种方式，您可以查看更改是否改进了算法，其他人可以验证您的结果.

This way you can see if changes have improved the algorithm or not and others can verify your results.

关于输入:

• 如果可能，您应该使用最坏情况的输入.如果您无法判断输入是否是最坏情况，则应使用多种不同的情况或随机输入(如果可能).
• 您必须运行测试(针对每个输入长度)，直到运行时间的平均值稳定.

这篇关于测量一段代码的运行时复杂度的最佳实践的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！