Obteniendo programáticamente la eficiencia de código Big-O

Me pregunto si hay alguna manera automática de determinar (al menos aproximadamente) la complejidad de tiempo de Big-O de una función dada.

Si representé una función O (n) frente a una función O (n lg n), creo que sería capaz de determinar visualmente cuál es cuál; Estoy pensando que debe haber alguna solución heurística que permita que esto se haga automáticamente.

¿Algunas ideas?

Editar: estoy feliz de encontrar una solución semiautomatizada, preguntándome si hay alguna manera de evitar hacer un análisis completamente manual.

Parece que lo que estás pidiendo es una extensión del problema de detención. No creo que tal cosa sea posible, ni siquiera en teoría.

Simplemente respondiendo a la pregunta “¿Se ejecutará alguna vez esta línea de código?” sería muy difícil si no imposible de hacer en el caso general.

Editado para agregar: aunque el caso general es intratable, consulte aquí una solución parcial: http://research.microsoft.com/apps/pubs/default.aspx?id=104919

Además, algunos han declarado que hacer el análisis a mano es la única opción, pero no creo que sea realmente la forma correcta de verlo. Un problema difícil de resolver sigue siendo insoluble incluso cuando se agrega un ser humano al sistema / máquina. Luego de una reflexión más profunda, supongo que una solución al 99% puede ser factible, e incluso podría funcionar tan bien o mejor que un humano.

Puede ejecutar el algoritmo en varios conjuntos de datos de tamaño y, a continuación, puede usar el ajuste de curva para obtener una aproximación. (Basta con mirar la curva que cree que será suficiente en la mayoría de los casos, pero cualquier paquete estadístico tiene ajuste de curvas).

Tenga en cuenta que algunos algoritmos muestran una forma con pequeños conjuntos de datos, pero otro con grandes … y la definición de grande sigue siendo un poco nebulosa. Esto significa que un algoritmo con una buena curva de rendimiento podría tener tanta sobrecarga del mundo real que (para conjuntos de datos pequeños) no funciona tan bien como el algoritmo teóricamente mejor.

En cuanto a las técnicas de inspección del código , ninguna existe. Pero instrumentar su código para ejecutar en varias longitudes y generar un archivo simple (RunSize RunLength sería suficiente) debería ser fácil. Generar datos de prueba adecuados podría ser más complejo (algunos algoritmos funcionan mejor / peor con datos ordenados parcialmente, por lo que querría generar datos que representaran su caso de uso normal ).

Debido a los problemas con la definición de “lo que es grande” y el hecho de que el rendimiento depende de los datos, encuentro que el análisis estático a menudo es engañoso. Cuando optimizo el rendimiento y selecciono entre dos algoritmos, la prueba del mundo real “huye a la carretera” es el único árbitro final en el que confío.

Una respuesta corta es que es imposible porque las constantes importan .

Por ejemplo, podría escribir una función que se ejecute en O((n^3/k) + n^2) . Esto se simplifica a O (n ^ 3) porque como n se acerca al infinito, el término n^3 dominará la función, independientemente de la constante k .

Sin embargo, si k es muy grande en la función de ejemplo anterior, la función parecerá ejecutarse en casi exactamente n^2 hasta algún punto de cruce, en el cual el término n^3 comenzará a dominar. Debido a que la constante k será desconocida para cualquier herramienta de generación de perfiles, será imposible saber qué tan grande es un conjunto de datos para probar la función objective. Si k puede ser arbitrariamente grande, no puede crear datos de prueba para determinar el tiempo de ejecución de “oh”.

Tengo curiosidad de por qué es que quieres poder hacer esto. En mi experiencia, cuando alguien dice: “Quiero determinar la complejidad del tiempo de ejecución de este algoritmo”, no preguntan qué creen que están haciendo. Lo que probablemente esté preguntando es cuál es el rendimiento realista de dicho algoritmo para los datos probables. Calcular el Big-O de una función es de una utilidad razonable, pero hay tantos aspectos que pueden cambiar el “rendimiento del tiempo de ejecución real” de un algoritmo en uso real que nada supera a la instrumentación y las pruebas.

Por ejemplo, los siguientes algoritmos tienen el mismo Big-O exacto (pseudocódigo raro):

ejemplo a:

 huge_two_dimensional_array foo for i = 0, i < foo[i].length, i++ for j = 0; j < foo[j].length, j++ do_something_with foo[i][j] 

ejemplo b:

 huge_two_dimensional_array foo for j = 0, j < foo[j].length, j++ for i = 0; i < foo[i].length, i++ do_something_with foo[i][j] 

Nuevamente, exactamente el mismo gran O ... pero uno de ellos usa ordinalidad de fila y uno de ellos usa ordinalidad de columna. Resulta que debido a la localidad de referencia y la coherencia de la memoria caché, es posible que tenga dos tiempos de ejecución reales completamente diferentes, especialmente según el tamaño real de la matriz foo. Esto ni siquiera comienza a tocar las características de rendimiento real de cómo se comporta el algoritmo si es parte de un software que tiene alguna concurrencia incorporada.

No es una negación negativa, pero la gran O es una herramienta con un scope estrecho. Es de gran utilidad si se encuentra en el análisis algorítmico profundo o si está tratando de probar algo sobre un algoritmo, pero si está haciendo un desarrollo de software comercial, la prueba está en el pudín, y va a querer tener números de rendimiento real para tomar decisiones inteligentes

¡Aclamaciones!

Me sorprende ver tantos bashs de afirmar que uno puede “medir” la complejidad con un cronómetro. Varias personas han dado la respuesta correcta, pero creo que todavía hay espacio para conducir el punto esencial a casa.

  1. La complejidad del algoritmo no es una pregunta de “progtwigción”; es una pregunta de “informática”. Responder a la pregunta requiere analizar el código desde la perspectiva de un matemático, de modo que la computación de la complejidad de Big-O sea prácticamente una forma de demostración matemática. Requiere una comprensión muy fuerte de las operaciones informáticas fundamentales, el álgebra, quizás el cálculo (límites) y la lógica. Ninguna cantidad de “prueba” puede ser sustituida por ese proceso.

  2. El problema de detención se aplica, por lo que la complejidad de un algoritmo es fundamentalmente indecidible por una máquina.

  3. Se aplican los límites de las herramientas automatizadas , por lo que podría ser posible escribir un progtwig para ayudar, pero solo podría ayudar tanto como una calculadora ayuda con la tarea física de uno, o tanto como un navegador de refactorización ayuda a reorganizar un progtwig. código base

  4. Para cualquier persona que considere seriamente escribir una herramienta de este tipo, sugiero el siguiente ejercicio. Elija un algoritmo razonablemente simple, como su clasificación favorita, como su algoritmo sujeto. Obtenga una referencia sólida (libro, tutorial basado en la web) para guiarlo en el proceso de cálculo de la complejidad del algoritmo y, en última instancia, del “Big-O”. Documente sus pasos y resultados a medida que avanza en el proceso con su algoritmo sujeto. Realice los pasos y documente su progreso para varios escenarios, como el mejor de los casos, el peor caso y el promedio de casos. Una vez que haya terminado, revise su documentación y pregúntese qué se necesitaría para escribir un progtwig (herramienta) para que lo haga por usted. Se puede hacer? ¿Cuánto se automatizaría realmente y cuánto sería aún manual?

Los mejores deseos.

Esto podría funcionar para algoritmos simples, pero ¿qué pasa con O (n ^ 2 lg n), o O (n lg ^ 2 n)?

Podrías ser engañado visualmente muy fácilmente.

Y si es un algoritmo realmente malo, tal vez no volvería incluso en n = 10.

Prueba de que esto es indecidible:

Supongamos que tenemos algún algoritmo HALTS_IN_FN (Progtwig, función) que determina si un progtwig se detuvo en O (f (n)) para todo n, para alguna función f.

Deje que P sea el siguiente progtwig:

 if(HALTS_IN_FN(P,f(n))) { while(1); } halt; 

Como la función y el progtwig son fijos, HALTS_IN_FN en esta entrada es de tiempo constante. Si HALTS_IN_FN devuelve verdadero, el progtwig se ejecuta para siempre y, por supuesto, no se detiene en O (f (n)) para cualquier f (n). Si HALTS_IN_FN devuelve falso, el progtwig se detiene en O (1) vez.

Por lo tanto, tenemos una paradoja, una contradicción, por lo que el progtwig es indecidible.

Creo que es prácticamente imposible hacer esto automáticamente. Recuerde que O (g (n)) es el límite superior del peor de los casos y que muchas funciones funcionan mejor que para muchos conjuntos de datos. Tendría que encontrar el conjunto de datos del peor caso para cada uno para poder compararlos. Esa es una tarea difícil por sí sola para muchos algoritmos.

Jeffrey L Whitledge es correcto. Una simple reducción del problema de detención demuestra que esto es indecidible …

TAMBIÉN, si pudiera escribir este progtwig, lo usaría para resolver P vs NP, y tendría $ 1 millón … B-)

Mucha gente ha comentado que este es un problema inherentemente irresoluble en teoría. Bastante, pero más allá de eso, incluso resolverlo para cualquier caso menos trivial parecería ser increíblemente difícil.

Digamos que tiene un progtwig que tiene un conjunto de bucles nesteds, cada uno basado en la cantidad de elementos en una matriz. O (n ^ 2). Pero, ¿y si el ciclo interno solo se ejecuta en un conjunto de circunstancias muy específicas? Digamos que, en promedio, se ejecuta en aproximadamente log (n) casos. De repente, nuestro algoritmo “obviamente” O (n ^ 2) es realmente O (n log n). Escribir un progtwig que pueda determinar si el ciclo interno se ejecutará y con qué frecuencia es potencialmente más difícil que el problema original.

Recuerde que O (N) no es dios; las constantes altas pueden cambiar el campo de juego y lo harán. Los algoritmos de Quicksort son O (n log n) por supuesto, pero cuando la recursión es lo suficientemente pequeña, digamos hasta 20 elementos, muchas implementaciones de quicksort cambiarán las tácticas a un algoritmo separado ya que es más rápido hacer un tipo diferente de ordenación , digamos inserción tipo con peor O (N), pero una constante mucho menor.

Por lo tanto, entienda sus datos, haga conjeturas y pruebe.

Bueno, como no puedes probar si una función incluso se detiene, creo que estás pidiendo un poco.

De lo contrario, @Godeke lo tiene.

También debe tener cuidado al ejecutar dichos puntos de referencia. Algunos algoritmos tendrán un comportamiento muy dependiente del tipo de entrada.

Tome Quicksort, por ejemplo. Es el peor de los casos O (n²), pero generalmente O (nlogn). Para dos entradas del mismo tamaño.

El vendedor ambulante es (creo, no estoy seguro) O (n²) ( EDITAR: el valor correcto es 0 (n!) Para el algoritmo de fuerza bruta ), pero la mayoría de los algoritmos obtienen soluciones aproximadas bastante buenas mucho más rápido.

Esto significa que la estructura de benchmarking se ha adaptado la mayoría de las veces de forma ad hoc. Imagine escribir algo genérico para los dos ejemplos mencionados. Sería muy complejo, probablemente inutilizable, y probablemente dará resultados incorrectos de todos modos.

Supongo que esto no es posible de manera totalmente automática ya que el tipo y la estructura de la entrada difieren mucho entre las funciones.

No sé cuál es tu objective al hacer esto, pero tuvimos un problema similar en un curso que estaba enseñando. Los estudiantes debían implementar algo que funciona con cierta complejidad.

Para no revisar su solución manualmente y leer su código, usamos el método sugerido por @Godeke. El objective era encontrar estudiantes que utilizaran la lista vinculada en lugar de un árbol de búsqueda de balansed, o estudiantes que implementaran la ordenación de burbuja en lugar de ordenación de stack (es decir, implementaciones que no funcionan con la complejidad requerida, pero sin leer su código).

Sorprendentemente, los resultados no revelaron a los estudiantes que hicieron trampa. Eso puede deberse a que nuestros estudiantes son honestos y quieren aprender (o simplemente saben que vamos a verificar esto ;-)). Es posible perder a los estudiantes que hacen trampa si las entradas son pequeñas, o si la entrada en sí está ordenada o tal. También es posible equivocarse con los estudiantes que no hicieron trampas, pero que tienen grandes valores constantes.

Pero a pesar de los posibles errores, vale la pena, ya que ahorra mucho tiempo de control.

Como otros han dicho, esto es teóricamente imposible. Pero en la práctica, puede adivinar si una función es O ( n ) u O ( n ^ 2), siempre y cuando no le importe equivocarse algunas veces.

La primera vez que el algoritmo, ejecutarlo en la entrada de varios n . Trace los puntos en un gráfico log-log . Dibuja la línea que mejor se ajusta a los puntos. Si la línea se ajusta bien a todos los puntos, entonces los datos sugieren que el algoritmo es O ( n ^ k ), donde k es la pendiente de la línea.

No soy un estadístico. Deberías tomar todo esto con un grano de sal. Pero en realidad lo he hecho en el contexto de las pruebas automatizadas para las regresiones de rendimiento. El parche aquí contiene algún código JS para él.

Estoy usando una biblioteca big_O ( enlace aquí ) que se ajusta al cambio en el tiempo de ejecución contra la variable independiente n para inferir el orden de la clase de crecimiento O() .

El paquete sugiere automáticamente la clase de mejor ajuste al medir el residuo de los datos recostackdos con cada comportamiento de crecimiento de la clase.

Verifica el código en esta respuesta .

Ejemplo de salida,

 Measuring .columns[::-1] complexity against rapid increase in # rows -------------------------------------------------------------------------------- Big O() fits: Cubic: time = -0.017 + 0.00067*n^3 -------------------------------------------------------------------------------- Constant: time = 0.032 (res: 0.021) Linear: time = -0.051 + 0.024*n (res: 0.011) Quadratic: time = -0.026 + 0.0038*n^2 (res: 0.0077) Cubic: time = -0.017 + 0.00067*n^3 (res: 0.0052) Polynomial: time = -6.3 * x^1.5 (res: 6) Logarithmic: time = -0.026 + 0.053*log(n) (res: 0.015) Linearithmic: time = -0.024 + 0.012*n*log(n) (res: 0.0094) Exponential: time = -7 * 0.66^n (res: 3.6) -------------------------------------------------------------------------------- 

Si tiene muchos recursos computacionales homogéneos, los compararé con varias muestras y haré una regresión lineal, luego simplemente tomaré el término más alto.

Es fácil obtener una indicación (por ejemplo, “¿es la función lineal? ¿Sub-lineal? Polinómica? Exponencial”)

Es difícil encontrar la complejidad exacta.

Por ejemplo, aquí hay una solución de Python: usted proporciona la función y una función que crea parámetros de tamaño N para ella. Obtiene una lista de valores (n, tiempo) para trazar, o para realizar análisis de regresión . Lo multiplica por una vez por la velocidad, para obtener una buena indicación de que tendría que cronometrarlo muchas veces para minimizar la interferencia de factores ambientales (por ejemplo, con el módulo timeit ).

 import time def measure_run_time(func, args): start = time.time() func(*args) return time.time() - start def plot_times(func, generate_args, plot_sequence): return [ (n, measure_run_time(func, generate_args(n+1))) for n in plot_sequence ] 

Y para usarlo para ordenar la burbuja de tiempo:

 def bubble_sort(l): for i in xrange(len(l)-1): for j in xrange(len(l)-1-i): if l[i+1] < l[i]: l[i],l[i+1] = l[i+1],l[i] import random def gen_args_for_sort(list_length): result = range(list_length) # list of 0..N-1 random.shuffle(result) # randomize order # should return a tuple of arguments return (result,) # timing for N = 1000, 2000, ..., 5000 times = plot_times(bubble_sort, gen_args_for_sort, xrange(1000,6000,1000)) import pprint pprint.pprint(times) 

Esto impreso en mi máquina:

 [(1000, 0.078000068664550781), (2000, 0.34400010108947754), (3000, 0.7649998664855957), (4000, 1.3440001010894775), (5000, 2.1410000324249268)]