On Jan 20, 5:02 pm, "Jan Kaliszewski" <z...@chopin.edu.pl> wrote: > Hello, > > Inspired by some my needs as well as some discussions in the net, I've > implemented a sorted dictionary (i.e. a dict that returns keys, values and > items always sorted by keys): > > http://code.activestate.com/recipes/576998/ > > Maybe it'll appear to be useful for somebody... And I'm curious about your > opinions.
Using an underlying list to track sorted items means that insertion and deletion take O(n) time. That could be reduced to O(log n) time by using a blist or skiplist as the underlying structure for maintaining a sort. The other alternative is to just append items to the list and sort the list on demand. Since the Timsort takes advantage of existing order, the process will approach O(n) if sorting after every few updates. This is close the O(n) time it takes to iterate the list in the first place: s = SortedDict(items) list(s) # O(n log n) to sort and O(n) to iterate s[newkey] = newval list(s) # close to O(n) my two cents, Raymond -- http://mail.python.org/mailman/listinfo/python-list
