1
$\begingroup$

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 !

|cite|improve this question
$\endgroup$
  • $\begingroup$ Welcome to CS.SE! What do you mean by "number of individuals"? (Are you counting the number of non-empty cells?) What do you mean by "the space"? What do you mean by "size"? What data structures have you already considered, and why have you rejected them? It often works better here if you can articulate specific requirements you have for the data structure, rather than asking for open-ended advice. What do you mean by O(size^3) complexity? O(size^3) complexity, for what operation(s)? Why do you think a hashtable will have that complexity? $\endgroup$ – D.W.♦ Mar 27 '17 at 20:34
  • $\begingroup$ Thank you D.W., I have updated the question, to better answer your questions. Can you please take a look ? $\endgroup$ – jbernardo Mar 27 '17 at 20:47
  • $\begingroup$ While initially the number of live cells may be quadratic, as the game progressed it may become cubic. Is the goal simulating only a few steps? In that case, usually the answer is to use some sparse representation, or perhaps some data structure from computational geometry like an octree. $\endgroup$ – Yuval Filmus Mar 27 '17 at 20:53
  • $\begingroup$ The number of simulation rounds is lower than 2000, but what you said is interesting, and I think that is the case. The professor told us that the number of cells compared to the cube will be sparse, I will investigate the octree, never heard of them. Thanks you ! $\endgroup$ – jbernardo Mar 27 '17 at 20:58
1
$\begingroup$

There is a simple solution. Instead of storing a hashmap of all positions, store the set of only the positions that are currently alive. Live cells are included in the set; dead cells are not. When you want to know whether a particular cell is alive or not, look up that position in the set; if it is found, then the cell is alive, otherwise the cell is dead. You can store the set as a hashtable.

You said that you expect only about O(size^2) cells to be alive. My proposal reduces the space complexity to O(size^2), instead of O(size^3). Also, the running time to check whether a particular cell is alive will be O(1). The running time to enumerate all live cells will be O(size^2).

It follows that the running time to compute the next state of the world will be O(size^2). Since each cell has only 4 neighbors, you only need to enumerate O(5 * size^2) = O(size^2) many cells (all of the live cells and their neighbors) to see which will be alive in the next iteration. To tell whether a cell will be alive in the next iteration can be done by examining its state and the state of its 4 neighbors, which can be done in O(1) time.

This approach should also generalize nicely to a parallel/distributed implementation.

This all assumes that the number of live cells is limited to O(size^2) for all iterations. That might be a dubious assumption in practice: the number of live cells can quickly grow to O(size^3), for some initial configurations (in particular, it might take only O(lg size) iterations to go from O(size^2) to O(size^3) live cells).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ In fact, that is the second solution I was implementing right before posting the question. Will finish it and compare the results. Thank you for the long and detailed response ! $\endgroup$ – jbernardo Mar 27 '17 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.