[Python-3000] ordered dict for p3k collections? (original) (raw)

Jason Orendorff jason.orendorff at gmail.com
Wed Sep 26 20:07:19 CEST 2007

One situation where a sorteddict would win is finding upper and lower bounds. This especially matters if you want to iterate over a specific range of keys: "show me all entries between 1 Jan 2007 and 1 Feb 2007" is O(N) in the number of entries in that range, not the entire data set.

I think people ask for things like this because they have a high-level need like "read 3 log files, jam all the data into a single data structure, and extract time slices from that" for which no particularly obivous combination of lists and dicts seems to jump out at you. Then they hit on an idea like sorteddict that looks like it might get them 60% of the way there and seems like a simple, obvious building block that belongs in the stdlib. That's my own experience, anyway.

Is sorteddict really such a great building block? I dunno. It seems like that might or might not be true. These situations seem to come up pretty rarely in Python's problem domain, so it's hard to get a feel for it.

I do know from recent personal experience that system-level code often wants custom data structures, and having spent a decade with Python lists and dictionaries, I'm out of shape. :)

-j

More information about the Python-3000 mailing list