Dan*_*ral 39 java algorithm big-o scala
我想通过基准测试估算库中某些方法的性能.我不需要精确度 - 它足以证明某些东西是O(1),O(logn),O(n),O(nlogn),O(n ^ 2)或更糟.因为大哦意味着上限,所以估计O(logn)的O(logn)不是问题.
现在,我正在考虑找到最适合每个大数据的数据的常数乘数k(但会覆盖所有结果),然后选择最适合的大哦.
鉴于到目前为止的评论,我需要做一些事情:
n尺寸对方法进行基准测试.对于每种规模n,我将使用经过验证的基准框架,提供可靠的统计结果.这是我想要测量的那种东西的一个例子.我有一个带有此签名的方法:
def apply(n: Int): A
给定a n,它将返回序列的第n个元素.给定现有实现,该方法可以具有O(1),O(logn)或O(n),并且小的改变可以使其错误地使用次优实现.或者,更容易,可以获得一些依赖于它的方法来使用它的次优版本.
Rex*_*err 16
为了开始,你必须做出一些假设.
n 与任何常数项相比都很大.特别是,(3)与(1)一致难以实现.因此,您可能会遇到指数最坏的情况,但从未遇到过最糟糕的情况,因此认为您的算法比平均情况要好得多.
话虽如此,您只需要任何标准的曲线拟合库. Apache Commons Math有一个完全足够的.然后,您可以创建一个包含您要测试的所有常用术语的函数(例如,常量,log n,n,n log n,n n,n n*n,e ^ n),或者您获取数据的日志并且适合指数,然后如果你得到一个不接近整数的指数,看看抛出一个log n是否更适合.
(更详细地说,如果你适合C*x^a的C和a,或更容易log C + a log x,你可以得到的指数a;在全共术语一次刻录方案,您将获得每学期的权重,所以如果你有n*n + C*n*log(n)其中C大,你也会接受那个词.)
你需要改变大小,以便你可以区分不同的情况(如果你关心那些可能很难用日志术语),并且安全地比你有参数的大小更多(大概3倍过量会开始出现好的,只要你至少打了十几个左右.
编辑:这是Scala代码,为您完成所有这些.我不会解释每一小块,而是留给你调查; 它使用C*x ^ a拟合实现上面的方案,并返回((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*时间才能运行.以下是一些参数选择运行〜15s的示例:
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
无论如何,对于规定的用例 - 您要检查以确保订单不会改变 - 这可能是足够的,因为您可以在设置测试时稍微玩一下这些值以确保它们给出合理的结果.人们还可以创建寻求稳定性的启发式方法,但这可能是过度的.
(顺便提一下,这里没有明确的预热步骤; Theil-Sen估计器的稳健拟合应该使得它不需要合理的大基准.这也是我不使用任何其他长凳框架的原因;任何统计它只会丢失这个测试的力量.)
再次编辑:如果alpha使用以下内容替换方法:
// 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 a y value, e.g. 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 => p.b*pow(p.x,p.m))
// C*log(n)*n^alpha
val logalpha = Estimator(log, exp, (x,y) =>log(y/log2(x)), p => p.b*log2(p.x)*pow(p.x,p.m))
// 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)
}
然后你也可以在有一个日志项的时候得到指数的估计值 - 存在错误估计来选择对数是否是正确的方式,但是你可以接听电话(即我假设你最初会监督它并阅读下来的数字):
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计算,所以它实际上是平均值,再加上证明你只需要做一次计时,然后可以尝试两种拟合.)
Ste*_*n C 14
我认为你的方法不会起作用.
问题是"大O"复杂性是基于一个限制,因为一些缩放变量趋于无穷大.对于该变量的较小值,性能行为可能看起来完全适合不同的曲线.
问题在于,使用经验方法,您永远无法知道缩放变量是否足够大,以使限制在结果中显而易见.
另一个问题是,如果你在Java/Scala中实现它,你必须花费相当长的时间来消除由于诸如JVM预热(例如类加载,JIT编译,堆调整大小)和垃圾收集之类的事情中的失真和"噪声". .
最后,没有人会对复杂性的经验估计给予太多信任.或者至少,如果他们理解复杂性分析的数学,他们就不会.
跟进
回应此评论:
您估计的重要性将大大改善您使用的越来越大的样本.
这是事实,尽管我的观点是你(丹尼尔)没有将此考虑在内.
此外,运行时功能通常具有可被利用的特殊特征; 例如,算法往往不会改变他们在某些巨大的行为.
对于简单的情况,是的.
对于复杂的案例和现实世界的案例,这是一个可疑的假设.例如:
假设某些算法使用具有大但固定大小的主哈希数组的哈希表,并使用外部列表来处理冲突.对于小于主哈希数组大小的N(==条目数),大多数操作的行为将显示为O(1).O(N)只有当N远大于此时,才能通过曲线拟合检测到真实行为.
假设该算法使用大量内存或网络带宽.通常情况下,它会很有效,直到达到资源限制,然后性能会严重下降.你怎么解释这个？如果它是"经验复杂性"的一部分,那么如何确保达到转换点？如果你想排除它,你怎么做？
如果您乐意根据经验进行估算,则可以衡量指数增加数量的操作所需的时间.使用该比率,您可以获得您估计的功能.
例如,如果1000次操作与10000次操作的比率(10x)是(先测试较长的操作)您需要进行实际操作次数以查看您所拥有的范围的顺序.
它只是一个估计值,因为时间复杂度是针对理想的机器而且应该可以通过数学证明而不是测量.
例如,许多人试图凭经验证明PI是一个分数.当他们测量圆圈与直径的比例时,他们已经确定它总是一小部分.最终,人们普遍认为PI不是一个分数.
我们最近实现了一个工具，可以对 JVM 代码进行半自动平均运行时间分析。您甚至不必访问源。它尚未发布（仍在解决一些可用性缺陷）但我希望很快就会发布。
它基于程序执行的最大似然模型[1]。简而言之，字节码增加了成本计数器。然后在您控制分布的一堆输入上运行（分布式，如果需要）目标算法。使用涉及的启发式方法（裂缝上的最小二乘法，排序）将聚合计数器外推到函数。从这些中，更多的科学导致对平均运行时渐近的估计（3.576n - 1.23log(n) + 1.7例如）。例如，该方法能够以高精度重现 Knuth 和 Sedgewick 所做的严格经典分析。
与其他人发布的内容相比，这种方法的一大优势是您独立于时间估计，尤其是独立于机器、虚拟机甚至编程语言。你真的得到了关于你的算法的信息，没有所有的噪音。
而且——可能是杀手级功能——它带有一个完整的 GUI，可指导您完成整个过程。
有关更多详细信息和进一步参考，请参阅我在 cs.SE上的回答。您可以在此处找到一个初步网站（包括该工具的测试版和已发表的论文）。
（请注意，平均运行时间可以这样估计，而最坏情况运行时间永远不可能，除非您知道最坏情况。如果您知道最坏情况，您可以使用平均情况进行最坏情况分析；只需向工具提供最坏情况实例. 一般来说，运行时界限是无法确定的。）