Obtención programática de la eficiencia Big-O del código

https://stackoverflow.com/questions/480775

20-08-2019
|

Pregunta

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

Si graficara una función O (n) frente a una función O (n lg n) creo que podría determinar visualmente cuál es cuál; Creo que debe haber alguna solución heurística que permita que esto se haga automáticamente.

¿Alguna idea?

Editar: Estoy feliz de encontrar una solución semiautomática, solo me pregunto si hay alguna forma de evitar hacer un análisis totalmente manual.

Solución

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

Simplemente respondiendo la pregunta " ¿Alguna vez se ejecutará esta línea de código? " sería muy difícil, si no imposible, en el caso general.

Editado para agregar: Aunque el caso general es intratable, vea 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 intratable sigue siendo intratable incluso cuando se agrega un ser humano al sistema / máquina. Tras una reflexión adicional, supongo que una solución del 99% puede ser factible, e incluso podría funcionar tan bien o mejor que un ser humano.

Otros consejos

Puede ejecutar el algoritmo en varios conjuntos de datos de tamaño, y luego puede usar el ajuste de curva para obtener una aproximación. (Simplemente mirando la curva que crea probablemente será suficiente en la mayoría de los casos, pero cualquier paquete estadístico tiene ajuste de curva).

Tenga en cuenta que algunos algoritmos exhiben una forma con conjuntos de datos pequeños, pero otra 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 en el mundo real que (para pequeños conjuntos de datos) no funciona tan bien como el algoritmo teóricamente mejor.

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

Debido a los problemas con la definición de " ¿qué 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. Al optimizar el rendimiento y seleccionar entre dos algoritmos, el mundo real & "; El caucho sale a la carretera &"; test 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 a medida que n se acerca al infinito, el término n^3 dominará la función, independientemente de la constante k.

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

Tengo curiosidad por saber por qué 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 preguntan. Lo más probable es que se pregunte cuál es el rendimiento realista de dicho algoritmo para datos probables. Calcular el Big-O de una función es de utilidad razonable, pero hay muchos aspectos que pueden cambiar el & "; Rendimiento de tiempo de ejecución real &"; de un algoritmo en uso real que nada supera la instrumentación y las pruebas.

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

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 big-O ... pero uno de ellos usa la ordinalidad de fila y uno de ellos usa la 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 dependiendo del tamaño real de la matriz foo. Esto ni siquiera comienza a tocar las características de rendimiento reales de cómo se comporta el algoritmo si es parte de una pieza de software que tiene cierta concurrencia integrada.

No es un nelly negativo, pero big-O es una herramienta con un alcance limitado. Es de gran utilidad si está profundamente inmerso en el análisis algorítmico o si está tratando de probar algo sobre un algoritmo, pero si está haciendo un desarrollo de software comercial, la prueba está en el budín, y va querer tener números de rendimiento reales para tomar decisiones inteligentes.

¡Salud!

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

La complejidad del algoritmo no es una & "; programación &"; pregunta; es un " informática " pregunta. Para responder a la pregunta es necesario analizar el código desde la perspectiva de un matemático, de modo que calcular la complejidad de Big-O es prácticamente una forma de prueba matemática. Requiere una comprensión muy sólida de las operaciones informáticas fundamentales, álgebra, tal vez cálculo (límites) y lógica. No hay cantidad de & Quot; prueba & Quot; puede ser sustituido por ese proceso.
Se aplica el problema de detención, por lo que la complejidad de un algoritmo es fundamentalmente indecidible por una máquina.
Se aplican los límites de las herramientas automatizadas , por lo que podría ser posible escribir un programa para ayudar, pero solo podría ayudar tanto como una calculadora ayuda con la tarea de física, o tanto como un navegador de refactorización ayuda con la reorganización de una base de código.
Para cualquiera que esté considerando seriamente escribir una herramienta de este tipo, sugiero el siguiente ejercicio. Elija un algoritmo razonablemente simple, como su tipo favorito, como su algoritmo sujeto. Obtenga una referencia sólida (libro, tutorial basado en la web) para guiarlo a través del proceso de cálculo de la complejidad del algoritmo y, en última instancia, el & Quot; Big-O & Quot ;. Documente sus pasos y resultados a medida que avanza en el proceso con su algoritmo de materia. Realice los pasos y documente su progreso para varios escenarios, como el mejor de los casos, el peor de los casos y el caso promedio. Una vez que haya terminado, revise su documentación y pregúntese qué se necesitaría para escribir un programa (herramienta) para hacerlo por usted. Se puede hacer? ¿Cuánto se automatizaría realmente y cuánto seguiría siendo manual?

Mis mejores deseos.

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

Podrías engañarte visualmente muy fácilmente.

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

Prueba de que esto es indecidible:

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

Sea P el siguiente programa:

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

Dado que la función y el programa son fijos, HALTS_IN_FN en esta entrada es tiempo constante. Si HALTS_IN_FN devuelve verdadero, el programa se ejecuta para siempre y, por supuesto, no se detiene en O (f (n)) para ninguna f (n). Si HALTS_IN_FN devuelve falso, el programa se detiene en O (1) tiempo.

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

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

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

TAMBIÉN, si pudiera escribir este programa, 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 insoluble en teoría. Es justo, pero más allá de eso, incluso resolverlo para cualquiera de los casos más triviales parecería increíblemente difícil.

Digamos que tiene un programa que tiene un conjunto de bucles anidados, cada uno basado en el número de elementos en una matriz. O (n ^ 2). Pero, ¿qué pasa si el ciclo interno solo se ejecuta en un conjunto de circunstancias muy específico? Digamos, en promedio, que se ejecuta en casos de log (n) aprox. De repente nuestra & Quot; obviamente & Quot; El algoritmo O (n ^ 2) es realmente O (n log n). Escribir un programa que pueda determinar si se ejecutará el bucle interno y con qué frecuencia es potencialmente más difícil que el problema original.

Recuerda que O (N) no es dios; altas constantes pueden y cambiarán el campo de juego. Los algoritmos de clasificación rápida son O (n log n), por supuesto, pero cuando la recursividad se reduce lo suficiente, digamos hasta 20 elementos, muchas implementaciones de clasificación rápida cambiarán las tácticas a un algoritmo separado, ya que en realidad es más rápido hacer un tipo diferente de clasificación , digamos el tipo de inserción con peor O (N), pero una constante mucho más pequeña.

Entonces, comprenda sus datos, haga conjeturas educadas y pruebe.

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

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 & # 178;), pero generalmente O (nlogn). Para dos entradas del mismo tamaño.

El vendedor viajero es (creo que no estoy seguro) O (n & # 178;) ( 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 evaluación comparativa debe adaptarse la mayor parte del tiempo de manera 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 forma totalmente automática ya que el tipo y la estructura de la entrada difieren mucho entre las funciones.

No sé cuál es su objetivo al hacer esto, pero tuvimos un problema similar en un curso que estaba enseñando. Se requirió que los estudiantes implementaran algo que funciona con cierta complejidad.

Para no repasar su solución manualmente y leer su código, utilizamos el método sugerido por @Godeke. El objetivo era encontrar estudiantes que usaran una lista enlazada en lugar de un árbol de búsqueda equilibrado, o estudiantes que implementaran el ordenamiento de burbujas en lugar del ordenamiento en montón (es decir, implementaciones que no funcionan en la complejidad requerida, pero sin leer realmente su código).

Sorprendentemente, los resultados no revelaron estudiantes que hicieron trampa. Eso podría deberse a que nuestros estudiantes son honestos y quieren aprender (o simplemente sabían que revisaremos esto ;-)). Es posible pasar por alto a los estudiantes que hacen trampa si las entradas son pequeñas, o si la entrada en sí está ordenada o algo así. También es posible estar equivocado acerca de los estudiantes que no hicieron trampa, pero que tienen grandes valores constantes.

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

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

Primera vez que el algoritmo, ejecutándolo en la entrada de varios n . Trace los puntos en un gráfico de log-log . Dibuja la línea que mejor se ajuste a través de 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. Debe tomar todo esto con un grano de sal. Pero en realidad lo he hecho en el contexto de pruebas automatizadas para regresiones de rendimiento. El parche aquí contiene algunos códigos JS para él.

Estoy usando una biblioteca big_O ( enlace aquí ) que se ajusta al cambio en la ejecución tiempo 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 recopilados contra el comportamiento de crecimiento de cada clase.

Verifique 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ía con varias muestras y haré una regresión lineal, luego simplemente tome el término más alto.

Es fácil obtener una indicación (por ejemplo, " ¿es la función lineal? sub-lineal? polinomial? exponencial ")

Es difícil encontrar la complejidad exacta.

Por ejemplo, aquí hay una solución de Python: 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 realizar análisis de regresión . Lo multiplica una vez por velocidad, para obtener una indicación realmente buena, tendría que cronometrarlo muchas veces para minimizar la interferencia de factores ambientales (por ejemplo, con 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 en el tipo de 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)

Esta impreso en mi máquina:

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

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow