衡量一段代码的运行时复杂性的最佳实践

Question

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

利用给定大小的随机输入数据多次重复操作可以消除由于OS决定在不良时刻进行多任务而导致的波动,从而产生更精确的时间.增加问题的大小可以提供更多的点,理想情况下间距很大.

我的测试代码工作正常(初始,非定时预热循环减少加载时间;然后,从10的大小开始,以10%的增量扩展到1000000,重复运行直到5s有已完成或已完成5次完整运行).但是,我通过猜测得到了这些数字.

是否有一种可接受的"科学"方法来扩展重复和问题大小,以实现更快,更准确的时间尺寸图？是否有代码(或库)可以支撑所有无聊的位,并且我应该在滚动自己之前知道它？特别是,我可以认为,当发现时间上的颠簸时,可以采取更多措施 - 而相对平稳的读数可以简单地被认为是"足够好".

编辑

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

Answer 1

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

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

如果没有任何帮助,通常的方法是显示算法如何在机器上缩放,就像你写的那样.但是有许多因素会影响结果.只是注意其中一些:

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

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

你能做的最好的事情是:

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

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

关于输入:

• 如果可能,您应该使用最坏情况输入.如果你不能说输入是否是最坏的情况,你应该使用许多不同的情况或随机输入(如果可能的话).
• 您必须运行测试(针对每个输入长度),直到运行时间的平均值稳定为止.