Coneladas juego de vida usando un conjunto desordenado de coordenadas -- ++ campo con game-of-life campo con set camp codereview Relacionados El problema

Conways Game of Life using unordered set of coordinates


3
vote

problema

Español

Anteriormente, había estado usando una matriz de BOOL (Dead / Live) para representar celdas. Miré en el código de revisión para ver cómo otras personas han implementado el juego de la vida de Conway . Alguien en los comentarios de un post sugirió usar un conjunto desordenado para almacenar solo celdas en vivo. Esto suena como si fuera más eficiente, porque solo almacenar células vivas significa que el programa solo tiene que revisar las células vivas y sus vecinos. Lo intenté, pero no estoy seguro de si el programa es más eficiente como lo he implementado. Se aprecian cualquier sugerencia.

clase de cuadrícula

  #ifndef UTILITIES_H_INCLUDED #define UTILITIES_H_INCLUDED  #include<iostream> #include<unordered_set>  #define dead cells_at_t.end()  namespace ConwaysGameOfLife {     struct Grid     {         private:             std::size_t cols{25};             std::size_t rows{25};              int top{-cols};             int bottom{cols};             const int left{-1};             const int right{1};             const int middle{0};              using set_of = std::unordered_set<std::size_t>;              set_of cells_at_t{55+76,81+76,104+76,105+76,106+76,205+76,206+76,230+76,231+76};             set_of cells_at_t_minus_one;              std::unordered_set<int> neighbors             {                 top+left,                 top,                 top+right,                 left,                 right,                 bottom+left,                 bottom,                 bottom+right             };             void rule(const std::size_t& position)             {                 std::size_t live_neighbors{0};                  for(const auto& neighbor : neighbors)                     //Total Neighbors                 {                     if(cells_at_t.find(position + neighbor) != dead)                     {                         live_neighbors++;                     }                 }                 if(cells_at_t.find(position) != dead && live_neighbors < 2)                     //Underpopulation                 {                     cells_at_t_minus_one.erase(position);                 }                 else if(cells_at_t.find(position) != dead && (live_neighbors == 2 || live_neighbors == 3))                     //Aging of a Cell                 {                     cells_at_t_minus_one.insert(position);                 }                 else if(cells_at_t.find(position) == dead && live_neighbors == 3)                     //Birth of a Cell                 {                     cells_at_t_minus_one.insert(position);                 }                 else if(cells_at_t.find(position) != dead && live_neighbors > 3)                     //Overpopulation                 {                     cells_at_t_minus_one.erase(position);                 }             }         public:             void apply()             {                 set_of cells;                 for(const auto& position : cells_at_t)                 {                     if(cells.insert(position).second);                     {                         rule(position);                     }                     for(const auto& neighbor : neighbors)                     {                         if(cells.insert(position + neighbor).second);                         {                             rule(position + neighbor);                         }                     }                 }                 cells_at_t = cells_at_t_minus_one;             }             void display()             {                 for(int r{0}; r < rows; ++r)                 {                     for(int c{0}; c < cols; ++c)                     {                         if(cells_at_t.find(r * cols + c) != dead)                             std::cout << '0';                         else                             std::cout << ' ';                     }                     std::cout << std::endl;                 }                 std::cout << std::endl;             }             Grid() {}             ~Grid() {}     }; }  #endif // UTILITIES_H_INCLUDED   
Original en ingles

Previously I had been using an array of bool(dead/live) to represent cells. I looked on code review to see how other people have implemented Conway's Game of Life. Someone in the comments of a post suggested using an unordered set to only store live cells. This sounds like it would be more efficient, because only storing live cells means that the program only has to check live cells and their neighbours. I tried it, but I am not sure if the program is more efficient the way I have implemented it. Any suggestions are appreciated.

Grid Class

#ifndef UTILITIES_H_INCLUDED #define UTILITIES_H_INCLUDED  #include<iostream> #include<unordered_set>  #define dead cells_at_t.end()  namespace ConwaysGameOfLife {     struct Grid     {         private:             std::size_t cols{25};             std::size_t rows{25};              int top{-cols};             int bottom{cols};             const int left{-1};             const int right{1};             const int middle{0};              using set_of = std::unordered_set<std::size_t>;              set_of cells_at_t{55+76,81+76,104+76,105+76,106+76,205+76,206+76,230+76,231+76};             set_of cells_at_t_minus_one;              std::unordered_set<int> neighbors             {                 top+left,                 top,                 top+right,                 left,                 right,                 bottom+left,                 bottom,                 bottom+right             };             void rule(const std::size_t& position)             {                 std::size_t live_neighbors{0};                  for(const auto& neighbor : neighbors)                     //Total Neighbors                 {                     if(cells_at_t.find(position + neighbor) != dead)                     {                         live_neighbors++;                     }                 }                 if(cells_at_t.find(position) != dead && live_neighbors < 2)                     //Underpopulation                 {                     cells_at_t_minus_one.erase(position);                 }                 else if(cells_at_t.find(position) != dead && (live_neighbors == 2 || live_neighbors == 3))                     //Aging of a Cell                 {                     cells_at_t_minus_one.insert(position);                 }                 else if(cells_at_t.find(position) == dead && live_neighbors == 3)                     //Birth of a Cell                 {                     cells_at_t_minus_one.insert(position);                 }                 else if(cells_at_t.find(position) != dead && live_neighbors > 3)                     //Overpopulation                 {                     cells_at_t_minus_one.erase(position);                 }             }         public:             void apply()             {                 set_of cells;                 for(const auto& position : cells_at_t)                 {                     if(cells.insert(position).second);                     {                         rule(position);                     }                     for(const auto& neighbor : neighbors)                     {                         if(cells.insert(position + neighbor).second);                         {                             rule(position + neighbor);                         }                     }                 }                 cells_at_t = cells_at_t_minus_one;             }             void display()             {                 for(int r{0}; r < rows; ++r)                 {                     for(int c{0}; c < cols; ++c)                     {                         if(cells_at_t.find(r * cols + c) != dead)                             std::cout << '0';                         else                             std::cout << ' ';                     }                     std::cout << std::endl;                 }                 std::cout << std::endl;             }             Grid() {}             ~Grid() {}     }; }  #endif // UTILITIES_H_INCLUDED 
        
 
 

Lista de respuestas


Relacionados problema

1  Set persistente (árbol negro rojo) - seguimiento  ( Persistent set red black tree follow up ) 
Seguimiento de esta pregunta cosas que cambié: arreglado algunos typos variables y métodos renombrados a nombres más descriptivos. (Eliminado 1 varia...

11  Programa de chat "ai"  ( Ai chat program ) 
He lanzado este simple programa de chat, y mientras funciona. Creo que ciertamente podría usar alguna mejora. Así es como funciona. Obtenga la entrada del ...

7  Convierta una lista de conjuntos en la lista mínima de conjuntos que no sean intersectores  ( Convert a list of sets into the minimum list of non intersecting sets ) 
Tengo una lista de conjuntos. Los mismos elementos pueden aparecer en varios conjuntos. Quiero transformar esto en una nueva lista de conjuntos donde: Ca...

1  Optimización divisible de subconjunto más grande  ( Largest divisible subset optimization ) 
Entonces, esta es mi solución al siguiente problema de leetcode: https: // leetcode .com / problemas / mayor-divisible-subconjunto / descripción / ¿Cómo p...

3  Prueba para una matriz que es un subconjunto de otra matriz maestra  ( Test for an array being subset of another master array ) 
Estaba intentando construir una pequeña función de utilidad para verificar si una matriz es parte de otra matriz. Está probando si una matriz es un subconjunt...

7  Forma más rápida de comparar conjuntos genéricos  ( Faster way of comparing generic sets ) 
El siguiente método de extensión es el factor limitante en el desempeño de una solicitud que estoy desarrollando, según Visual Studio 2012 Performance Analysi...

2  Set persistente (árbol negro rojo)  ( Persistent set red black tree ) 
Esta es una estructura de datos parcialmente persistente utilizando un árbol negro rojo. Se copiarán $ O (LG (N)) $ artículos para cada operación eliminar o...

3  Encontrar la cantidad de formas de particionar {1,2, ..., n} en P1 y P2 de tal manera que suma (P1) == SUM (P2)  ( Finding the number of ways to partition 1 2 n into p1 and p2 such that s ) 
Estoy tratando de escribir un algoritmo de espacio y tiempo eficiente para calcular la cantidad de formas de particionar un conjunto de enteros {1, 2, ..., n}...

1  Posibles combinaciones de letras de una almohadilla de marcación en tiempo lineal utilizando un enfoque recursivo  ( Possible letter combinations of a dial pad in linear time using a recursive appr ) 
complejidad de tiempo: Camino la matriz de llaves inzagonadas inicial que representan el número O (n) hacia atrás. Luego hago un paseo interno de la matriz de...

2  Disyointset con O (1) Encuentre y o (1) Unión amortizada  ( Disjointset with o1 find and o1 amortised union ) 
¿Este código supera la implementación común con la compresión de ruta y la unidad por rango? Todavía estoy de acuerdo con una revisión. github import j...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos