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

Groups > comp.lang.python > #24821 > unrolled thread

Re: Best data structure for DFS on large graphs

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

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

#24821 — Re: Best data structure for DFS on large graphs

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

[toc] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web