¿Se utiliza el análisis suavizado fuera de la academia?

24

¿El análisis suavizado encontró su camino en el análisis principal de algoritmos? ¿Es común que los diseñadores de algoritmos apliquen análisis suavizados a sus algoritmos?

algorithms complexity-theory algorithm-analysis Gilles 'SO- deja de ser malvado'
fuente
11
¿Las personas aplican algún tipo de análisis de complejidad a sus algoritmos fuera de la academia?
Dave Clarke
2
Lo que dice @DaveClarke; tal vez debería pedir análisis rigurosos (o no triviales). Espero que muchos profesionales vean sus algoritmos, cuenten la profundidad de anidación del bucle y digan: "¡Esto es O(n3) !".
Raphael
3
Mientras buscaba cualquier uso de análisis suavizado que no fuera Simplex, encontré una lista comisariada por uno de los tipos que descubrió la técnica.
Raphael
1
@DaveClarke, ¿qué hay de las personas que trabajan en IBM, HP o NTT? ¿No deberían estar usando ese tipo de análisis?
Marcos Villagra
1
@DaveClarke que hago.
Kevin

Respuestas:

12

Podría estar equivocado, pero veo el análisis suavizado como una forma de explicar el comportamiento en la práctica de los algoritmos que tienen malas garantías teóricas (simplex, k-means, etc.). No estoy seguro de lo que significaría usar un análisis suavizado en la práctica, excepto para justificar el uso de una heurística particular con un mal desempeño en el peor de los casos ("Mi heurística tiene un comportamiento blah blah en el peor de los casos, pero un análisis suavizado indica que lo hará hacerlo bien en la práctica, etc. "

Suresh
fuente
2
El problema es que hasta ahora, los grandes éxitos para el análisis suavizado han sido explicar la práctica actual, por lo que los profesionales podrían simplemente reaccionar diciendo "bueno, eso es bueno, todo lo que he estado haciendo tiene sentido" :). No sé si alguien decidió usar una heurística hasta ahora menos conocida POR EL análisis suavizado.
Suresh
El análisis suavizado formal es muy difícil, no hay razón para que alguien que no sea en teoría deba practicarlo en exceso. Por otro lado, si lo considera como una heurística utilizada para analizar un algoritmo (es decir, la entrada es semi-aleatoria), entonces probablemente se use todo el tiempo.
Yuval Filmus
3

La forma en que las personas analizan los algoritmos en el mundo real es muy diferente de la academia. Mientras que en la academia el objetivo es encontrar un límite superior probablemente correcto en el tiempo de ejecución, en la vida real el objetivo es comprender cómo funciona el algoritmo y qué ajustes pueden mejorar el tiempo de ejecución. Hay dos métodos principales que están prohibidos en la academia pero que se usan en la práctica:

  • El método de aproximación. Aquí utiliza muchos supuestos simplificadores para tratar de pronosticar el tiempo de ejecución de un algoritmo. Similar a lo que solían hacer los físicos teóricos.
  • Experimentación. Usted ejecuta su algoritmo y mide varias estadísticas: cuánto tiempo pasó en cada parte, cuántas veces se llamó a cada función, con qué frecuencia se ejecutó cada rama, y ​​así sucesivamente. Esta información se puede utilizar para optimizar el algoritmo. La experimentación también se utiliza para averiguar si algunas aproximaciones realizadas al analizar el algoritmo funcionan en la práctica o no.

Dicho esto, no creo que sea muy común analizar un algoritmo en la práctica, aparte de agregar texto de relleno en una publicación académica relacionada. La atención se centra en la ingeniería de software o en la optimización de bajo nivel, según el tema.

Finalmente, el análisis suavizado es una heurística que se puede usar para explicar por qué los algoritmos funcionan mejor en la práctica de lo que sugeriría su peor caso, es decir, porque algunas de las entradas son "aleatorias" en algún sentido. Esta heurística se puede usar para aproximar el comportamiento del algoritmo si se usa el método de aproximación.

Yuval Filmus
fuente
"Mientras que en la academia el objetivo es encontrar un límite superior probadamente correcto en el tiempo de ejecución", ese es un objetivo, no el objetivo. También hay mucho trabajo en el análisis de casos promedio, a pesar de que el estudiante promedio de CS puede no ver mucho (porque es relativamente difícil). "Entender cómo funciona el algoritmo" es, posiblemente, la base de todos los algoritmos en la academia.
Raphael