Hi I have written a simple game of life code in that uses 2 arrays, one which maintains current state and another which maintains next state. Can anyone suggest how to optimize this program for memory consumption. Ideally, I would like its space complexity to be less than RC.
+2
A:
I don't know too much about GOL, but assuming that there are many empty 'squares', have you looked at Sparse Matrixes?
nonnb
2010-08-24 08:11:55
+4
A:
It depends on how sparse your playing field is. If your playing field is dense, then the space complexity of any storage algorithm will trend towards RC. (Specifically, RC/2, since once you get more active cells than inactive cells, you can just store the inactive cells instead if you really cared that much about optimal space usage.)
If the playing field is sparse, you can get something that scales instead with the number of active cells by simply storing coordinate pairs per active cell or some other sparse matrix structure.
Amber
2010-08-24 08:12:09
i didnt quite get storing inactive cells instead of active cells part...in my current program I create an array of RxC where each element is either active or inactive. No matter what you do that memory has been allocated...how does active or inactive count change that number?
techbeast
2010-08-24 08:20:37
This would be if you were storing (r,c) pairs instead of creating a full matrix.
Amber
2010-08-24 08:23:43
so if i were storing (r,c) pairs, then during evolution stage, it would become a search operation for get the count of "alive" neighbors...any clever way to optimize that?
techbeast
2010-08-24 08:29:11
Take a look at the wikipedia page for sparse matrices - there are some storage techniques that allow you to still fairly quickly look up "adjacent" cells. The other option would be to store the (r,c) pairs as keys in a hash table, where the lookup time is O(1) - thus giving you constant-time lookup.
Amber
2010-08-24 16:20:59
A:
The other answerers have a good point in looking for other data structures for your states. But regardless of that, a simple optimisation might be working with two pointers to states (you might do this already). So instead of doing two array copies you do one copy and three pointer assigments:
state curr, next;
[...]
for (;;) {
next = advance(curr);
curr = copy(next);
}
To this:
state s1, s2;
state *curr, *next;
[...]
for (;;) {
*next = advance(*curr);
/* swap pointers */
state *tmp = curr;
curr = next;
next = tmp;
}
schot
2010-08-24 08:26:50
A:
I recommend sparse matrices, as nonnb and Amber recommended. You could also look into encoding, if you have processor power to burn, or want to serialize to disk. RLE or token based compression might get you somewhere.
Merlyn Morgan-Graham
2010-08-24 08:28:40