java - produccion - Estimando empíricamente la eficiencia del tiempo de los grandes oh
indicadores de eficiencia formulas (9)
Fondo
Me gustaría estimar el gran rendimiento de algunos métodos en una biblioteca a través de puntos de referencia. No necesito precisión, basta con mostrar que algo es O (1), O (logn), O (n), O (nlogn), O (n ^ 2) o peor que eso. Dado que big-oh significa límite superior, estimar O (logn) para algo que es O (log logn) no es un problema.
En este momento, estoy pensando en encontrar el multiplicador constante k que mejor se ajusta a los datos para cada Big-oh (pero superará todos los resultados), y luego elegir el Big-oh con la mejor opción.
Preguntas
- ¿Hay mejores maneras de hacerlo de lo que estoy hablando? Si es así, ¿Que son?
- De lo contrario, ¿alguien puede indicarme los algoritmos para estimar k para una mejor adaptación y comparar qué tan bien encaja cada curva con los datos?
Notas y restricciones
Teniendo en cuenta los comentarios hasta ahora, debo aclarar algunas cosas:
- Esto necesita ser automatizado. No puedo "mirar" los datos y hacer una llamada de juicio.
- Voy a comparar los métodos con múltiples
ntamaños. Para cada tamañon, voy a utilizar un marco de referencia comprobado que proporciona resultados estadísticos confiables. - De hecho, sé de antemano el gran oh de la mayoría de los métodos que se probarán. Mi principal intención es proporcionar pruebas de regresión de rendimiento para ellos.
- El código se escribirá en Scala y se puede usar cualquier biblioteca de Java gratuita.
Ejemplo
Aquí hay un ejemplo del tipo de cosas que quiero medir. Tengo un método con esta firma:
def apply(n: Int): A
Dado un n , devolverá el enésimo elemento de una secuencia. Este método puede tener O (1), O (logn) u O (n) dadas las implementaciones existentes, y los pequeños cambios pueden hacer que use una implementación subóptima por error. O, más fácilmente, podría obtener algún otro método que dependa de él para usar una versión subóptima.
De hecho, sé de antemano el gran oh de la mayoría de los métodos que se probarán. Mi principal intención es proporcionar pruebas de regresión de rendimiento para ellos.
Este requisito es clave. Desea detectar valores atípicos con datos mínimos (porque las pruebas deben ser rápidas , maldita sea) y, en mi experiencia, adaptar las curvas a las evaluaciones numéricas de recurrencias complejas, la regresión lineal y similares se sobreajustará. Creo que tu idea inicial es buena.
Lo que haría para implementarlo es preparar una lista de las funciones de complejidad esperadas g1, g2, ..., y para los datos f, probar qué tan cerca de la constante f / gi + gi / f es para cada i. Con una función de costo por mínimos cuadrados, esto solo es calcular la variance de esa cantidad para cada i y reportar la más pequeña. Observe las variaciones al final e inspeccione manualmente los ajustes inusualmente deficientes.
Debería considerar cambiar aspectos críticos de su tarea.
Cambie la terminología que está utilizando para: "estimar el tiempo de ejecución del algoritmo" o "prueba de regresión de rendimiento de configuración"
¿Puedes estimar el tiempo de ejecución del algoritmo? Bueno, propones probar diferentes tamaños de entrada y medir alguna operación crítica o el tiempo que toma. Luego, para la serie de tamaños de entrada, usted planea estimar programáticamente si el tiempo de ejecución del algoritmo no tiene crecimiento, crecimiento constante, crecimiento exponencial, etc.
Entonces tiene dos problemas, ejecutar las pruebas y calcular de forma programática la tasa de crecimiento a medida que ingresa el conjunto. Esto suena como una tarea razonable.
Lo que estás buscando lograr es imposible en general. Incluso el hecho de que un algoritmo llegue a detenerse alguna vez no se puede probar en un caso general (ver el problema de detención ). E incluso si se detiene en sus datos, aún no puede deducir la complejidad ejecutándola. Por ejemplo, sort de burbuja tiene complejidad O (n ^ 2), mientras que en los datos ya ordenados se comporta como si fuera O (n). No hay forma de seleccionar datos "apropiados" para un algoritmo desconocido para estimar su peor caso.
No creo que tu enfoque funcione en general.
El problema es que la complejidad de "O grande" se basa en un límite ya que algunas variables de escala tienden a infinito. Para valores más pequeños de esa variable, el comportamiento de rendimiento puede parecer que se ajusta completamente a una curva diferente.
El problema es que con un enfoque empírico nunca se puede saber si la variable de escala es lo suficientemente grande como para que el límite sea aparente en los resultados.
Otro problema es que si implementa esto en Java / Scala, debe hacer todo lo posible para eliminar las distorsiones y el "ruido" en sus tiempos debido a cosas como el calentamiento de JVM (por ejemplo, carga de clases, compilación JIT, cambio de tamaño del montón) y recolección de basura .
Finalmente, nadie va a confiar mucho en las estimaciones empíricas de la complejidad. O al menos, no lo harían si entendieran las matemáticas del análisis de la complejidad.
SEGUIR
En respuesta a este comentario:
La importancia de su estimación mejorará drásticamente cuanto más y más muestras utilice.
Esto es cierto, aunque mi punto es que usted (Daniel) no ha tenido esto en cuenta.
Además, las funciones de tiempo de ejecución suelen tener características especiales que pueden explotarse; por ejemplo, los algoritmos tienden a no cambiar su comportamiento a una gran n.
Para casos simples, sí.
Para casos complicados y casos del mundo real, esa es una suposición dudosa. Por ejemplo:
Supongamos que algún algoritmo utiliza una tabla hash con una matriz de hash primaria grande pero de tamaño fijo, y utiliza listas externas para hacer frente a las colisiones. Para N (== número de entradas) menor que el tamaño de la matriz de hash primaria, el comportamiento de la mayoría de las operaciones parecerá ser
O(1). El verdadero comportamiento deO(N)solo se puede detectar mediante ajuste de curva cuando N es mucho más grande que eso.Supongamos que el algoritmo utiliza mucha memoria o ancho de banda de red. Por lo general, funcionará bien hasta que llegue al límite de recursos, y luego el rendimiento disminuirá considerablemente. ¿Cómo cuentas esto? Si es parte de la "complejidad empírica", ¿cómo se asegura de que llegue al punto de transición? Si quiere excluirlo, ¿cómo lo hace?
No estoy seguro de obtener el 100% de lo que quieres. Pero entiendo que pruebe su propio código, para que pueda modificarlo, por ejemplo, inyecte instrucciones de observación. De lo contrario, podría usar alguna forma de tejido de aspecto?
¿Qué le parece agregar contadores reseteables a sus estructuras de datos y luego aumentarlos cada vez que se invoca una subfunción particular? Puede hacer que los @elidable para que desaparezcan en la biblioteca implementada.
Luego, para un método dado, digamos delete(x) , lo probaría con todo tipo de conjuntos de datos generados automáticamente, tratando de darles algún sesgo, etc., y reunir los conteos. Mientras que Igor señala que no se puede verificar que la estructura de datos nunca viole un límite de O-grande, al menos se podrá afirmar que en el experimento real nunca se excede un conteo de límite dado (por ejemplo, bajar un nodo en un árbol nunca se completa más de 4 * log(n) veces), por lo que puede detectar algunos errores.
Por supuesto, necesitaría ciertas suposiciones, por ejemplo, que llamar a un método es O (1) en su modelo de computadora.
Para comenzar, debe hacer un par de suposiciones.
-
nes grande en comparación con cualquier término constante. - Puede aleatorizar de forma efectiva sus datos de entrada
- Puede muestrear con suficiente densidad para obtener un buen manejo de la distribución de tiempos de ejecución
En particular, (3) es difícil de lograr en concierto con (1). Así que puedes obtener algo con un peor caso exponencial, pero nunca te topes con el peor de los casos, y así piensas que tu algoritmo es mucho mejor de lo que es en promedio.
Dicho esto, todo lo que necesita es cualquier biblioteca de ajuste de curva estándar. Apache Commons Math tiene uno completamente adecuado. A continuación, cree una función con todos los términos comunes que desee probar (por ejemplo, constante, log n, n, n log n, n n, n n * n, e ^ n), o tome el registro de sus datos y ajusta el exponente, y luego si obtienes un exponente no cercano a un número entero, mira si al arrojar un log n se ajusta mejor.
(Más detalladamente, si ajusta C*x^a para C y a , o más fácilmente, log C + a log x , puede obtener el exponente a ; en el esquema de todos los términos comunes a la vez, usted Obtendré pesos para cada término, así que si tiene n*n + C*n*log(n) donde C es grande, también elegirá ese término.
Deseará variar el tamaño lo suficiente para diferenciar los diferentes casos (puede ser difícil con los términos de registro, si le interesan), y de forma segura más tamaños diferentes que usted tiene parámetros (probablemente el exceso 3x comenzaría a ser está bien, siempre y cuando lo haga al menos una docena o más en total).
Editar: Aquí está el código de Scala que hace todo esto por ti. En lugar de explicar cada pequeña pieza, te dejo investigar; implementa el esquema anterior utilizando el ajuste C * x ^ a, y devuelve ((a, C), (límite inferior para a, límite superior para a)). Los límites son bastante conservadores, como se puede ver al ejecutar la cosa un par de veces. Las unidades de C son segundos ( a tiene unidades), pero no confíes demasiado ya que hay un poco de sobrecarga de bucle (y también algo de ruido).
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))
}
}
Tenga en cuenta que se espera que el método multibench tome aproximadamente sqrt (2) n m * tiempo para ejecutarse, suponiendo que se utilizan datos de inicialización estáticos y es relativamente barato en comparación con lo que esté ejecutando. Aquí hay algunos ejemplos con parámetros elegidos para tomar ~ 15s para ejecutar:
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 todos modos, para el caso de uso indicado, donde está comprobando para asegurarse de que el pedido no cambie, esto es probablemente adecuado, ya que puede jugar un poco con los valores al configurar la prueba para asegurarse de que den algo sensato. . También se podrían crear heurísticas que busquen estabilidad, pero eso probablemente sea excesivo.
(Incidentalmente, aquí no hay un paso de calentamiento explícito, la sólida adaptación del estimador Theil-Sen debería hacer innecesario el uso de puntos de referencia sensiblemente grandes. Esta es también la razón por la cual no utilizo ningún otro marco de trabajo; cualquier estadística que simplemente pierda poder de esta prueba).
Editar nuevamente: si reemplaza el método alpha con lo siguiente:
// 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)
}
luego puede obtener una estimación del exponente cuando también hay un término de registro; existen estimaciones de error para elegir si el término del registro o no es el camino correcto, pero depende de usted hacer la llamada (es decir, estoy asumiendo supervisarás esto inicialmente y leerás los números que salen):
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)
(Editar: corrigió el cálculo de RMS, por lo que en realidad es el promedio, además demostró que solo necesita hacer sincronizaciones una vez y luego puede probar ambos ajustes).
Para un análisis empírico de la complejidad del programa, lo que haría sería ejecutar (y cronometrar) el algoritmo con 10, 50, 100, 500, 1000 elementos de entrada, etc. A continuación, puede graficar los resultados y determinar el orden de función más adecuado a partir de los tipos básicos más comunes: constante, logarítmico, lineal, nlogn, cuadrático, cúbico, polinomio superior, exponencial. Esta es una parte normal de la prueba de carga, que asegura que el algoritmo se comporta primero como teorizado, y segundo que cumple las expectativas de rendimiento del mundo real a pesar de su complejidad teórica (un algoritmo de tiempo logarítmico en el que cada paso lleva 5 minutos va perder todas las pruebas de cardinalidad absoluta, excepto las absolutas, en un algoritmo de complejidad cuadrática en el que cada paso es de unos pocos milisegundos).
EDITAR: Rompiéndolo, el algoritmo es muy simple:
Defina una lista, N, de varias cardinalidades para las cuales desea evaluar el rendimiento (10,100,1000,10000, etc.)
Para cada elemento X en N:
Cree un conjunto adecuado de datos de prueba que tenga elementos X.
Inicie un cronómetro, o determine y almacene la hora actual del sistema.
Ejecute el algoritmo sobre el conjunto de prueba de elementos X.
Detenga el cronómetro o determine la hora del sistema nuevamente.
La diferencia entre los tiempos de inicio y finalización es el tiempo de ejecución de su algoritmo sobre los elementos X.
Repita para cada X en N.
Trazar los resultados; dados los elementos X (eje x), el algoritmo toma el tiempo T (eje y). La función básica más cercana que gobierna el aumento en T como X aumenta es su aproximación Big-Oh. Como dijo Raphael, esta aproximación es exactamente eso, y no obtendrá distinciones muy finas, como los coeficientes de N, que podrían marcar la diferencia entre un algoritmo N ^ 2 y un algoritmo 2N ^ 2 (ambos son técnicamente O (N ^ 2) pero dado el mismo número de elementos, uno realizará el doble de rápido).
Recientemente implementamos una herramienta que realiza un análisis semiautomático de tiempo de ejecución promedio para el código JVM. Ni siquiera tiene que tener acceso a las fuentes. Todavía no se ha publicado (todavía está solucionando algunos defectos de usabilidad) pero lo estaré pronto, espero.
Se basa en modelos de máxima probabilidad de ejecución del programa [1]. En resumen, el código de bytes se aumenta con contadores de costos. El algoritmo objetivo se ejecuta (distribuido, si lo desea) en un grupo de entradas cuya distribución usted controla. Los contadores agregados se extrapolan a funciones que usan heurística involucrada (método de mínimos cuadrados en crack, más o menos). De ellos, más ciencia conduce a una estimación de la asintótica promedio de tiempo de ejecución ( 3.576n - 1.23log(n) + 1.7 , por ejemplo). Por ejemplo, el método es capaz de reproducir análisis clásicos rigurosos realizados por Knuth y Sedgewick con gran precisión.
La gran ventaja de este método en comparación con lo que otros publican es que usted es independiente de las estimaciones de tiempo , que es, en particular, independiente de la máquina, la máquina virtual e incluso el lenguaje de programación. Realmente obtienes información sobre tu algoritmo, sin todo el ruido.
Y, probablemente la característica más importante, viene con una GUI completa que lo guía a través de todo el proceso.
Ver mi respuesta en cs.SE para un poco más de detalle y más referencias. Puede encontrar un sitio web preliminar (que incluye una versión beta de la herramienta y los documentos publicados) here .
(Tenga en cuenta que el tiempo de ejecución promedio puede estimarse de esa manera, mientras que el peor de los casos no puede ser, excepto en caso de que conozca el peor caso. Si lo hace, puede usar el caso promedio para el peor de los casos; . En general, los límites de tiempo de ejecución no pueden decidirse , sin embargo).
- Análisis de máxima verosimilitud de algoritmos y estructuras de datos por U. Laube y ME Nebel (2010). [ preprint ]
Si está contento de estimar esto empíricamente, puede medir cuánto tiempo lleva hacer un número exponencialmente creciente de operaciones. Usando la relación puede obtener qué función estima que es.
por ejemplo, si la relación de 1000 operaciones a 10000 operaciones (10x) es (prueba la más larga). Necesitas hacer un número realista de operaciones para ver cuál es el orden para el rango que tienes.
- 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)
Es solo una estimación ya que la complejidad del tiempo está destinada a una máquina ideal y algo debería ser matemáticamente probado en lugar de medidas.
Por ejemplo, muchas personas intentaron demostrar empíricamente que PI es una fracción. Cuando midieron la relación de circunferencia a diámetro para los círculos que habían hecho, siempre fue una fracción. Eventualmente, se aceptó generalmente que PI no es una fracción.