Calcula la probabilidad de que un programa sea más rápido que otro

Question

Así que a menudo me encuentro con la situación de querer comparar el tiempo de ejecución de dos procesos informáticos. Incluso cuando se mide sólo el tiempo de usuario+sistema (a diferencia del tiempo del reloj de pared) hay un elemento aleatorio en el tiempo medido. Voy a suponer que esta aleatoriedad se distribuye de forma poisson (cambios de tareas e interrupciones de eventos aleatorios en el sistema informático).

Mi hipótesis es que un solo programa con una entrada idéntica se ejecutará en una cantidad de tiempo que se compone de una cantidad de tiempo constante para ejecutar las instrucciones y una cantidad de tiempo aleatoria generada por uno o más procesos de Poisson.

Así que simplifiquemos por el momento y supongamos que hay un proceso de Poisson y que cada vez que ocurre representa la misma cantidad de tiempo. No conocemos lambda, ni t(lambda), el tiempo asociado a ella. Sin embargo, puedo ejecutar el mismo programa con la misma entrada muchas veces.

¿Cómo puedo estimar cuál es la parte constante del tiempo de ejecución? ¿Cómo puedo estimar lambda y t(lambda)?

La cuestión más profunda es...

Si tengo dos programas que hacen lo mismo y quiero estimar la probabilidad de que uno se ejecute más rápido que el otro ¿cómo lo haría? Parece que aplicar a ciegas la distribución normal podría ser problemático. La parte aleatoria es (creo) poisson; pero antes de aplicar la distribución poisson tendría que factorizar la parte constante.

Answer 1

Puede modelar los tiempos de funcionamiento $X_1,\dots,X_n$ del programa como condicionalmente independiente e idénticamente distribuido, dado $M=\mu$ y $\Lambda=\lambda$ con densidad $$ f_{X_1\mid M,\Lambda}(x_1\mid \mu,\lambda) = \lambda\,e^{-\lambda(x_1-\mu)} I_{(\mu,\infty)}(x_1) \, . $$ La probabilidad de este modelo exponencial traducido es $$ L_x(\mu,\lambda)=\lambda^n \, e^{-\lambda\left(\left(\sum_{i=1}^n x_i\right) - n\mu\right)} I_{(0,x_{(1)})}(\mu) \, . $$ Como primer intento, intentaría un análisis bayesiano con una prioridad tipo Jeffreys $f_{M,\Lambda}(\mu,\lambda)\propto 1/\lambda$ . Uno de los objetivos es estimar $M$ por $\mathbb{E}[M\mid X=x]$ . Para muestrear a partir de la posterioridad, intentaría un algoritmo Metropolis-Hastings proponiendo el siguiente $M$ como $\mathrm{U}[0,x_{(1)}]$ y el siguiente $\Lambda$ de una distribución gamma con una expectativa igual al valor anterior y una varianza ínfima. Con un muestreador de trabajo, es fácil calcular la estimación y un intervalo creíble posterior para $M$ . No es difícil extender este análisis a un segundo programa; con las adiciones necesarias a la notación, la forma natural de comparar ambos programas es calcular $P(M<M'\mid X=x,X'=x')$ . Si esta probabilidad es cercana a cero o a uno, se puede afirmar que uno de los programas es más rápido.