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

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?

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.

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 .

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 )