[Python-Dev] Proposal: add odict to collections
Steven D'Aprano
steve at pearwood.info
Sun Jun 15 10:38:55 CEST 2008
On Sun, 15 Jun 2008 02:59:51 pm David Wolever wrote:
> And, as far as questions about the definition of an ordered
> dictionary, is there any good reason not to simply treat the dict as
> a list? Something like (with the obvious bits left out):
Yes.
(1) If you implement the ordered dict as a list of key/value pairs, then
you get order for free, but searching is slow, and so is deletion. If
we wanted O(N) searches, we'd just use a list of tuples :)
(2) If you implement it as a hash table plus a list of keys in insertion
order, then searching the dict is fast, but deletions are slow. Also
you double (?) the amount of memory needed for the keys.
On the other hand... a tree-based implementation would require more
work, and many more decisions (what kind of tree?), would lose the O(1)
behaviour of the hash table, and may end up using just as much memory.
So I wouldn't discount your suggestion.
--
Steven
More information about the Python-Dev
mailing list