[Python-ideas] ordered dict

[Josiah Carlson]

"BJörn Lindqvist" <bjourne at gmail.com> wrote:
> On 4/26/07, Josiah Carlson <jcarlson at 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 at 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 at 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).