I am currently working in solving Conway's Game Of Life problem for a Parallel and Distributed Computing course.
The problem is a little bit different form the original, in the sense that instead of having a 2D representation of the cells we have a 3D one, each cell is represented by three ints. When considering neighbours, only the x + 1, x - 1, y + 1, y - 1, z + 1 and z - 1 are considered (no diagonals).
The input of the problem is constituted by the size of the cube (size) where the cells are present, followed by a list of positions of live cells.
The number of cells, is in the order of O(size^2), and the space is in the order of O(size^3).
My current implementation uses C++ maps, in which a key is a tuple with x, y and z, and the value is an integer telling in that position the cell is alive or not. My current approach is to just go through every position available in the cube and check the number of neighbours and update that position accordingly, but i believe this is not ideal because the number of live cells is in the order of O(size^2) and not O(size^3).
My question is how would you improve this solution ? Is there a better data structure to use ? Considering that I have to build an OpenMP implementation (shared memory) for very large input cases (size > 10000).
Thank you !