Чтобы начать, вам нужно сделать пару предположений.
n велико по сравнению с любыми постоянными терминами. - Вы можете эффективно рандомизировать свой вводdata
- Вы можете производить выборку с достаточной плотностью, чтобы получить хорошее представление о распределении времени выполнения
В частности, (3) трудно достичь в сочетании с (1).Таким образом, вы можете получить что-то с экспоненциальным наихудшим случаем, но никогда не столкнетесь с этим наихудшим случаем и, таким образом, думаете, что ваш алгоритм намного лучше, чем в среднем.
С учетом сказанного все, что вам нужно, это любая стандартная криваяпримерочная библиотека. Apache Commons Math полностью соответствует.Затем вы либо создаете функцию со всеми общими терминами, которые вы хотите проверить (например, константа, log n, n, n log n, n n, n n * n, e ^ n), либо вывозьмите журнал ваших данных и подгоните экспоненту, а затем, если вы получите показатель, не близкий к целому числу, посмотрите, дает ли подбрасывание в журнал n лучшее соответствие.
(Более подробно, если вы подходитеC*x^a для C и a, или более просто log C + a log x, вы можете получить показатель степени a, в схеме «все общие условия сразу» вы получите весовые коэффициенты для каждого термина,поэтому, если у вас есть n*n + C*n*log(n), где C большое, вы также подберете этот термин.)
Вы захотите изменить размер на столько, чтобы вы могли различать разные случаи (может быть сложно с лог-терминами, если вы заботитесь об этом), и безопасно больше размеров, чем у вас есть параметры (возможно, 3-кратное превышение будет в порядке, если вы выполняете по крайней мере дюжину или около того прогонов).
Редактировать: Вот код Scala, который делает все это за вас.Вместо того, чтобы объяснять каждый маленький кусочек, я оставлю это вам для расследования;он реализует схему выше, используя C * x ^ a fit, и возвращает ((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 * времени для запуска, при условии, что используются статические данные инициализации и относительно дешево по сравнению с тем, что вы используете.Вот несколько примеров с параметрами, выбранными для запуска ~ 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
В любом случае, для заявленного варианта использования - когда вы проверяете, чтобы убедиться, что порядок не меняется - это, вероятно,достаточно, так как вы можете немного поиграть со значениями при настройке теста, чтобы убедиться, что они дают что-то разумное.Можно также создать эвристику, которая ищет стабильность, но это, вероятно, излишне.
(Между прочим, здесь нет явного шага разогрева; надежная подгонка оценки Тейла-Сена должна сделать его ненужным для разумно больших тестов.По этой же причине я не использую никакую другую среду для тестирования: любая статистика, которая делает это, просто теряет энергию из этого теста.)
Редактируйте снова: если вы замените метод 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, так что это фактически среднее значение, плюс продемонстрированочто вам нужно сделать только один раз, а затем попробовать обе попытки.)