Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.002 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'context': 0.05; 'objects,': 0.07; 'omit': 0.07; 'dict': 0.09; 'integers': 0.09; 'to:addr:python.list': 0.09; 'to:addr:tim.thechases.com': 0.09; 'to:name:tim chase': 0.09; 'cc:addr:python-list': 0.10; 'assume': 0.11; '(direct': 0.16; 'arbitrarily': 0.16; 'dictionaries': 0.16; 'disk.': 0.16; 'means.': 0.16; 'range.': 0.16; 'received:209.85.216.53': 0.16; 'wrote:': 0.17; 'stefan': 0.17; 'tim': 0.18; '>>>': 0.18; 'module': 0.19; 'define': 0.20; 'sort': 0.21; 'large,': 0.22; 'parse': 0.22; "i'd": 0.22; 'example': 0.23; 'matching': 0.23; 'cc:no real name:2**0': 0.24; 'cc:2**1': 0.24; 'cc:addr:python.org': 0.25; 'header:In-Reply-To:1': 0.25; 'first,': 0.27; 'transition': 0.27; 'message-id:@mail.gmail.com': 0.27; '>>>>': 0.29; 'chase': 0.29; 'large.': 0.29; 'could': 0.32; 'right?': 0.33; 'subject:data': 0.33; 'received:google.com': 0.34; 'generic': 0.35; 'pm,': 0.35; 'received:209.85': 0.35; 'something': 0.35; 'there': 0.35; 'depends': 0.36; 'should': 0.36; 'too': 0.36; 'two': 0.37; 'rather': 0.37; 'received:209': 0.37; 'received:209.85.216': 0.37; 'subject:: ': 0.38; 'store': 0.38; 'mean': 0.38; 'things': 0.38; 'header:Received:5': 0.40; 'help': 0.40; 'identify': 0.61; 'between': 0.63; 'different': 0.63; 'information': 0.63; 'more': 0.63; 'reached': 0.65; 'jul': 0.65; 'obtained': 0.71; 'state.': 0.71; 'grow': 0.74; 'upper': 0.75; 'subject:Best': 0.91 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=S327SntBH9t7VncI1U6WI4zyoIk83utRSMM0pyG9fk8=; b=fSKS7v626ziUAzprGsBpQJDpJ5+I37BdoI7FihxzOeaRzJv0c9WK473NLlBFk8Nn3C 0Tv+xUk0ECPgJeENo88kirGeoKYJb9UZ94kmnSf8GBlf5TXZyh8L2wQXRHO1D4mcPWha e2QpA4owvgcu5QoMduS4zdlmzURErKIcDhIqpBwqyYiJ76FIyh8K6ybVmnMzmbjed4yK VKYWgsGn+kNXmaZREjn70uB9w7ShV2nkrQKXTYZXKOKFufgjIWy8RrFd+XRrwpgzJy3A lRzXPSQ/9UDXrFI6nBKEzeR0Bba6QQ39SG/9ZlHjg9YYcF4S99AztB/ttWnT6GiaFii8 QeZA== MIME-Version: 1.0 In-Reply-To: <4FF3044A.9060206@tim.thechases.com> References: <4FF3044A.9060206@tim.thechases.com> Date: Tue, 3 Jul 2012 20:38:05 +0530 Subject: Re: Best data structure for DFS on large graphs From: Miheer Dewaskar To: Tim Chase Content-Type: text/plain; charset=ISO-8859-1 Cc: python-list@python.org, Stefan Behnel X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 51 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1341328088 news.xs4all.nl 6875 [2001:888:2000:d::a6]:59987 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:24822 On Tue, Jul 3, 2012 at 8:10 PM, Tim Chase wrote: > On 07/03/12 08:39, Miheer Dewaskar wrote: >> On Tue, Jul 3, 2012 at 4:53 PM, Stefan Behnel 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