grab dict keys/values without iterating ?!
roy at panix.com
Wed Dec 11 15:46:12 CET 2013
In article <3efc283f-419d-41b6-ad20-c2901c3b9f78 at googlegroups.com>,
rusi <rustompmody at gmail.com> wrote:
> The classic data structure for this is the trie:
> General idea: http://en.wikipedia.org/wiki/Trie
> In python:
I agree that a trie fits the problem description well. If I were coding
this up in C or C++, that's probably the data structure I'd use, with
each node containing an array of pointers to nodes, and the array
indexed by the ascii value of the next character (this doesn't translate
well to unicode). Lookup speed would be awesomely fast.
The problem is, that doesn't make a whole lot of sense in Python. The
cited implementation uses dicts at each level. By the time you've done
that, you might as well just throw all the data into one big dict and
use the full search string as the key. It would be a lot less code, and
probably run faster.
Still, as an exercise in learning about a useful (and under-appreciated)
data structure, implementing this as a trie sounds like a wonderful idea.
More information about the Python-list