Volver arriba
2013-09-25
Hace
varios artículos, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Dicho lo anterior, nuestra biblioteca está bien para explorar, pero
estaría mejor si pudiéramos hacer que fuera un poquito más deprisa.
Podemos lograr mejoras significativas sin necesidad de realizar
cambios profundos en el código, sin necesidad de hacerlo largo y
prolijo. No conseguiremos algo tan rápido como un programa
especializado y optimizado a mano en C, pero conseguiremos una
ganancia importante con poco trabajo.
Memoización
Nuestro código tiene muchos cálculos que son redundantes.
Afortunadamente, casi todo el código que hemos desarrollado es
referencialmente transparente, así que es perfectamente lícito
almacenar en memoria los resultados de los cálculos pesados que
utilizamos más de una vez. Esta táctica es conocida como
«memoización» y es muy útil cuando nuestro programa tiene problemas de
rendimiento, pero hay memoria de sobra. Podemos modificar nuestras
funciones para hacer esto explícitamente, pero es preferible evitar
tal cosa. En vez de eso, lo que vamos a hacer es extender de alguna
manera nuestro lenguaje para poder aplicar la técnica de memoización a
las funciones de nuestra elección. Esto es muy fácil en Scheme porque
las funciones son objetos de primera clase y tenemos a nuestra
disposición un sistema de macros con el que empujar los límites del
lenguaje. En Python, las funciones son casi tan versátiles como en
Scheme y, aunque no hay un sistema de macros, hay unos dispositivos
conocidos como «decoradores» que se adaptan al uso que queremos dar.
Empezamos con Scheme. En primer lugar, vamos a crear una función
con la que crear versiones con memoización de otras funciones. Las
versiones memoizadas tienen una memoria asociativa que relaciona
argumentos de llamadas antiguas con sus resultados, de manera que no
hace falta repetir los cálculos cuando vuelven a darse los argumentos
antiguos, sino que es suficiente devolver el resultado almacenado.
Usamos una lista asociativa como memoria; cada celda en esta memoria
es un par cuyo primer elemento (el car) es el conjunto de
argumentos que sirve como clave y cuyo segundo elemento
(el cdr) es el valor devuelto por la función. Vamos
añadiendo elementos al principio de la memoria
mediante cons y modificamos destructivamente la memoria
mediante set!. Una primera versión sería así:
(define (memoise function)
(let ((cache '()))
(lambda arguments
(let ((cached-arguments-and-results (assoc arguments cache)))
(if cached-arguments-and-results
(cdr cached-arguments-and-results)
(let ((results (apply function arguments)))
(set! cache (cons (cons arguments results)
cache))
results))))))
Esta versión no funciona con funciones que devuelven múltiples
valores. En Python, trabajar con funciones que devuelven múltiples
valores es relativamente sencillo porque lo que se hace en realidad es
devolver una tupla y hacer el equivalente
al destructuring-bind de Common Lisp para recibir los
valores devueltos en múltiples variables. En Scheme R5RS, en cambio,
podemos devolver múltiples valores de verdad, pero su manejo se
complica porque hay que usar continuaciones. Capturamos los múltiples
valores devueltos mediante una función variádica que acepta todos
estos valores y los mete en una lista; después, almacenamos esta lista
de valores en la celda correspondiente de la memoria; finalmente,
aplicamos la función values sobre la lista de valores para
poder hacer una devolución de valores múltiples propia. La solución
sería así:
(define (memoise function)
(let ((cache '()))
(lambda arguments
(let ((cached-arguments-and-results (assoc arguments cache)))
(if cached-arguments-and-results
(apply values (cdr cached-arguments-and-results))
(call-with-values
(lambda () (apply function arguments))
(lambda results
(set! cache (cons (cons arguments results)
cache))
(apply values results))))))))
Una vez tenemos la función, podemos probarla. Podemos computar la
secuencia de Fibonacci, por ejemplo:
(define (fibonacci n)
(if (< n 2)
1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
Esta función hace los cálculos de una forma muy ineficiente, ya
que repite los mismos cálculos una y otra vez. Podemos pisarla tras
su definición con una versión con memoización:
(define fibonacci (memoise fibonacci))
La nueva función es muchísimo más rápida. A cambio, por supuesto,
consume memoria. Siempre podríamos inventar una versión
de memoise con un mecanismo para purgar valores memorizados
antiguos para acotar el consumo de memoria.
Usar la función memoise directamente puede ser una cosa
algo incómoda. Sería conveniente poder definir funciones con
memoización de un solo paso y sin esfuerzo adicional sobre una
definición de función convencional. Da la casualidad de que podemos
extender el lenguaje mediante macros, así que estamos de enhorabuena.
Lo único que tenemos que hacer es capturar definiciones de funciones
normales y corrientes. La solución es así de facilita:
(define-syntax define-memoised
(syntax-rules ()
((_ (name . arguments) body ...)
(define name
(memoise (lambda arguments
body ...))))))
De esta manera, podemos definir la función que calcula el elemento
enésimo de la sucesión de Fibonacci como si fuera una función normal:
(define-memoised (fibonacci n)
(if (< n 2)
1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
Es así de fácil.
Ahora vamos con Python.
def memoise(function):
cache = {}
def memoised_function(*arguments):
if arguments in cache:
return cache[arguments]
else:
results = function(*arguments)
cache[arguments] = results
return results
return memoised_function
La versión de Python es más corta que la de Scheme. Como los
valores múltiples van en forma de tupla normal y corriente (de manera
que en realidad nunca devolvemos valores múltiples, sino un único
objeto que es una tupla), no hace falta hacer cosas especiales para
manejarlos.
Python no tiene macros, pero podemos hacer algo casi tan compacto
como usar define-memoised gracias a los decoradores.
El ejemplo de la sucesión de Fibonacci se traduce a Python así:
@memoise
def fibonacci(n):
if n < 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
El decorador tiene un efecto similar al que logramos mediante
macros en Scheme.
Aceleración de cyclic-cartesian-neighbourhoods
La función cyclic-cartesian-neighbourhoods hace muchas
operaciones pesadas que podemos ahorrar si disponemos de memoria
suficiente. Esta función hace muchas conversiones entre índices
planos e índices multidimensionales. Algunas implementaciones de
Scheme nos dan resultados significativamente más rápidos si aplicamos
memoización, mientras que la diferencia no es apreciable en otras.
Necesitaríamos hacer una pequeña reescritura, no obstante:
(define (cyclic-cartesian-neighbourhoods cells sizes offsets)
(let ((matrix (list->vector cells)))
(map (lambda (indices)
(map (lambda (index)
(vector-ref matrix index))
indices))
(cyclic-cartesian-neighbourhood-indices sizes offsets))))
Esta función tiene la misma interfaz que la original, pero
internamente es diferente. En primer lugar, realiza el acceso
aleatorio a las celdas mediante un vector y no una lista para así
beneficiarse de un tiempo de acceso constante; en segundo lugar, asume
que disponemos de una función
llamada cyclic-cartesian-neighbourhood-indices que acepta
una lista de dimensiones sizes y una lista de
distancias offsets, y devuelve una lista cuyos elementos
son a su vez listas con los índices planos
que cyclic-cartesian-neighbourhoods utilizaría para extraer
los vecinos de cada celda. La función es sin duda algo complicada:
(define-memoised (cyclic-cartesian-neighbourhood-indices sizes offsets)
(define (apply-one-offset index offset)
(multidimensional->flat sizes
(cyclic-addition sizes index offset)))
(define (apply-offsets index)
(map (lambda (offset) (apply-one-offset index offset))
offsets))
(let* ((total-size (fold * 1 sizes))
(flat-indices (range 0 total-size 1))
(multidimensional-indices (map (lambda (flat-index)
(flat->multidimensional sizes
flat-index))
flat-indices)))
(map apply-offsets multidimensional-indices)))
Hacemos memoización como optimización. Los cálculos son lo
bastante largos y pesados como para que la técnica sea beneficiosa.
Podemos hacer algo similar en Python. La
función cyclic_cartesian_neighbourhoods queda reescrita
así:
def cyclic_cartesian_neighbourhoods(cells, sizes, offsets):
return map(lambda indices:
tuple(map(lambda index:
cells[index],
indices)),
cyclic_cartesian_neighbourhood_indices(sizes, offsets))
Necesitamos crear la
función cyclic_cartesian_neighbourhood_indices:
@memoise
def cyclic_cartesian_neighbourhood_indices(sizes, offsets):
def apply_one_offset(index, offset):
return multidimensional_to_flat(sizes,
cyclic_addition(sizes, index, offset))
def apply_offsets(index):
return tuple(map(lambda offset: apply_one_offset(index, offset),
offsets))
total_size = fold(lambda a, b: a * b, 1, sizes)
flat_indices = range(0, total_size, 1)
multidimensional_indices = map(lambda flat_index:
flat_to_multidimensional(sizes,
flat_index),
flat_indices)
return tuple(map(apply_offsets, multidimensional_indices))
Con esto, la ganancia en rapidez se nota mucho cuando el tablero
es grande.
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
https://sgcg.es/articulos/2013/09/25/jugando-con-automatas-celulares-17/
Volver arriba
