经验估计大哦时间效率
背景
我想通过基准来评估库中某些方法的大噢performance。 我不需要精确度 – 只要certificateO（1），O（logn），O（n），O（nlogn），O（n ^ 2）或者更糟。 由于大哦表示上限，估计O（logn）是O（log logn）的东西不是问题。
现在，我正在考虑find最适合每个大数据的恒定乘数k（但是会将所有结果置顶），然后select最合适的大数。
问题
- 有没有更好的办法比我所做的更好？ 如果是这样，他们是什么？
- 否则，任何人都可以指点我的algorithm来估计k为最佳拟合，并比较每条曲线如何适合数据？
注意和限制
鉴于迄今为止的意见，我需要澄清一些事情：
- 这需要自动化。 我不能“看”数据并做出判断。
- 我将要用多个
n大小来对这些方法进行基准testing。 对于每个规模n，我将使用经过validation的基准框架，提供可靠的统计结果。 - 事实上，我事先知道大多数将被testing的方法。 我的主要目的是为他们提供性能回归testing。
- 代码将用Scala编写，任何免费的Java库都可以使用。
例
这是我想测量的东西的一个例子。 我有这个签名的方法：
def apply(n: Int): A
给定一个n ，它将返回一个序列的第n个元素。 在现有的实现中，这个方法可以有O（1），O（logn）或者O（n），而小的修改可以让它错误地使用次优的实现。 或者，更容易的，可以得到一些依赖于它的其他方法来使用它的次优版本。
为了开始，你必须做一些假设。
- 与任何常数项相比，
n是大的。 - 您可以有效地随机化您的input数据
- 您可以以足够的密度进行采样，以便更好地处理运行时的分布
（3）与（1）一致难以实现。 所以，你可能会得到一个指数最坏的情况，但从来没有遇到最坏的情况，因此认为你的algorithm比平均好得多。
这就是说，所有你需要的是任何标准曲线拟合库。 Apache Commons Math有一个完全足够的。 然后，您可以创build一个包含您想要testing的所有常用术语的函数（例如，常量，日志n，n，n日志n，n n * n，e ^ n），或者logging您的数据并适合指数，然后如果你得到的指数不是接近整数，看看是否抛出一个日志n更合适。
（更详细地说，如果你对C和a适合C*x^a ，或者更容易log C + a log x ，则可以得到指数a ;在所有通用条件一次scheme中，因为如果你有n*n + C*n*log(n)这里C很大，你也可以select这个词。
你会想要改变大小足够的，以便你可以告诉不同的情况分开（如果你关心这些情况可能很难logging条款），并安全地有更多不同的大小比你有参数（可能会超过3倍的开始没关系，只要你至less做了十几次左右的跑步）。
编辑：这是Scala代码，为你做这一切。 我不会解释每一件小事，而是留给你们去调查。 它使用C * x ^ a拟合实现上面的scheme，并且返回（（a，C），（a的下界，a的上界））。 这个界限是相当保守的，你可以看到几次运行这个东西。 C的单位是秒（ a是无单位的），但是不要太信任，因为有一些循环开销（也有一些噪音）。
class TimeLord[A: ClassManifest,B: ClassManifest](setup: Int => A, static: Boolean = true)(run: A => B) { @annotation.tailrec final def exceed(time: Double, size: Int, step: Int => Int = _*2, first: Int = 1): (Int,Double) = { var i = 0 val elapsed = 1e-9 * { if (static) { val a = setup(size) var b: B = null.asInstanceOf[B] val t0 = System.nanoTime var i = 0 while (i < first) { b = run(a) i += 1 } System.nanoTime - t0 } else { val starts = if (static) { val a = setup(size); Array.fill(first)(a) } else Array.fill(first)(setup(size)) val answers = new Array[B](first) val t0 = System.nanoTime var i = 0 while (i < first) { answers(i) = run(starts(i)) i += 1 } System.nanoTime - t0 } } if (time > elapsed) { val second = step(first) if (second <= first) throw new IllegalArgumentException("Iteration size increase failed: %d to %d".format(first,second)) else exceed(time, size, step, second) } else (first, elapsed) } def multibench(smallest: Int, largest: Int, time: Double, n: Int, m: Int = 1) = { if (m < 1 || n < 1 || largest < smallest || (n>1 && largest==smallest)) throw new IllegalArgumentException("Poor choice of sizes") val frac = (largest.toDouble)/smallest (0 until n).map(x => (smallest*math.pow(frac,x/((n-1).toDouble))).toInt).map{ i => val (k,dt) = exceed(time,i) if (m==1) i -> Array(dt/k) else { i -> ( (dt/k) +: (1 until m).map(_ => exceed(time,i,first=k)).map{ case (j,dt2) => dt2/j }.toArray ) } }.foldLeft(Vector[(Int,Array[Double])]()){ (acc,x) => if (acc.length==0 || acc.last._1 != x._1) acc :+ x else acc.dropRight(1) :+ (x._1, acc.last._2 ++ x._2) } } def alpha(data: Seq[(Int,Array[Double])]) = { // Use Theil-Sen estimator for calculation of straight-line fit for exponent // Assume timing relationship is t(n) = A*n^alpha val dat = data.map{ case (i,ad) => math.log(i) -> ad.map(x => math.log(i) -> math.log(x)) } val slopes = (for { i <- dat.indices j <- ((i+1) until dat.length) (pi,px) <- dat(i)._2 (qi,qx) <- dat(j)._2 } yield (qx - px)/(qi - pi)).sorted val mbest = slopes(slopes.length/2) val mp05 = slopes(slopes.length/20) val mp95 = slopes(slopes.length-(1+slopes.length/20)) val intercepts = dat.flatMap{ case (i,a) => a.map{ case (li,lx) => lx - li*mbest } }.sorted val bbest = intercepts(intercepts.length/2) ((mbest,math.exp(bbest)),(mp05,mp95)) } }
请注意，假设使用了静态初始化数据，并且与您正在运行的任何数据相比，多multibench方法预计需要大约sqrt（2） n m *时间才能运行。 以下是一些参数select需要15秒才能运行的例子：
val tl1 = new TimeLord(x => List.range(0,x))(_.sum) // Should be linear // Try list sizes 100 to 10000, with each run taking at least 0.1s; // use 10 different sizes and 10 repeats of each size scala> tl1.alpha( tl1.multibench(100,10000,0.1,10,10) ) res0: ((Double, Double), (Double, Double)) = ((1.0075537890632216,7.061397125245351E-9),(0.8763463348353099,1.102663784225697)) val longList = List.range(0,100000) val tl2 = new TimeLord(x=>x)(longList.apply) // Again, should be linear scala> tl2.alpha( tl2.multibench(100,10000,0.1,10,10) ) res1: ((Double, Double), (Double, Double)) = ((1.4534378213477026,1.1325696181862922E-10),(0.969955396265306,1.8294175293676322)) // 1.45?! That's not linear. Maybe the short ones are cached? scala> tl2.alpha( tl2.multibench(9000,90000,0.1,100,1) ) res2: ((Double, Double), (Double, Double)) = ((0.9973235607566956,1.9214696731124573E-9),(0.9486294398193154,1.0365312207345019)) // Let's try some sorting val tl3 = new TimeLord(x=>Vector.fill(x)(util.Random.nextInt))(_.sorted) scala> tl3.alpha( tl3.multibench(100,10000,0.1,10,10) ) res3: ((Double, Double), (Double, Double)) = ((1.1713142886974603,3.882658025586512E-8),(1.0521099621639414,1.3392622111121666)) // Note the log(n) term comes out as a fractional power // (which will decrease as the sizes increase) // Maybe sort some arrays? // This may take longer to run because we have to recreate the (mutable) array each time val tl4 = new TimeLord(x=>Array.fill(x)(util.Random.nextInt), false)(java.util.Arrays.sort) scala> tl4.alpha( tl4.multibench(100,10000,0.1,10,10) ) res4: ((Double, Double), (Double, Double)) = ((1.1216172965292541,2.2206198821180513E-8),(1.0929414090177318,1.1543697719880128)) // Let's time something slow def kube(n: Int) = (for (i <- 1 to n; j <- 1 to n; k <- 1 to n) yield 1).sum val tl5 = new TimeLord(x=>x)(kube) scala> tl5.alpha( tl5.multibench(10,100,0.1,10,10) ) res5: ((Double, Double), (Double, Double)) = ((2.8456382116915484,1.0433534274508799E-7),(2.6416659356198617,2.999094292838751)) // Okay, we're a little short of 3; there's constant overhead on the small sizes
无论如何，对于所陈述的用例来说，如果你正在检查以确保顺序没有改变，这可能是足够的，因为在设置testing时你可以使用一些值来确保它们给出一些合理的。 人们也可以创造寻求稳定的启发式，但这可能是矫枉过正。
（顺便说一下，这里没有明确的预热步骤;泰尔森估计的稳健拟合应该不需要明智的大基准，这也是为什么我不使用任何其他的基准框架;任何统计数据，只是丢失来自这个testing的力量。）
再次编辑：如果用以下代码replacealpha方法：
// We'll need this math @inline private[this] def sq(x: Double) = x*x final private[this] val inv_log_of_2 = 1/math.log(2) @inline private[this] def log2(x: Double) = math.log(x)*inv_log_of_2 import math.{log,exp,pow} // All the info you need to calculate ay value, eg y = x*m+b case class Yp(x: Double, m: Double, b: Double) {} // Estimators for data order // fx = transformation to apply to x-data before linear fitting // fy = transformation to apply to y-data before linear fitting // model = given x, slope, and intercept, calculate predicted y case class Estimator(fx: Double => Double, invfx: Double=> Double, fy: (Double,Double) => Double, model: Yp => Double) {} // C*n^alpha val alpha = Estimator(log, exp, (x,y) => log(y), p => pb*pow(px,pm)) // C*log(n)*n^alpha val logalpha = Estimator(log, exp, (x,y) =>log(y/log2(x)), p => pb*log2(px)*pow(px,pm)) // Use Theil-Sen estimator for calculation of straight-line fit case class Fit(slope: Double, const: Double, bounds: (Double,Double), fracrms: Double) {} def theilsen(data: Seq[(Int,Array[Double])], est: Estimator = alpha) = { // Use Theil-Sen estimator for calculation of straight-line fit for exponent // Assume timing relationship is t(n) = A*n^alpha val dat = data.map{ case (i,ad) => ad.map(x => est.fx(i) -> est.fy(i,x)) } val slopes = (for { i <- dat.indices j <- ((i+1) until dat.length) (pi,px) <- dat(i) (qi,qx) <- dat(j) } yield (qx - px)/(qi - pi)).sorted val mbest = slopes(slopes.length/2) val mp05 = slopes(slopes.length/20) val mp95 = slopes(slopes.length-(1+slopes.length/20)) val intercepts = dat.flatMap{ _.map{ case (li,lx) => lx - li*mbest } }.sorted val bbest = est.invfx(intercepts(intercepts.length/2)) val fracrms = math.sqrt(data.map{ case (x,ys) => ys.map(y => sq(1 - y/est.model(Yp(x,mbest,bbest)))).sum }.sum / data.map(_._2.length).sum) Fit(mbest, bbest, (mp05,mp95), fracrms) }
那么当存在一个对数项时，你也可以得到一个指数的估计值 – 存在误差估计来select是否logging项是正确的方法，但这取决于你打电话（即我假设你会在开始的时候监视这个数据并读取下面的数字）：
val tl3 = new TimeLord(x=>Vector.fill(x)(util.Random.nextInt))(_.sorted) val timings = tl3.multibench(100,10000,0.1,10,10) // Regular n^alpha fit scala> tl3.theilsen( timings ) res20: tl3.Fit = Fit(1.1811648421030059,3.353753446942075E-8,(1.1100382697696545,1.3204652930525234),0.05927994882343982) // log(n)*n^alpha fit--note first value is closer to an integer // and last value (error) is smaller scala> tl3.theilsen( timings, tl3.logalpha ) res21: tl3.Fit = Fit(1.0369167329732445,9.211366397621766E-9,(0.9722967182484441,1.129869067913768),0.04026308919615681)
（编辑：固定RMS计算，所以它实际上是平均值，加上表明，你只需要做一次，然后可以尝试两种配合。）
我不认为你的方法一般会起作用。
问题在于“大O”的复杂性是基于一个极限，因为一些比例variables趋于无穷大。 对于该variables的较小值，性能行为可能完全适合不同的曲线。
问题是，用经验的方法，你永远不知道缩放variables是否足够大，以使结果中的限制显而易见。
另一个问题是，如果你在Java / Scala中实现这个function，你必须付出相当的努力来消除由于JVM热身（例如类加载，JIT编译，堆大小调整）和垃圾收集等原因导致的时序失真和“噪音” 。
最后，没有人会对复杂性的经验估计置若罔闻。 或者至less，如果他们理解复杂性分析的math则不会。
跟进
针对此评论：
您估算的重要性将大大提高您使用的越来越大的样本。
这是真的，但我的观点是你（丹尼尔）没有考虑到这一点。
另外，运行时function通常具有可被利用的特殊特性; 例如，algorithm往往不会改变他们的行为在一些巨大的n。
对于简单的情况，是的。
对于复杂的案例和现实世界的案例，这是一个可疑的假设。 例如：
-
假设一些algorithm使用一个散列表和一个大而固定大小的主散列数组，并使用外部列表来处理冲突。 对于N（==条目数）小于主散列数组的大小，大多数操作的行为将显示为
O(1)。 当N变得比N大得多时，真正的O(N)行为只能通过曲线拟合来检测。 -
假设algorithm使用大量的内存或networking带宽。 通常情况下，它将运行良好，直到达到资源限制，然后性能将严重下降。 你如何解释这个？ 如果它是“经验复杂性”的一部分，那么你如何确保你到达转折点？ 如果你想排除它，你怎么做？
如果你乐于根据经验估计这个值，你可以测量做多less次操作需要多长时间。 使用比率，你可以得到你估计它是哪个function。
例如，如果1000次操作与10000次操作（10次）的比率是（首先testing更长的次数）。您需要执行实际的操作次数来查看您所拥有的范围的顺序。
- 1x => O（1）
- 1.2x => O（ln ln n）
- 〜2-5x => O（ln n）
- 10x => O（n）
- 20-50x => O（n ln n）
- 100x => O（n ^ 2）
这只是一个估计，因为时间复杂性是为了一台理想的机器而devise的，应该在math上certificate一些东西，而不是测量。
很多人试图凭经validation明PI是一个分数。 当他们测量圆周的比例时，它们总是一个分数。 最终，普遍认为PI不是一个分数。
一般来说，你希望达到的目标是不可能的。 即使一个algorithm会停止的事实在一般情况下也不能被certificate（见停机问题 ）。 即使它停止了你的数据，你仍然无法通过运行来推断复杂性。 例如，冒泡sorting的复杂度为O（n ^ 2），而在已sorting的数据上，它的行为就好像是O（n）。 没有办法为未知algorithmselect“合适的”数据来估计其最差情况。
我们最近实现了一个为JVM代码进行半自动平均运行时分析的工具。 你甚至不需要访问源代码。 目前还没有发布（仍然在减less一些可用性缺陷），但我希望很快就会出现。
它基于程序执行的最大似然模型 [1]。 总之，字节码是用成本计数器增加的。 然后运行目标algorithm（如果需要的话，分布式），以处理由您控制的分布的一组input。 使用相关的启发式（裂缝最小二乘法的方法）将聚合的计数器外推到函数。 从这些，更多的科学导致估计平均运行时间渐近（ 3.576n - 1.23log(n) + 1.7 ）。 例如，该方法能够以高精度再现由Knuth和Sedgewick完成的严格的经典分析。
这种方法与其他方法相比，最大的优点是你独立于时间估计 ，特别是独立于机器，虚拟机甚至是编程语言。 你真的得到你的algorithm的信息，没有所有的噪音。
而且—可能是杀手级的function—它带有一个完整的GUI，引导你完成整个过程。
在cs.SE上查看我的答案，了解更多细节和更多参考资料。 您可以在这里find一个初步的网站（包括该工具的beta版本和发表的论文）。
（请注意，平均运行时间可以用这种方式进行估算，而最坏情况下的运行时永远不可能，除非你知道最坏情况，如果这样做，可以使用平均情况进行最坏情况分析;只给工具提供最坏情况。一般来说，运行时间界限是不能决定的 。
- algorithm和数据结构的最大似然分析 U.Laube和ME Nebel（2010）。 [ preprint ]
你应该考虑改变你的任务的关键方面。
将您正在使用的术语更改为：“估算algorithm的运行时间”或“设置性能回归testing”
你能估计algorithm的运行时间吗？ 那么你build议尝试不同的input大小，并衡量一些关键的操作或时间。 然后，对于一系列input大小，您计划以编程方式估计algorithm的运行时间是否没有增长，不断增长，指数增长等。
所以你有两个问题，运行testing，并在input集合增长时以编程方式估计增长率。 这听起来像一个合理的任务。
我不知道我得到100％你想要什么。 但我知道你testing你自己的代码，所以你可以修改它，例如注入观察语句。 否则，你可以使用某种forms的方面编织？
如何将可重复计数器添加到数据结构中，然后在每次调用特定的子函数时增加它们？ 你可以让那些计数@elidable所以他们将被部署在图书馆。
然后对于一个给定的方法，比如delete(x) ，你可以用各种自动生成的数据集来testing它，试图给它们一些偏移量等等，并且收集计数。 正如Igor指出的那样，您不能validation数据结构是否永远不会违反大O界限，您至less可以断言，在实际的实验中，绝不会超过给定的界限数（例如，一棵树永远不会超过4 * log(n)倍） – 所以你可以检测到一些错误。
当然，你需要一定的假设，例如在你的计算机模型中调用方法是O（1）。
事实上，我事先知道大多数将被testing的方法。 我的主要目的是为他们提供性能回归testing。
这个要求是关键。 你想用最less的数据来检测exception值（因为testing应该是快速的 ，可以忍受的），并且根据我的经验拟合曲线来对复杂的复发进行数值评估，线性回归等将会过度拟合。 我认为你最初的想法是一个好主意。
我要做什么来实现它是准备一个预期的复杂度函数g1，g2，…，并为数据f，testing如何接近常数f / gi + gi / f是每个我。 使用最小二乘成本函数，这只是计算每个i的数量方差 ，并报告最小。 最后眼球的差异，并手动检查exception糟糕的配合。
为了对程序的复杂性进行经验分析，你要做的是运行（和时间）algorithm的给定10,50,100,500,1000等input元素。 然后，您可以绘制结果图并根据最常见的基本types（常数，对数，线性，nlogn，二次，三次，高次多项式，指数）确定最佳拟合函数阶数。 这是负载testing的一个正常部分，它确保algorithm首先按照理论进行操作，其次，尽pipe其理论复杂性（每步需要5分钟的对数时间algorithm）仍然符合现实世界的性能预期除了绝对最高基数testing以外，每一步都是几毫秒的二次复杂度algorithm。
编辑：打破它，algorithm是非常简单的：
定义一个你想评估性能的基数N（10,100,1000,10000等）
对于N中的每个元素X：
创build一个具有X个元素的合适的testing数据集。
开始秒表，或确定并存储当前的系统时间。
在X元素testing集上运行algorithm。
停止秒表，或再次确定系统时间。
开始和停止时间之间的差异是您的algorithm在X元素上的运行时间。
重复N中的每个X.
绘制结果; 给定X个元素（x轴），该algorithm需要T时间（y轴）。 控制X增加的最接近的基本function是增加你的Big-Oh近似值。 正如Raphael所说的那样，这个近似就是这样，并且不会给你很好的区别，比如N的系数，这可能会使得N ^ 2algorithm和2N ^ 2algorithm之间的差异（在技术上都是O（N ^ 2），但给予相同数量的元素，将执行两倍的速度）。
