0

If I execute these lines of code in python:

states = itertools.product("012",repeat = 16)
states = list(states)

Then I use up more memory than I have on my laptop. Is there a way around this? I need this list of states so that when I generate a new state, I can update its value in the list.

Edit: I'm storing these states for a 4x4 grid,where 0, 1, and 2 are the possible states of each square on the grid. The value being stored is actually a 16 length list that says what the reward is for making a move to any of the squares on the grid from the current state. With impossible moves being marked with -np.inf. As the game is played the reward for moves that lead to winning from certain states increases, so that the bot is more likely to make that move in the future.

Ex: A simplified example for tic-tac-toe.

x| |o
 | | 
o| |

This state would be translated to a 9 length list, '102000200', and when it'd be looked up in the list of all possible states to see what the next best move is. Which in this case would be the middle spot for x.

Alxander
  • 323
  • 1
  • 3
  • 9
  • Describe your problem more clearly. What states? Update what value? – simonzack Nov 29 '14 at 06:43
  • That's ~43 million states. Could you not use a sparse representation, e.g. a dictionary (or `defaultdict`), where each key would be a tuple of strings (or just the string, or an integer made assuming the string is a number in base 3)? – jonrsharpe Nov 29 '14 at 10:09
  • Updated with a bit more information. I'm not sure how a dictionary would save space, wouldn't still be storing just as many values? – Alxander Nov 29 '14 at 17:32

2 Answers2

2

I've just tested this on Python 3.4 (64 bit).

The resulting list is big, but not enormous (or so it seems):

>>> import itertools, sys
>>> states = itertools.product("012",repeat = 16)
>>> s = list(states)
>>> sys.getsizeof(s)
357571088

And my initial speculation that a list of strings would be smaller is incorrect - that didn't make much of a difference.

However, I can see that Python's memory usage increases from 4 MB (after launch) to about 8 GB after the call to list, and it only returns to the baseline state after del(s), not after gc.collect() so it appears that there is some enormous overhead associated with such a large, multi-element list. It may have something to do with what Alex Martelli described here, in which case any Python solution will become quite complicated.

Perhaps you need to think about a different approach to the problem. You don't really need to store all those states - it's easy to calculate what item number 123456 of that list will be, so perhaps you only need to store the ones that are modified during the program's run?

Community
  • 1
  • 1
Tim Pietzcker
  • 328,213
  • 58
  • 503
  • 561
  • I did consider an approach where you only store the states that are actually generated, but my algorithm uses a prediction of a bots future move. The future move can't be predicted without that value already being initialized. – Alxander Nov 29 '14 at 18:13
2

itertools.product returns an iterator. converting to the list is the step that uses a lot of memory. can you write your algorithm to iterate over the product without storing it? like

for tuple16 in itertools.product("012", repeat = 16):
    do_something(tuple16)
japreiss
  • 11,111
  • 2
  • 40
  • 77