algorithm - Optimizando el ''Juego de la vida'' de Conway
performance language-agnostic (10)
Como se menciona en el Libro negro de Arbash, una de las formas más simples y sencillas de obtener una gran aceleración es mantener una lista de cambios.
En lugar de iterar por toda la cuadrícula de la celda cada vez, guarde una copia de todas las celdas que cambie.
Esto reducirá el trabajo que tienes que hacer en cada iteración.
Para experimentar, (hace mucho tiempo) implementé el Juego de la vida de Conway (¡y estoy al tanto de esta pregunta relacionada!).
Mi implementación funcionó manteniendo 2 matrices de booleanos, que representan el ''último estado'' y el ''estado que se está actualizando'' (las 2 matrices se intercambian en cada iteración). Si bien esto es bastante rápido, a menudo me he preguntado sobre cómo optimizar esto.
Una idea, por ejemplo, sería precomputar en la iteración N las zonas que podrían modificarse en la iteración (N + 1) (de modo que si una celda no pertenece a dicha zona, ni siquiera se considerará para su modificación en iteración (N + 1)). Soy consciente de que esto es muy vago, y nunca me tomé el tiempo para entrar en detalles ...
¿Tiene alguna idea (o experiencia) de cómo hacer para optimizar las iteraciones de Game of Life?
Dos ideas:
(1) Muchas configuraciones son en su mayoría espacio vacío. Mantenga una lista enlazada (no necesariamente en orden, eso tomaría más tiempo) de las celdas activas, y durante una actualización, solo actualice alrededor de las celdas activas (esto es similar a su sugerencia vaga, OysterD :)
(2) Mantenga una matriz extra que almacene el n. ° de celdas vivas en cada fila de 3 posiciones (izquierda-centro-derecha). Ahora cuando calcule el nuevo valor muerto / vivo de una celda, solo necesita 4 operaciones de lectura (filas superior e inferior y las posiciones del centro) y 4 operaciones de escritura (actualice los 3 valores de resumen de la fila afectada, y los muertos / valor en vivo de la nueva celda). Esta es una ligera mejora de 8 lecturas y 1 escritura, suponiendo que las escrituras no son más lentas que las lecturas. Supongo que puede ser más inteligente con esas configuraciones y llegar a una mejora aún mejor en esta línea.
Es un autómata bidimensional, por lo que probablemente pueda buscar técnicas de optimización. Su idea parece ser la de comprimir la cantidad de celdas que necesita verificar en cada paso. Ya que solo necesita verificar las celdas que están ocupadas o adyacentes a una celda ocupada, quizás podría mantener un buffer de todas esas celdas, actualizándolas en cada paso mientras procesa cada celda.
Si su campo está inicialmente vacío, esto será mucho más rápido. Probablemente pueda encontrar algún punto de equilibrio en el que mantener el buffer sea más costoso que procesar todas las celdas.
Hay algunas implementaciones súper rápidas que (desde la memoria) representan celdas de 8 o más cuadrados adyacentes como patrones de bits y usan eso como un índice en una gran matriz de valores precalculados para determinar en una sola instrucción de máquina si una celda está activa o muerta .
Mira aquí:
http://dotat.at/prog/life/life.html
También XLife:
Hay soluciones basadas en tablas para esto que resuelven múltiples celdas en cada búsqueda de tabla. Una consulta de google debería darle algunos ejemplos.
No sé exactamente cómo se puede hacer esto, pero recuerdo que algunos de mis amigos tuvieron que representar la cuadrícula de este juego con un Quadtree para una tarea. Supongo que es muy bueno para optimizar el espacio de la grilla, ya que básicamente solo representas las celdas ocupadas. No obstante, no sé acerca de la velocidad de ejecución.
El algoritmo en sí es intrínsecamente paralelizable. Usando el mismo método de doble búfer en un kernel CUDA no optimizado, estoy obteniendo alrededor de 25 ms por generación en un mundo envuelto de 4096x4096.
cuál es el algo más eficiente depende principalmente del estado inicial.
si la mayoría de las celdas están muertas, puede ahorrar mucho tiempo de CPU omitiendo las partes vacías y sin calcular las cosas celda por celda.
En mi opinión, puede tener sentido verificar primero si hay espacios completamente muertos, cuando su estado inicial es algo así como "al azar, pero con una probabilidad de vida inferior al 5%".
simplemente dividiría la matriz en mitades y comenzaría a verificar primero las más grandes.
entonces si tiene un campo de 10,000 * 10,000, primero debe acumular los estados del cuarto superior izquierdo de 5,000 * 5,000.
y si la suma de estados es cero en el primer trimestre, puede ignorar este primer trimestre completamente ahora y verificar la derecha superior 5,000 * 5,000 para vida siguiente.
si su suma de estados es> 0, ahora dividirá el segundo trimestre en 4 piezas nuevamente y repetirá este control de por vida para cada uno de estos subespacios.
podría bajar a las subtramas de 8 * 8 o 10 * 10 (no estoy seguro de qué tiene más sentido aquí) ahora.
cada vez que encuentre vida, marque estos subespacios como "tiene vida".
solo los espacios que "tienen vida" deben dividirse en subespacios más pequeños; los vacíos se pueden omitir.
Cuando termina de asignar el atributo "tiene vida" a todos los subespacios posibles, termina con una lista de subespacios que ahora simplemente extiende en +1 a cada dirección (con celdas vacías) y realiza el juego regular (o modificado) de la vida gobierna para ellos.
podría pensar que dividir un spa de 10.000 * 10.000 en subespacios de 8 * 8 es una gran cantidad de tareas, pero acumular sus valores de estado es, de hecho, mucho menos trabajo de computación que realizar el algoritmo GoL para cada celda más sus 8 vecinos más comparando el número y almacenando el nuevo estado para la iteración neta en alguna parte ...
pero como dije antes, para un estado de inicio aleatorio con un 30% de población esto no tendrá mucho sentido, ya que no habrá muchos subespacios 8 * 8 completamente muertos para encontrar (deje solo muertos, 256 * 256 subpacios)
y, por supuesto, la forma de optimización perfecta dependerá en última instancia de su idioma.
-110
Voy a citar mi respuesta de la otra pregunta, porque los capítulos que menciono tienen algunas soluciones muy interesantes y afinadas. Algunos de los detalles de implementación están en C y / o ensamblados, sí, pero en su mayor parte los algoritmos pueden funcionar en cualquier idioma:
Los capítulos 17 y 18 del libro negro del programador de gráficos de Michael Abrash son una de las lecturas más interesantes que he tenido. Es una lección de pensamiento fuera de la caja. Todo el libro es realmente genial, pero las soluciones finales optimizadas para el Juego de la vida son increíbles trozos de programación.