Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!ecngs!feeder2.ecngs.de!newsfeed.freenet.ag!news2.euro.net!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.001 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'context': 0.05; 'objects,': 0.07; 'omit': 0.07; 'dict': 0.09; 'cc:addr:python- list': 0.10; '(direct': 0.16; '-tkc': 0.16; 'dictionaries': 0.16; 'disk.': 0.16; 'from:addr:python.list': 0.16; 'from:addr:tim.thechases.com': 0.16; 'from:name:tim chase': 0.16; 'message-id:@tim.thechases.com': 0.16; 'range.': 0.16; 'received:70.251': 0.16; 'received:dsl.rcsntx.swbell.net': 0.16; 'received:rcsntx.swbell.net': 0.16; 'received:swbell.net': 0.16; 'wrote:': 0.17; 'stefan': 0.17; '>>>': 0.18; 'module': 0.19; 'define': 0.20; 'sort': 0.21; 'large,': 0.22; 'parse': 0.22; "i'd": 0.22; '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; 'header:User-Agent:1': 0.26; 'first,': 0.27; 'transition': 0.27; 'right?': 0.33; 'subject:data': 0.33; 'pm,': 0.35; 'something': 0.35; 'there': 0.35; 'too': 0.36; 'rather': 0.37; 'subject:: ': 0.38; 'store': 0.38; 'mean': 0.38; 'things': 0.38; 'help': 0.40; 'between': 0.63; 'information': 0.63; 'jul': 0.65; 'received:50.22': 0.84; 'subject:Best': 0.91 Date: Tue, 03 Jul 2012 09:40:10 -0500 From: Tim Chase User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.24) Gecko/20111120 Icedove/3.1.16 MIME-Version: 1.0 To: Miheer Dewaskar Subject: Re: Best data structure for DFS on large graphs References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - boston.accountservergroup.com X-AntiAbuse: Original Domain - python.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - tim.thechases.com X-Source: X-Source-Args: X-Source-Dir: 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: 29 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1341327790 news.xs4all.nl 6883 [2001:888:2000:d::a6]:56661 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:24821 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? 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. -tkc