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

Groups > comp.lang.python > #24819

Re: Best data structure for DFS on large graphs

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 <miheer.dew@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.021
X-Spam-Evidence '*H*': 0.96; '*S*': 0.00; 'context': 0.05; 'python': 0.09; 'deletion': 0.09; 'insertion': 0.09; 'cc:addr:python-list': 0.10; 'dictionaries': 0.16; 'wrote:': 0.17; 'stefan': 0.17; 'url:moin': 0.17; 'cc:2**0': 0.23; 'cc:no real name:2**0': 0.24; 'cc:addr:python.org': 0.25; 'header:In-Reply-To:1': 0.25; 'url:wiki': 0.26; 'message-id:@mail.gmail.com': 0.27; 'lists': 0.31; 'url:python': 0.32; 'right?': 0.33; 'subject:data': 0.33; 'received:google.com': 0.34; 'list': 0.35; 'built-in': 0.35; 'pm,': 0.35; 'received:209.85': 0.35; 'there': 0.35; 'but': 0.36; 'url:org': 0.36; 'url:library': 0.36; 'does': 0.37; 'received:209': 0.37; 'subject:: ': 0.38; 'mean': 0.38; 'url:docs': 0.38; 'header:Received:5': 0.40; 'help': 0.40; 'jul': 0.65; 'bst': 0.84; '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=Kx9dTkqViFL+0vbfRenb1Yk3slYhvveoSgXK2cC/dc4=; b=lp9UjQHxzSqC/xqYXT5WwkOEfWL6Uj+lC303TMJFPAl094zWZtPF0RFdYjePPdagwk kqiunPtxpDpRkQemX5jWeYRWs/JhVl1uWqtjei9IrBotJowmobi53LGr9ORUZA4tVEEW dWBSRK2zi0V7Ia9JY5+7KsxY+yNiuEtapZ9rRnMf7iXKw4QtywC5nE9hW8QJOOUsS+dK sBZnhPKOuJJL9CxFmPMYjn5c5aQrPgfCS/PJHzkH3F9GcRvgh8k6+471KN4zwQ3vESRz 4INeTn5smVHIjHb1agccGxF3USK0qZTXUBG47/gDFTQfFUUud5W3txXg6oT6gyTx+ju6 ZjKA==
MIME-Version 1.0
In-Reply-To <jsukoe$aui$1@dough.gmane.org>
References <CACA+676A=G=3+wvaHw3H0LAo2cghztXo4+9ORR73CXBOOpW0ZQ@mail.gmail.com> <jsukoe$aui$1@dough.gmane.org>
Date Tue, 3 Jul 2012 19:09:44 +0530
Subject Re: Best data structure for DFS on large graphs
From Miheer Dewaskar <miheer.dew@gmail.com>
To Stefan Behnel <stefan_ml@behnel.de>
Content-Type text/plain; charset=ISO-8859-1
Cc python-list@python.org
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.1742.1341322787.4697.python-list@python.org> (permalink)
Lines 25
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1341322787 news.xs4all.nl 6934 [2001:888:2000:d::a6]:44027
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:24819

Show key headers only | View raw

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?

> > Anyway, does python have a built-in BST like data-structure ?
>
> It has lists and bisect:
>
> http://docs.python.org/library/bisect.html

But insertion and deletion in a list is o(n):

http://wiki.python.org/moin/TimeComplexity/#list




--
Miheer Dewaskar

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

Thread

Re: Best data structure for DFS on large graphs Miheer Dewaskar <miheer.dew@gmail.com> - 2012-07-03 19:09 +0530

csiph-web