On 25 Sep, 20:28, Paul Hankin <[EMAIL PROTECTED]> wrote:
> On Sep 25, 7:58 pm, Steven Bethard <[EMAIL PROTECTED]> wrote:
>
>
>
> > > Paul Hankin wrote:
> > > ...
> > > class sorteddict(dict):
> > > "A sorted dictionary"
> > > def __init__(self, arg=None, cmp=None, key=None, reverse=False):
> > > if arg:
> > > ...
>
> > With this is the implementation, I'm definitely -1. Not because it's a
> > bad implementation, but because if the iteration is always doing a sort,
> > then there's no reason for a separate data structure. Just use sorted()
> > directly on a regular dict. That has the advantage of being much more
> > obvious about where the expensive operations are::
>
> > for key in sorted(d, ...):
> > ... whatever you want to do ...
>
> > IMHO, the only reason to introduce a sorteddict() is if it minimizes the
> > cost of sorting the keys.
>
> I disagree with your reason for introducing a sorteddict - the main
> reason should be if it makes code that uses it simpler and more
> readable, with efficiency (within reasonable limits) being of
> secondary importance. Unfortunately for sorteddict, your code is
> simpler and more explicit for most obvious use cases.
>
> But, with Bill's cached sorted key list it'll be reasonably efficient,
> and it's likely possible to update the sorted cache more efficiently
> than resorting if there's only been a small number of insertions since
> the last sort, but I haven't the time to do a thorough job.
>
> --
> Paul Hankin
I think that keeping a sorted list of keys is worthwhile, but because
the key or cmp functions could access keys or values or both you have
to invalidate whenever a key or value is added or changed. Here's my
version (v. similar to yours of course, but sorting when necessary):
class sorteddict(dict):
def __init__(self, iterable=None, cmp=None, key=None,
reverse=False):
if iterable is None:
iterable = []
dict.__init__(self, iterable)
self.__cmp = cmp
self.__key = key
self.__reverse = reverse
self.__keys = None
def update(self, *args, **kwargs):
dict.update(self, *args, **kwargs)
self.__keys = None
@classmethod
def fromkeys(cls, iterable, value=None):
dictionary = cls()
for key in iterable:
dictionary[key] = value
return dictionary
def copy(self):
dictionary = sorteddict(dict.copy(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
dictionary.__keys = None if self.__keys is None else
self.__keys[:]
return dictionary
def clear(self):
self.__keys = None
dict.clear(self)
def setdefault(self, key, value):
self.__keys = None
return dict.setdefault(self, key, value)
def pop(self, key, value=None):
if key not in self:
return value
self.__keys = None
return dict.pop(self, key, value)
def popitem(self):
self.__keys = None
return dict.popitem(self)
def keys(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return self.__keys[:]
def values(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return [self[key] for key in self.__keys]
def items(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return [(key, self[key]) for key in self.__keys]
def __iter__(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return iter(self.__keys)
def iterkeys(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return iter(self.__keys)
def itervalues(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
for key in self.__keys:
yield self[key]
def iteritems(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
for key in self.__keys:
yield key, self[key]
def __delitem__(self, key):
self.__keys = None
dict.__delitem__(self, key)
def __setitem__(self, key, value):
self.__keys = None
dict.__setitem__(self, key, value)
def __repr__(self):
return str(self)
def __str__(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return "{%s}" % ", ".join(
["%r: %r" % (key, self[key]) for key in self.__keys])
--
http://mail.python.org/mailman/listinfo/python-list
