Ordered dicts

[bearophileHUGS]

I have found that in certain situations ordered dicts are useful. I use
an Odict class written in Python by ROwen that I have improved and
updated some for personal use.

So I'm thinking about a possible C version of Odict (maybe fit for the
collections module).

On a 32 bit Win Python 2.5 requires about:
28.2 bytes/element for set(int)
36.2 bytes/element for dict(int:None)

Deleted keys from a dict/set aren't removed, they are tagged as
deleted.
My experience of CPython sources is tiny, I have just read few parts,
so a person much more expert than me can comment the following lines.

During the printing of the set/dict I think such flags are just read
and skipped one after the other.

So I think to keep the insertion order of the keys a simple chained
list is enough, each inserted key has a pointer to the successive one
(even deleted keys). So theoretically an Odict of (int:None) can
require just 40.2 bytes/element (Python Odicts require much more
memory, because they ).
(I don't know if some extra memory for the garbage collector is
necessary, I don't think so.)

The simple linked list has to be managed (tail insertions only), and
scanned from the listHead inside iterating methods like iteritems,
items, values, etc.

If such solution is possibile, then how much difficult is such
implementation?

Bye,
bearophile

 

[Neil Cerutti]

I have found that in certain situations ordered dicts are
useful. I use an Odict class written in Python by ROwen that I
have improved and updated some for personal use.

So I'm thinking about a possible C version of Odict (maybe fit
for the collections module).

Check out http://sourceforge.net/projects/pyavl/ for a probably
useful sorted mapping type, already implemented in C as an
extension module.

However, I haven't tried it myself.

 

[Duncan Booth]

Deleted keys from a dict/set aren't removed, they are tagged as
deleted.
My experience of CPython sources is tiny, I have just read few parts,
so a person much more expert than me can comment the following lines.

During the printing of the set/dict I think such flags are just read
and skipped one after the other.

So I think to keep the insertion order of the keys a simple chained
list is enough, each inserted key has a pointer to the successive one
(even deleted keys).

Not quite. Dictionary slots containing deleted keys are available for re-
use. In an ordinary dictionary you just overwrite the deleted flag with the
new value, but for your ordered dictionary if you did that you would have
to fix up the linked list.

Probably the simplest solution for an odict would be to keep the key in the
dictionary after deletion but mark it as deleted (by setting the value to
null). Then if you reinsert the deleted value it goes back in at its
original order.

The catch of course is that keys then never get released, but you can
always compact an odict by copying it:

d = odict(d)

which should preserve the order but release the deleted keys (assuming no
other references to the original copy).

The simple linked list has to be managed (tail insertions only), and
scanned from the listHead inside iterating methods like iteritems,
items, values, etc.

You would also need to make sure that internal iterations also go through
the linked list order. e.g. resizing a dict currently just goes through
each entry inserting it into the new dict.

If such solution is possibile, then how much difficult is such
implementation?

It sounds easy enough, just a copy of the existing dict code with a few
minor tweaks.

 

[bearophileHUGS]

Thank to Neil Cerutti and Duncan Booth for the answers. I have not
tried that C AVL implementation yet.

Duncan Booth:

but for your ordered dictionary if you did that you would have
to fix up the linked list.

To fix the list in constant time you probably need a doubly-linked
list, this requires more memory (or the bad xor trick) and more code
complexity.

Then if you reinsert the deleted value it goes back in at its original order.

Uhm, this doesn't sound good. Thank you, I missed this detail
Then the doubly-linked list, and the links fixing seem necessary...

Bear hugs,
bearophile

 

[Duncan Booth]

Uhm, this doesn't sound good. Thank you, I missed this detail
Then the doubly-linked list, and the links fixing seem necessary...

An alternative to a doubly linked list might be to never reuse deleted
entries but if the number of deleted entries exceeds a certain proportion
just pack the dictionary.

 

[Steve Holden]

I have found that in certain situations ordered dicts are useful. I use
an Odict class written in Python by ROwen that I have improved and
updated some for personal use.

So I'm thinking about a possible C version of Odict (maybe fit for the
collections module).

On a 32 bit Win Python 2.5 requires about:
28.2 bytes/element for set(int)
36.2 bytes/element for dict(int:None)

Deleted keys from a dict/set aren't removed, they are tagged as
deleted.
My experience of CPython sources is tiny, I have just read few parts,
so a person much more expert than me can comment the following lines.

During the printing of the set/dict I think such flags are just read
and skipped one after the other.

So I think to keep the insertion order of the keys a simple chained
list is enough, each inserted key has a pointer to the successive one
(even deleted keys). So theoretically an Odict of (int:None) can
require just 40.2 bytes/element (Python Odicts require much more
memory, because they ).
(I don't know if some extra memory for the garbage collector is
necessary, I don't think so.)

The simple linked list has to be managed (tail insertions only), and
scanned from the listHead inside iterating methods like iteritems,
items, values, etc.

If such solution is possibile, then how much difficult is such
implementation?

FYI there was a *long* discussion around the need for Speed sprint about
implementing ordered dicts. As the discussion started by your thread has
started to reveal, everyone has just-ever-so-slightly-different
requirements. IIRC the goal was dropped because it wasn't possible to
agree on a specification.

regards
Steve

 

[bearophileHUGS]

Steve Holden:

I forgot a detail: in the Python version of Odict I use element
deletion is O(n). You need a second dict to improve that (or a duble
linked list of hashing operations, see below).

FYI there was a *long* discussion around the need for Speed sprint about
implementing ordered dicts. As the discussion started by your thread has
started to reveal, everyone has just-ever-so-slightly-different
requirements. IIRC the goal was dropped because it wasn't possible to
agree on a specification.

I received a similar answer about graphs too. But this time I think the
semantic of an ordered dict is simple and clear enough, so I belive a
generally acceptable solution may be found still.
An implementation with double linked lists allows amortized O(1) for
all the usual dict metods, deletions too. Maybe firstkey() lastkey()
methods can be added too, that return the first and last key of the
odict.
The following is a simple example, note that this is a "wrong"
implementation, because you can't scan the keys in the ordered way (you
can scan the values in a ordered way). I presume in a C implementation
you can find the key of a given value. If this isn't possibile without
creating a chain of hashing operations, then I too drop off from this
odict idea

class Odict(dict):
def __init__(self):
dict.__init__(self)
self.lh = None # list header
self.lt = None # list tail

def __getitem__(self, key):
return dict.__getitem__(self, key)[1]

def __setitem__(self, key, val):
if key in self:
dict.__getitem__(self, key)[1] = val
else:
new = [self.lt, val, None]
dict.__setitem__(self, key, new)
if self.lt: self.lt[2] = new
self.lt = new
if not self.lh: self.lh = new

def __delitem__(self, k):
if k in self:
pred,_,succ= dict.__getitem__(self,k)
if pred: pred[2] = succ
else: self.lh = succ
if succ: succ[0] = pred
else: self.lt = pred
dict.__delitem__(self, k)
else: raise KeyError, k

Bye,
bearophile