On 25 Sep, 22:33, Paul Hankin <[EMAIL PROTECTED]> wrote: > On Sep 25, 9:55 pm, Mark Summerfield <[EMAIL PROTECTED]> > wrote: > > > ... > > class sorteddict(dict): > > > ... > > if self.__keys is None: > > self.__keys = sorted(dict.keys(self), cmp=self.__cmp, > > key=self.__key, > > reverse=self.__reverse) > > You'd be better defining __keys like this: > > def __getkeys(self): > if self.__keycache is None: > self.__keycache = dict.keys(self) > self.__keycache.sort(cmp=...) > return self.__keycache > > __keys = property(__getkeys) > > and where you have 'self.__keys = None', either replace with > 'self.__keycache = None' or more cleanly with a call to: > > def __invalidate_key_cache(self): > self.__keycache = None > > to improve the code quality.
Yes, that's much better. As you've no doubt realised, this particular implementation gives best performance when the pattern of use is: lots of edits, lots of lookups, ..., and gives worst performance when the pattern of use is: edit, lookup, edit, lookup (in which case using a dict and sorted() is probably better). So there is lots of scope for someone to do a version that has good performance for all patterns of use:-) I've put a full version with doctests & docstrings on PyPI: http://pypi.python.org/pypi/sorteddict Here's the stripped version (just 92 lines): 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.__keycache = None @property def __keys(self): if self.__keycache is None: self.__keycache = dict.keys(self) self.__keycache.sort(cmp=self.__cmp, key=self.__key, reverse=self.__reverse) return self.__keycache def __invalidate_key_cache(self): self.__keycache = None def update(self, *args, **kwargs): self.__invalidate_key_cache() dict.update(self, *args, **kwargs) @classmethod def fromkeys(cls, iterable, value=None): dictionary = cls() for key in iterable: dictionary[key] = value return dictionary def copy(self): return sorteddict(dict.copy(self), cmp=self.__cmp, key=self.__key, reverse=self.__reverse) def clear(self): self.__invalidate_key_cache() dict.clear(self) def setdefault(self, key, value): self.__invalidate_key_cache() return dict.setdefault(self, key, value) def pop(self, key, value=None): if key not in self: return value self.__invalidate_key_cache() return dict.pop(self, key, value) def popitem(self): self.__invalidate_key_cache() return dict.popitem(self) def keys(self): return self.__keys[:] def values(self): return [self[key] for key in self.__keys] def items(self): return [(key, self[key]) for key in self.__keys] def __iter__(self): return iter(self.__keys) def iterkeys(self): return iter(self.__keys) def itervalues(self): for key in self.__keys: yield self[key] def iteritems(self): for key in self.__keys: yield key, self[key] def __delitem__(self, key): self.__invalidate_key_cache() dict.__delitem__(self, key) def __setitem__(self, key, value): self.__invalidate_key_cache() dict.__setitem__(self, key, value) def __repr__(self): raise NotImplementedError() def __str__(self): return "{%s}" % ", ".join( ["%r: %r" % (key, self[key]) for key in self.__keys]) -- http://mail.python.org/mailman/listinfo/python-list
