On Tue, Jul 3, 2012 at 8:10 PM, Tim Chase <python.l...@tim.thechases.com> wrote: > On 07/03/12 08:39, Miheer Dewaskar wrote: >> On Tue, Jul 3, 2012 at 4:53 PM, Stefan Behnel <stefan...@behnel.de> wrote: >>> >>> Miheer Dewaskar, 03.07.2012 13:11: >>>> I am not sure,but if there are large number of states Dictionaries wont >>>> help much right? >>> >>> Dicts are fast for lookup, not for searching. >>> >> What do you mean by searching in the context of Dicts? > > It took me a while to parse Stefan's post, and I *think* he means > that key-indexing (direct lookup) is fast O(1), and that by > "searching" he means something like "find all keys/values matching > property $FOO" such as between a range. > > One of the important things you omit is how you define "large". Is > this a couple thousand? Hundreds of thousands? Millions?
I want it to be a generic Game solver.So the number of states depends on the game. For a simple tic-tac-toe the upper bound is 3^9 states.But for more complex games it could be much larger. I would like to assume that the number of states can grow arbitrarily large. > Also, what sort of information are you keeping in the state? Just > available transitions? Or do you want additional metadata? If it's > just transition mappings (A->B) rather than complex objects, I'd try > using a dict first, and if it's too large, I'd reach for the > "anydbm" module to store them to disk. The state just has 'state data'.The transitions are obtained by functions analyzing the state. So that I should not be able to identify between two same states that have been reached by different means. For example in the tic-tac-toe game the states can be a 3x3 box of integers 0 -> unoccupied 1 -> x 2-> o ( (2,0,1), o - x (1,1,0), -> x x - (2,0,0) ) o - - -- Miheer Dewaskar -- http://mail.python.org/mailman/listinfo/python-list
