"BJörn Lindqvist" <bjourne@gmail.com> wrote:
On 4/26/07, Josiah Carlson <jcarlson@uci.edu> wrote:
Similar fuck ups are possible when using dicts. In practice this is not a problem. An ordered dict doesn't need any more safeguards than Python's already existing data structures. Using the natural order of its items are just fine and when you need something more fancy, override the __eq__ method or give the collections sort method a comparator function argument. [snip] I really do not understand what you are talking about. Maybe you have misunderstood something?
In your post with Message-Id: <740c3aec0704202128g6537c5bfv94c0f60a5d883d76@mail.gmail.com> you state...
l = [(), "moo", 123, []] l.sort() l [123, [], 'moo', ()]
If it is not a problem for lists it is not a problem for ordered dictionaries.
I pointed out in a reply to that message that it would be a problem because the sort will fail in Python 3.x . In your post with Message-Id: <740c3aec0704210817m3e11a9e5lb3325523e2490348@mail.gmail.com> you offer...
Alternatively, you could require a comparator function to be specified at creation time.
Now you offer Java TreeMap as an example of semantics that you would like to duplicate, from which I now understand the context of offering a 'comparator function'. Your current desired semantics are possible in Python 3.x, as it no longer relies on a total ordering, but merely a "natural ordering" (which should be defined for all a,b pairs both of type c), which list.sort() will rely on in 3.x as well. The question at this point is whether or not we want the equivalent of a Java TreeMap in Python. I'm leaning towards no, as I have found very few uses of such things in my own code. There's also the fact that Daniel Stutzbach's BList implementation (which may make it into Python's collections module), would allow for a more or less equivalent implementation of your desired semantics using bisect, though each operation would suffer an O(logn) slowdown for overall O(nlog^2n) sorting and O(log^2n) insertion/deletion/search per item (O(logn) queries, O(logn) per query*). Would that be sufficient? - Josiah * The BList is at worst log base 64 (at beast 128), so if you are emulating a TreeMap using BList and bisect, then in the worst case of 1 billion items in your TreeMap, you are running at around 1/5 the speed of an equivalent Red-Black tree (1/4 at 16 million, 1/3 at 256k, 1/2 at 4k).