Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #24821

Re: Best data structure for DFS on large graphs

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 <python.list@tim.thechases.com>
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 <python.list@tim.thechases.com>
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 <miheer.dew@gmail.com>
Subject Re: Best data structure for DFS on large graphs
References <CACA+676A=G=3+wvaHw3H0LAo2cghztXo4+9ORR73CXBOOpW0ZQ@mail.gmail.com> <jsukoe$aui$1@dough.gmane.org> <CACA+677Kz_6OnYpQQz7MLqdikD_Oe1XHGm8EDjZM+kwH35T2Aw@mail.gmail.com>
In-Reply-To <CACA+677Kz_6OnYpQQz7MLqdikD_Oe1XHGm8EDjZM+kwH35T2Aw@mail.gmail.com>
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 <stefan_ml@behnel.de>
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.12
Precedence list
List-Id General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups comp.lang.python
Message-ID <mailman.1746.1341327790.4697.python-list@python.org> (permalink)
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

Show key headers only | View raw

On 07/03/12 08:39, Miheer Dewaskar wrote:
> On Tue, Jul 3, 2012 at 4:53 PM, Stefan Behnel <stefan_ml@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?

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

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: Best data structure for DFS on large graphs Tim Chase <python.list@tim.thechases.com> - 2012-07-03 09:40 -0500

csiph-web