估计实际（而非理论）运行复杂度的实现

Question

估计实际（而非理论）运行复杂度的实现

javacomplexity-theorybenchmarkingcalipermicrobenchmark

9

任何计算机科学专业的人都知道，堆排序在理论上的最坏情况是 O(n log n)，而快速排序的最坏情况是 O(n^2)。然而，在实践中，一个良好实现的快速排序（具有良好的启发式）将在每个数据集上优于堆排序。一方面，我们几乎不会观察到最坏情况，另一方面例如 CPU 缓存行、预取等在许多简单任务中产生巨大差异。而且，例如快速排序可以处理已排序的数据（具有良好的启发式）在 O(n) 的时间复杂度内，而堆排序将始终以 O(n log n) 的时间重新组织数据，因为它没有利用现有的结构。

对于我的玩具项目 caliper-analyze，我最近一直在研究从基准测试结果中估算算法实际平均复杂度的方法。特别地，我尝试了劳森和汉森的 NNLS 拟合与不同的多项式。

然而，它还没有表现得太好。有时我会得到可用的结果，有时则不会。我想可能会有所帮助，只需进行更大的基准测试，特别是尝试更多的参数。

以下结果是用于排序Double对象的，采用SAW模式和10%的随机性。本次运行中n只有500，因此并不代表实际使用情况...这些数字是估计的运行时间与大小的依赖关系。输出结果经过手动编辑和排序，并且不反映工具当前提供的内容！

BubbleSortTextbook       LINEAR: 67.59  NLOG2N:  1.89  QUADRATIC: 2.51
BubbleSort               LINEAR: 54.84                 QUADRATIC: 1.68
BidirectionalBubbleSort  LINEAR: 52.20                 QUADRATIC: 1.36
InsertionSort            LINEAR: 17.13  NLOG2N:  2.97  QUADRATIC: 0.86
QuickSortTextbook                       NLOG2N: 18.15
QuickSortBo3             LINEAR: 59.74                 QUADRATIC: 0.12
Java                     LINEAR:  6.81  NLOG2N: 12.33
DualPivotQuickSortBo5                   NLOG2N: 11.28
QuickSortBo5             LINEAR:  3.35  NLOG2N:  9.67

您可以看出，在这种特定情况下（通常情况下，它并不完全令人满意），结果基本上与已知行为相符：冒泡排序非常昂贵，而对于快速排序的良好启发式方法要好得多。然而，例如，具有中位数启发式方法的快速排序最终以O(n + n^2)的估计值结束，而其他快速排序则被估计为O(n + n log n) 现在是我的实际问题：

您是否了解从基准数据中执行运行时复杂度分析以预测哪个实现（如上所示，我有兴趣比较同一算法的不同实现！）在真实数据上表现最佳的算法/方法/工具？
您是否了解关于此的科学文章（估计实现的平均复杂度）？
您是否了解可帮助获得更准确估计的稳健拟合方法？例如，NNLS的正则化版本。
您是否了解需要多少样本才能获得合理估计的经验法则？（特别是，当工具应该避免给出任何估计，因为它可能会不准确？）

我想再强调一遍，我不关心理论复杂度或形式分析。我感兴趣的是看到在真实CPU上对于基准数据实现（即使是理论上相同的算法）的表现... 对于一个常见范围的数值因素，比渐近行为更加重要。（不，长期来看，它不仅仅是时间复杂度和排序。但我对索引结构和其他参数感兴趣。如果我没有记错，caliper也可以测量内存消耗）此外，我正在使用Java。只调用Matlab内置函数的方法对我没有用处，因为我不生活在Matlab世界中。

如果有时间，我将尝试以更多的大小重新运行其中一些基准测试，以便获得更多数据点。也许那时它就能够正常工作了...但我相信有更稳健的回归方法可以用于从较小的数据集中获得更好的估计。此外，我想检测样本是否过小以至于无法进行任何预测！

- Erich Schubert

@JimGarrison 不一定。原帖中一直强调他对理论组成部分不太感兴趣... - Zong

4

更适合[cstheory.se]或[stats.se]。 - Jim Garrison

3

这并不适用于TCS，因为我假设这是一个黑盒算法模型。在计算机视觉领域，我觉得解决方案可能实用性不太强。相比之下，Stack Overflow更注重将这些东西实现到实际代码中。理论上的解决方案对我帮助不大。理论上，NNLS应该能胜任这项工作，但实际上它的表现并不足够好；它可能对离群值的鲁棒性不够强，而且对于相同n的多次测量也没有很好的表现。 - Erich Schubert

此外，统计学家们经常假设我只是这样做一次。然后我可以手动选择参数、调整核函数等；但我正在尝试将其转化为我的卡尺分析工具的内置函数，应该在我不设置任何参数的情况下运行。 :-( - Erich Schubert

2

@Raedwald 我认为他在最后的列表中很好地总结了问题：如何编写一个程序，在给定一组基准结果的情况下自动估算算法的可扩展性。 - Has QUIT--Anony-Mousse

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Lawrey · Accepted Answer

如果您想要得到实际的复杂度，最好进行测量。试图在没有测量的情况下猜测程序的性能是非常不可靠的。

同一程序在不同的机器上执行的性能可能会有很大不同。例如，一个算法在一台机器上可能更快，但在另一台机器上可能更慢。

您的程序的速度可能会因为机器正在执行其他任务而变慢，因此像缓存这样的资源使用较多的算法可能会变慢，并且在必须共享这些资源时会使其他程序变慢。

在计算机上单独测试算法可以比尝试在真实程序中使用它快2-5倍。

您知道需要多少样本才能获得合理的估计值吗？（特别是，何时应该避免给出任何估计值，因为它可能会不准确？）

要确定像90%或99%这样的百分位数，您需要1 /（1-p）^ 2，即针对99％，在预热后至少需要10,000个样本。对于99.9％，则需要一百万个。