El análisis asintótico responde cómo escala el programa cuando crecen la entrada o los recursos, y su respuesta sale del algoritmo: es la misma en cualquier máquina. La evaluación comparativa responde qué tiempo concreto toma el programa en esta máquina, con esta JVM y con esta entrada, y su respuesta cambia con la plataforma. Las dos hacen falta: el análisis predice qué pasa al doblar el problema o el hardware, y la medición confirma o desmiente que la implementación cumpla esa predicción.
Sumar un arreglo en árbol es sumar las parejas de cada nivel y repetir con lo que queda. La tabla recorre esos niveles para el tamaño escogido: cuántos valores entran, cuántas sumas ocurren en ese nivel, todas al mismo tiempo, y cuántos valores pasan al siguiente. El trabajo W es el total de la columna del medio y la profundidad D es el número de niveles.
Nada de esto se ejecutó. Al cambiar el tamaño, el análisis vuelve a responder con dos números, y lo hace también para una entrada que la máquina no alcanzaría a correr.
Seis preguntas sobre el mismo programa. Para cada una, la herramienta que la responde.
El ciclo de cola y la suma en árbol hacen las mismas W sumas, así que el conteo de operaciones totales las deja en el mismo orden de crecimiento. La diferencia está en el otro número: el ciclo necesita el acumulador de la suma anterior para hacer la siguiente, de modo que su profundidad es su trabajo entero, mientras el árbol termina en D niveles.
La última columna es el paralelismo disponible, lo que el análisis secuencial no ve. Cambie de tamaño y compare las filas: el trabajo se multiplica y la profundidad apenas crece.
Una prueba tiene salida binaria:
reverse(List(1,2,3)) == List(3,2,1) cumple o no cumple. Una
medición tiene salida continua y aleatoria: cada ejecución da un valor
distinto. Estos son diez tiempos del mismo programa en la misma máquina,
sin nadie más usándola.
Un equipo del curso llega con dos versiones de la suma del arreglo y una medición de cada una.
Dos implementaciones de la misma función tienen el
mismo trabajo y la misma profundidad: una usa List y la otra
Array. Diseñe la medición que decidiría entre las dos. Escriba
cuántas repeticiones hace, qué valor reporta de ellas, qué registra de la
máquina y de la JVM para que otra persona pueda repetir el experimento, y
qué resultado lo haría cambiar de implementación.