Especialización en algoritmos en tiempo de ejecución
En informática , la especialización de algoritmos en tiempo de ejecución es una metodología para crear algoritmos eficientes para costosas tareas de cálculo de ciertos tipos. La metodología se origina en el campo de la demostración automatizada de teoremas y, más específicamente, en el proyecto de demostración del teorema del vampiro .
La idea se inspira en el uso de la evaluación parcial para optimizar la traducción de programas. Muchas operaciones centrales en los probadores de teoremas exhiben el siguiente patrón. Suponga que necesitamos ejecutar algún algoritmo en una situación en la que un valor de es fijo para potencialmente muchos valores diferentes de . Para hacer esto de manera eficiente, podemos intentar encontrar una especialización de para cada fijo , es decir, un algoritmo de este tipo , que ejecutar es equivalente a ejecutar .
El algoritmo especializado puede ser más eficiente que el genérico, ya que puede explotar algunas propiedades particulares del valor fijo . Por lo general, se pueden evitar algunas operaciones que tendrían que realizar, si se sabe que son redundantes para este parámetro en particular . En particular, a menudo podemos identificar algunas pruebas que son verdaderas o falsas para , desenrollar bucles y recursividad, etc.
La diferencia clave entre la especialización en tiempo de ejecución y la evaluación parcial es que los valores de en el que está especializado no se conocen estáticamente, por lo que la especialización tiene lugar en el tiempo de ejecución .