Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #24821
| Date | 2012-07-03 09:40 -0500 |
|---|---|
| From | Tim Chase <python.list@tim.thechases.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> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.1746.1341327790.4697.python-list@python.org> (permalink) |
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
Re: Best data structure for DFS on large graphs Tim Chase <python.list@tim.thechases.com> - 2012-07-03 09:40 -0500
csiph-web