SGCG

Volver arriba

Jugando con autómatas celulares (18)

2013-09-29

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. Hicimos algunas mejoras en un artículo anterior; hoy veremos algunas más. No conseguiremos algo tan rápido como un programa especializado y optimizado a mano en C, pero conseguiremos una ganancia importante con poco trabajo.

Acceso aleatorio a elementos de la lista de celdas en Scheme

La función matrix-ref de nuestra biblioteca sirve para acceder a elementos de la lista de celdas en posiciones aleatorias. Como esta lista es simplemente enlazada en la versión de la biblioteca hecha en Scheme, el acceso es lineal. Cualquier función que recorra todos los elementos de la lista de celdas mediante matrix-ref incurrirá en un coste no lineal, sino cuadrático. Esto puede ser algo lento, pero la solución es muy fácil: no tenemos más que hacer que matrix-ref funcione también con vectores y hacer la conversión necesaria mediante list->vector (cuyo coste es lineal con el tamaño de la lista de celdas) antes de empezar a trabajar con matrix-ref. La versión modificada de nuestra función es así:
(define (matrix-ref matrix sizes indices) (let ((ref (if (vector? matrix) vector-ref list-ref))) (ref matrix (multidimensional->flat sizes indices))))

La función translate-and-display-cartesian-2d que usamos para mostrar por pantalla las mallas cartesianas bidimensionales de autómatas como el del juego de la vida de Conway es una de las funciones ofensoras que hacen uso de matrix-ref, aunque no directamente, sino a través de una función auxiliar llamada cartesian-rows que extrae una lista de filas del retículo de celdas del autómata. Hacemos que la función funcione con vectores sin más que añadir una línea y modificar otra. El resultado es así:
(define (cartesian-rows cells sizes) (let ((rows (car sizes)) (columns (cadr sizes)) (matrix (list->vector cells))) (map (lambda (row) (map (lambda (column) (matrix-ref matrix sizes (list row column))) (range 0 columns 1))) (range 0 rows 1))))
La ganancia al actuar así es enorme.

Memoización de las funciones de aritmética de índices

Las funciones de aritmética de índices son muy generales y permiten trabajar con dimensiones arbitrariamente grandes gracias al uso generoso de map, fold y unfold con listas de dimensiones, pero a cambio son algo lentas, especialmente en Python (si usamos CPython, que es la implementación de referencia), ya que el intérprete es muy lento a la hora de hacer llamadas a funciones. Podemos hacer las cosas más rápidas si experimentamos con @memoise delante de las funciones flat_to_multidimensional, multidimensional_to_flat y cyclic_addition. Antes de rehacer cyclic_cartesian_neighbourhoods como en el anterior artículo de la serie, podríamos haber decorado las funciones problemáticas con @memoised para obtener mejoras de rendimiento un poquito menores, pero muy considerables.

Aceleración de la función de extracción de filas

La función de extracción de filas todavía puede correr un poquito más si usamos técnicas de memoización para construir los índices con una pequeña reescritura como la que aplicamos en cyclic-cartesian-neighbourhoods. La ganancia puede ser ya muy pequeña. Si asumimos que existe una función llamada cartesian-row-indices que acepta una lista sizes de tamaños y un número de fila row y devuelve una lista con los índices planos correspondientes a esa fila, la función cartesian-rows puede simplificarse un poquito:
(define (cartesian-rows cells sizes) (let ((rows (car sizes)) (columns (cadr sizes)) (matrix (list->vector cells))) (map (lambda (row) (map (lambda (index) (vector-ref matrix index)) (cartesian-row-indices sizes row))) (range 0 rows 1))))
Eso era Scheme. La versión de Python es así:
def cartesian_rows(cells, sizes): rows, columns = sizes return map(lambda row: map(lambda index: cells[index], cartesian_row_indices(sizes, row)), range(0, rows, 1))
Lo que hacemos es dejar de operar con matrix-ref y acceder a los elementos de la lista plana de celdas directamente. La función cartesian-row-indices con memoización necesaria es así en Scheme:
(define-memoised (cartesian-row-indices sizes row) (let ((columns (cadr sizes))) (map (lambda (column) (multidimensional->flat sizes (list row column))) (range 0 columns 1))))
Es así en Python:
@memoise def cartesian_row_indices(sizes, row): columns = sizes[1] indices = map(lambda column: multidimensional_to_flat(sizes, (row, column)), range(0, columns, 1)) return indices

Otros artículos de la serie

• Introducción.
• Pequeño autómata de demostración.
• Función para crear reglas deterministas.
• Funciones para sacar por pantalla las listas de celdas.
• Funciones auxiliares útiles.
• Más funciones auxiliares útiles.
• Funciones para trabajar con mallas cartesianas.
• Extracción de vecinos en mallas cartesianas cíclicas
• Funciones para crear autómatas unidimensionales elementales.
• Funciones para crear generaciones sucesivas de autómatas cómodamente.
• Prueba con varios autómatas elementales.
• Funciones para imprimir autómatas bidimensionales cartesianos.
• Juego de la vida de Conway.
• Funciones para trabajar con autómatas no deterministas.
• Autómata no determinista: modelo del incendio forestal.
• Autómatas de segundo orden.
• Mejora del rendimiento mediante memoización.
• Salida de imágenes.

Categorías: Informática

Artículos publicados el mismo mes

Permalink: http://sgcg.es/articulos/2013/09/29/jugando-con-automatas-celulares-18/

Volver arriba