Especialización en algoritmos de 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 tareas de computación costosas de ciertos tipos. La metodología tiene su origen en el campo de la demostración automatizada de teoremas y, más concretamente, en el proyecto de demostración de teoremas Vampiro .
La idea está inspirada en el uso de la evaluación parcial para optimizar la traducción del programa. Muchas operaciones centrales en los probadores de teoremas exhiben el siguiente patrón. Supongamos que necesitamos ejecutar algún algoritmo en una situación en la que se fija un valor de para potencialmente muchos valores diferentes de . Para hacer esto eficientemente, podemos tratar de encontrar una especialización de para cada fijo , es decir, tal algoritmo , 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, puede evitar algunas operaciones que tendría 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 bucles desenrollados y recursión, etc.
La diferencia clave entre la especialización en tiempo de ejecución y la evaluación parcial es que los valores de en los que se especializa no se conocen estáticamente, por lo que la especialización tiene lugar en tiempo de ejecución .