[Python-Dev] Proposal: add odict to collections (original) (raw)

"Martin v. Löwis" martin at v.loewis.de
Sun Jun 15 10:48:25 CEST 2008

... like your implementation. It is not too hard to get the delitem O(log n) compared to your O(n), see here:

http://codespeak.net/svn/user/arigo/hack/pyfuse/OrderedDict.py So many people are implementing this kind of data type but do not really care about making as fast as it could be ... IMHO yet another reason to ship a usable implementation with Python.

If you use a linked list instead of Python list, you can even do deletion in O(1). Of course, memory consumption will be higher.

Regards, Martin

More information about the Python-Dev mailing list