Pour commencer, vous avez à faire quelques hypothèses.
-
n est grand par rapport à toutes les constantes.
- Vous pouvez effectivement aléatoire, vos données d'entrée
- Vous pouvez échantillon avec une densité suffisante pour obtenir une bonne poignée sur la distribution de temps de fonctionnement
En particulier, (3) est difficile à réaliser, de concert avec (1). De sorte que vous pouvez obtenir quelque chose avec une exponentielle pire des cas, mais ne jamais courir dans le pire des cas, et donc pense que votre algorithme est beaucoup mieux que c'est une moyenne.
Avec cela dit, vous n'avez besoin que de toute norme d'ajustement de la courbe de la bibliothèque. Apache Commons Mathématiques est totalement adéquat. Ensuite, vous créez une fonction avec tous les termes courants que vous souhaitez tester (par exemple, constant, journal de n, n, n log n, n*n n*n*n, e^n), ou vous prenez le journal de vos données et l'ajustement de l'exposant, et puis si vous obtenez un exposant pas proche d'un entier, voir si le lancer dans une du journal n donne un meilleur ajustement.
(Plus en détail, si vous correspondez C*x^a pour C et a, ou plus facilement, log C + a log x, vous pouvez obtenir de l'exposant a; dans la commune de termes-à-une fois de régime, vous obtiendrez de pondération pour chaque terme, donc si vous avez n*n + C*n*log(n) où C est grand, vous allez ramasser ce terme aussi.)
Vous aurez envie de faire varier la taille par un nombre suffisant de sorte que vous pouvez dire les différents cas à part (peut-être dur avec le journal termes, si vous vous souciez de celles-ci), et en toute sécurité plus de différentes tailles que vous avez des paramètres (probablement 3x excès serait de commencer à être d'accord, aussi longtemps que vous le faites au moins une douzaine de pistes au total).
Edit: Voici la Scala de code qui fait tout pour vous. Plutôt que d'expliquer chaque petit morceau, je vais le laisser à vous d'enquêter, il met en œuvre le schéma ci-dessus en utilisant le C*x^un ajustement, et renvoie ((a,C),(limite inférieure pour une, limite supérieure pour l'un)). Les limites sont assez conservatrices, comme vous pouvez le voir à partir de l'exécution de la chose plusieurs fois. Les unités de C sont des secondes (a est sans unité), mais n'ont pas confiance que trop bien qu'il y a une boucle de frais généraux (et aussi un peu de bruit).
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))
}
}
Notez que l' multibench méthode devrait prendre environ sqrt(2)*m*n*de temps à s'exécuter, en supposant que l'initialisation statique de données est utilisée et est relativement bon marché par rapport à ce que vous êtes en cours d'exécution. Voici quelques exemples avec les paramètres choisis pour prendre ~15s à exécuter:
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
De toute façon, pour l'usage indiqué cas où vous êtes en vérifiant que l'ordre ne change pas--c'est sans doute suffisant, puisque vous pouvez jouer avec les valeurs un peu lors de la configuration de test pour s'assurer qu'ils donnent quelque chose de sensé. On pourrait aussi créer une méthode heuristique de recherche pour plus de stabilité, mais c'est probablement excessif.
(Soit dit en passant, n'est pas explicite chauffe pas ici; le robuste montage de le Theil-Sen estimateur devrait rendre inutile pour sensiblement les grands repères. C'est aussi pourquoi je n'utilise pas d'autres doivent être coupées cadre; toutes les statistiques qu'il ne perd de la puissance de ce test.)
Edit encore: si vous remplacez l' alpha méthode avec les éléments suivants:
// 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)
}
ensuite, vous pouvez obtenir une estimation de l'exposant quand il y a un journal terme--erreur des estimations existent pour choisir si le journal terme ou pas, c'est la bonne façon de procéder, mais c'est à vous de faire l'appel (c'est à dire que je suis en supposant que vous allez superviser le commencement et la lecture des nombres qui se détachent):
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)
(Edit: correction du calcul RMS c'est donc en fait la moyenne, plus démontré que vous ne devez faire les timings une fois et peut ensuite essayer les deux ajustements.)
