Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Proposed implementation for an Ordered Dictionary

Reply
Thread Tools

Proposed implementation for an Ordered Dictionary

 
 
Raymond Hettinger
Guest
Posts: n/a
 
      02-26-2009
Here's a proposed implementation for Py2.7 and Py3.1:

http://code.activestate.com/recipes/576669/

Would like you guys to kick the tires, exercise it a bit, and let me
know what you think. The recipe runs under 2.6 and 3.0 without
modification so it should be easy to play with.

The main virtue of the proposed API is a near-zero learning curve.
The API is a same as for regular dictionaries but it remembers the
insertion order and used that for iteration, repr, etc.


Raymond

 
Reply With Quote
 
 
 
 
Benjamin Peterson
Guest
Posts: n/a
 
      02-26-2009
Raymond Hettinger <python <at> rcn.com> writes:

>
> Here's a proposed implementation for Py2.7 and Py3.1:
>
> http://code.activestate.com/recipes/576669/
>
> Would like you guys to kick the tires, exercise it a bit, and let me
> know what you think. The recipe runs under 2.6 and 3.0 without
> modification so it should be easy to play with.


Why not just inherit from collections.MutableMapping?



 
Reply With Quote
 
 
 
 
Hrvoje Niksic
Guest
Posts: n/a
 
      02-26-2009
Raymond Hettinger <(E-Mail Removed)> writes:

> Here's a proposed implementation for Py2.7 and Py3.1:
>
> http://code.activestate.com/recipes/576669/


Several methods like __contains__() and __getitem__() are not
overridden, so their performance is just as fast as a regular
dictionary.

Methods like __setitem__ and __delitem__ are overridden but have a
fast path depending on whether or not the key already exists.

It seems that __delitem__ of an existing key is O(n), whereas it's
amortized constant time for dicts. (__setitem__ is constant time for
both.) Is there a way to avoid this?

If not, it should probably be documented, since it differs from dict.
 
Reply With Quote
 
Raymond Hettinger
Guest
Posts: n/a
 
      02-26-2009
[Benjamin Peterson]
> Why not just inherit from collections.MutableMapping?


It makes the recipe shorter to inherit some methods from dict. Also,
subclassing from dict gives a speedup for __getitem__(), __len__(),
and get().
 
Reply With Quote
 
Raymond Hettinger
Guest
Posts: n/a
 
      02-26-2009
[Hrvoje Niksic]
> It seems that __delitem__ of an existing key is O(n), whereas it's
> amortized constant time for dicts. *(__setitem__ is constant time for
> both.) *Is there a way to avoid this?


I don't see any fast/clean way. It's possible to tracking pending
deletions
and do them all at once but that's a bit messy and slow.


> If not, it should probably be documented, since it differs from dict.


That makes sense.


Raymond

 
Reply With Quote
 
Paul Rubin
Guest
Posts: n/a
 
      02-26-2009
Raymond Hettinger <(E-Mail Removed)> writes:
> I don't see any fast/clean way. It's possible to tracking pending
> deletions and do them all at once but that's a bit messy and slow.


What about using a second dictionary (indexed by the incrementing
counter) instead of a list to record the insertion order? Then you
have O(1) deletion, and traversal takes an O(n log n) sorting
operation.
 
Reply With Quote
 
Raymond Hettinger
Guest
Posts: n/a
 
      02-26-2009
[Paul Rubin]
> What about using a second dictionary (indexed by the incrementing
> counter) instead of a list to record the insertion order? *Then you
> have O(1) deletion, and traversal takes an O(n log n) sorting
> operation.


My first attempt used exactly that approach and it works fine
though it does complicate the code quite a bit and slows down
all of the common operations by a constant factor.


Raymond
 
Reply With Quote
 
Raymond Hettinger
Guest
Posts: n/a
 
      02-26-2009
> > What about using a second dictionary (indexed by the incrementing
> > counter) instead of a list to record the insertion order? *Then you
> > have O(1) deletion, and traversal takes an O(n log n) sorting
> > operation.


> My first attempt used exactly that approach and it works fine
> though it does complicate the code quite a bit and slows down
> all of the common operations by a constant factor.


FWIW, here is the code for that approach.

--------------------------------------
from collections import MutableMapping

class OrderedDict(dict):

def __init__(self, *args, **kwds):
if len(args) > 1:
raise TypeError('expected at 1 argument, got %d', len
(args))
self.clear()
self.update(*args, **kwds)

def clear(self):
self.__cached_sort = None
self.__cnt = 0
self.__order = {}
dict.clear(self)

def __setitem__(self, key, value):
if key not in self:
self.__cached_sort = None
self.__cnt += 1
self.__order[key] = self.__cnt
dict.__setitem__(self, key, value)

def __delitem__(self, key):
if key in self:
self.__cached_sort = None
del self.__order[key]
dict.__delitem__(self, key)

def __sorted(self):
# return keys in insertion order and cache the result
if self.__cached_sort is None:
self.__cached_sort = sorted(dict.keys(self),
key=self.__order.__getitem__)
return self.__cached_sort

def __iter__(self):
return iter(self.__sorted())

def __reversed__(self):
return iter(reversed(self.__sorted()))

def popitem(self):
# O(n) cost on the first pop and O(1) on successive pops
if not self:
raise KeyError
key = self.__sorted().pop()
del self.__order[key]
value = dict.pop(self, key)
return key, value

# Methods with indirect access via the above methods

setdefault = MutableMapping.setdefault
update = MutableMapping.update
pop = MutableMapping.pop
keys = MutableMapping.keys
values = MutableMapping.values
items = MutableMapping.items

def __repr__(self):
return '{' + ', '.join(map('%r: %r'.__mod__, self.items())) +
'}'

def copy(self):
return self.__class__(self)

@classmethod
def fromkeys(cls, iterable, value=None):
d = cls()
for key in iterable:
d[key] = value
return d

def __reduce__(self):
# pickle an items list and any extra info in the instance dict
items = list(self.items())
inst_dict = vars(self).copy()
for attr in vars(self.__class__):
inst_dict.pop(attr, None)
return (self.__class__, (items,), inst_dict)

 
Reply With Quote
 
Paul Rubin
Guest
Posts: n/a
 
      02-27-2009
Raymond Hettinger <(E-Mail Removed)> writes:
> > What about using a second dictionary

> My first attempt used exactly that approach and it works fine
> though it does complicate the code quite a bit and slows down
> all of the common operations by a constant factor.


Ehh, I guess I'm not surprised at the slowdown and extra complexity
from the second dict. Oh well. If the module really turns out to be
really used a lot, another (messy) approach would be to write a C
extension that uses a doubly linked list some day.
 
Reply With Quote
 
Raymond Hettinger
Guest
Posts: n/a
 
      02-27-2009
[Paul Rubin]
> Ehh, I guess I'm not surprised at the slowdown and extra complexity
> from the second dict. *Oh well. *If the module really turns out to be
> really used a lot, another (messy) approach would be to write a C
> extension that uses a doubly linked list some day.


That seems like an ideal implementation to me.

O(1): appending, popping, searching, and deletion
O(n): traversal

Raymond
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Performance ordered dictionary vs normal dictionary Navkirat Singh Python 6 07-29-2010 10:18 AM
Re: Performance ordered dictionary vs normal dictionary Chris Rebert Python 0 07-29-2010 06:11 AM
Ordered list inside ordered list DL Javascript 6 11-21-2009 11:43 PM
Yet another ordered dictionary implementation Tom Anderson Python 0 11-26-2005 03:09 AM
Ordered dictionary? Leif K-Brooks Python 13 01-23-2004 11:46 PM



Advertisments