¿Por qué usar comparaciones en lugar de tiempo de ejecución para comparar dos algoritmos?

19

Noté que en algunos trabajos de investigación de CS, para comparar la eficiencia de dos algoritmos, se usa el número total de comparación clave en los algoritmos en lugar de los tiempos reales de computación. ¿Por qué no podemos comparar cuál es mejor ejecutando ambos programas y contando el tiempo total necesario para ejecutar los algoritmos?

tiene
fuente
¡Bienvenido! Espero que la mayoría de esos documentos no utilicen tiempos de ejecución. Sin embargo, sé que algunos lo hacen, especialmente en las comunidades más aplicadas y cuando los sistemas considerados son muy complejos.
Raphael

Respuestas:

14

Este es realmente un problema profundo que tiene algunas respuestas metódicas y algunas pragmáticas. Supongo que quiere saber algo sobre los algoritmos disponibles. Si desea saber qué algoritmo funciona mejor en una máquina dada en entradas dadas, continúe y mida los tiempos de ejecución. Si desea comparar la calidad de un compilador para un algoritmo dado, continúe y mida los tiempos de ejecución. Para aprender algo sobre el algoritmo, no lo hagas.

Permítanme primero dar algunas razones por las cuales el uso de tiempos de ejecución no es una buena idea.

  1. Los
    tiempos de ejecución de generalidad medidos usando un idioma y un compilador en una máquina tienen poco significado si cambia algún componente. Incluso las implementaciones ligeramente diferentes del mismo algoritmo pueden funcionar de manera diferente porque se activa una optimización del compilador en el caso, pero no en el otro.
  2. Predicción
    Entonces tiene un par de tiempos de ejecución para algunas entradas. ¿Qué dice eso sobre el tiempo de ejecución de alguna otra entrada? En general, nada.
  3. Importancia
    Por lo general, no comparará todas las entradas (de algún tamaño), de modo que eso restringe inmediatamente su capacidad de comparar algoritmos: ¿tal vez su conjunto de prueba desencadenó el peor caso en uno y el mejor en el otro algoritmo? O tal vez sus entradas fueron demasiado pequeñas para exhibir el comportamiento en tiempo de ejecución .
  4. Medición
    Medición de tiempos de ejecución bien no es trivial. ¿Hay un JIT? ¿Ha habido contención, es decir, estás contando el tiempo que el algoritmo ni siquiera se ejecutó? ¿Puede reproducir exactamente el mismo estado de máquina para otra ejecución (del otro algoritmo), en particular procesos concurrentes y cachés? ¿Cómo se trata la latencia de memoria?

Espero que esto te haya convencido de que los tiempos de ejecución son una medida horrible para comparar algoritmos, y que se necesita algún método general y abstracto para investigar el tiempo de ejecución de algoritmos.

En la segunda parte de la pregunta. ¿Por qué utilizamos comparaciones u operaciones elementales similares?

  1. Tratabilidad analítica
    Suponiendo que desee hacer un análisis formal, debe poder hacerlo. Contar declaraciones individuales es muy técnico, a veces incluso difícil; Sin embargo, algunas personas lo hacen (por ejemplo, Knuth). Contar solo algunas declaraciones, aquellas que dominan el tiempo de ejecución, es más fácil. Por la misma razón, a menudo "solo" investigamos (límites superiores en) el peor tiempo de ejecución.

  2. Dominio
    La operación seleccionada domina el tiempo de ejecución. Eso no significa que contribuya con la mayor cantidad de tiempo de ejecución; las comparaciones claramente no lo hacen, por ejemplo, en Quicksort al ordenar enteros del tamaño de una palabra. Pero se ejecutan con mayor frecuencia , por lo que al contarlos se cuenta con qué frecuencia se ejecutan las partes más ejecutadas del algoritmo. En consecuencia, su tiempo de ejecución asintótico es proporcional al número de operaciones elementales dominantes. Es por eso que nos sentimos cómodos usando la notación de Landau y la palabra "tiempo de ejecución" aunque solo contamos las comparaciones.

Tenga en cuenta que puede ser útil contar más de una operación. Por ejemplo, algunas variantes de Quicksort toman más comparaciones pero menos intercambios que otras (en promedio).

Para lo que vale, después de haber hecho toda la teoría, es posible que desee volver a visitar los tiempos de ejecución para verificar que las predicciones que hace su teoría sean sólidas. Si no lo son, su teoría no es útil (en la práctica) y debe ampliarse. La jerarquía de memoria es una de las primeras cosas que te das cuenta de que es importante pero que falta en los análisis básicos.

Rafael
fuente
1
Tenga en cuenta que el análisis formal también tiene sus límites. Por ejemplo, el caso promedio para distribuciones de entrada no uniformes es a menudo intratable.
Raphael
10

Esto se debe a que el tiempo total para ejecutar los algoritmos depende del hardware en el que se ejecuta junto con otros factores. No es confiable comparar dos algoritmos si uno se ejecuta en un Pentium 4 y el otro en, por ejemplo, un Core i7. No solo esto, sino que digamos que ejecutó ambos en la misma computadora. ¿Qué decir que ambos tienen la misma cantidad de tiempo de procesador? ¿Qué sucede si algún otro proceso tiene una prioridad más alta que el proceso de uno de los algoritmos?

Para superar esto, nos desconectamos de este tiempo general para completar, y en su lugar comparamos en función de qué tan bien se escala el algoritmo. Es posible que haya notado notación como O (1) u O (n ^ 2) en los trabajos de investigación. Esto puede requerir un poco más de lectura, si usted está interesado ver la notación O grande .

Chris Howell
fuente
1
¡Además, el tiempo real de ejecución depende del tamaño y el contenido de la entrada real utilizada para ejecutar los algoritmos!
Tsuyoshi Ito
7

Dado que las otras respuestas explican por qué analizamos el tiempo de ejecución en términos de número de operaciones elementales, permítanme ofrecer un par de razones por las cuales las comparaciones son la métrica correcta de muchos (no todos) algoritmos de clasificación:

  • Para muchos algoritmos de clasificación, el número de comparaciones domina el tiempo de ejecución, es decir, se realizan al menos tantas comparaciones como cualquier otra operación elemental.
  • las comparaciones son la operación costosa ; piense en cómo se implementa una rutina de clasificación en la biblioteca: la función de clasificación pasa una matriz de elementos y un puntero a una función que compara dos elementos; en general, llamar y esperar a que se ejecute la función de comparación es más costoso que las operaciones "internas"; Como esta función la proporciona el usuario, es más difícil optimizarla
  • (esto puede o no ser una buena razón para algunos) podemos decir algo interesante sobre la cantidad de comparaciones que son suficientes y necesarias para ordenar una secuencia; sabemos cómo hacer esto en el peor de los casos y, en promedio, para varias distribuciones, incluso cómo diseñar un algoritmo que converja en óptimo a medida que se ejecuta en elementos muestreados en una distribución desconocida ( Algoritmos de mejora automática ); sabemos cómo hacer esto cuando algunas comparaciones se dan de forma gratuita ( Ordenando con información parcial )
Sasho Nikolov
fuente
1) "se realizan al menos tantas comparaciones como cualquier otra operación elemental", solo hasta un factor constante. 2) "las comparaciones son la operación costosa", que supone una configuración genérica. Para la clasificación de enteros (que generalmente se analiza), los intercambios suelen ser más caros.
Raphael
seguro. op parecía estar confundido sobre el análisis de algoritmos en general, no quería aportar factores constantes. Espero que el hecho de que estoy hablando de una configuración genérica esté claro en la descripción: la rutina de clasificación en una biblioteca estándar no es la clasificación de enteros
Sasho Nikolov
Además de los documentos que op vio definitivamente no se trata de algoritmos especializados de clasificación de enteros, nadie cuenta el número de comparaciones
Sasho Nikolov
@Raphael Ordenar números enteros pequeños no es un problema común en la práctica. Apuesto a que la mayoría de las clasificaciones que se realizan en el mundo son cadenas (de una longitud u otra ). Incluso para la clasificación de enteros, no estoy seguro de si es preciso que los intercambios sean más caros: la ramificación es una operación relativamente costosa en un procesador moderno de alta gama, ya que la predicción de ramificaciones sería inútil en la mayoría de los casos.
Gilles 'SO- deja de ser malvado'
@Gilles En sí mismo, los swaps son más caros que las comparaciones de enteros que cualquier plataforma que conozco. Los costos "secundarios" como, por ejemplo, las predicciones erróneas de las ramas son definitivamente un factor, cuyo impacto es objeto de una investigación en curso. (Con respecto al uso en la práctica, no puedo hacer una declaración calificada. Sin embargo, observo que los mantenedores de bibliotecas estándar siguen mejorando los algoritmos de clasificación que usan para los tipos de datos primitivos, así que supongo que ven mucho uso (ab).)
Raphael