Re: Sorted dictionary

2010-01-21 Thread Arnaud Delobelle
"Jan Kaliszewski" writes: > Dnia 21-01-2010 o 09:27:52 Raymond Hettinger napisał(a): > >> On Jan 20, 5:02 pm, "Jan Kaliszewski" wrote: > >>> http://code.activestate.com/recipes/576998/ > >> Using an underlying list to track sorted items >> means that insertion and deletion take O(n) time. >> Th

Re: Sorted dictionary

2010-01-21 Thread Daniel Stutzbach
On Thu, Jan 21, 2010 at 12:45 PM, Jan Kaliszewski wrote: > Please note that I used funcions from bisect, that use binary search. > > Doesn't it take O(log n) time? > It takes O(log n) time to find the point to insert, but O(n) time to perform the actual insertion. -- Daniel Stutzbach, Ph.D. Pre

Re: Sorted dictionary

2010-01-21 Thread Jan Kaliszewski
Dnia 21-01-2010 o 09:27:52 Raymond Hettinger napisał(a): On Jan 20, 5:02 pm, "Jan Kaliszewski" wrote: http://code.activestate.com/recipes/576998/ 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 usi

Re: Sorted dictionary

2010-01-21 Thread Jan Kaliszewski
Dnia 21-01-2010 o 08:49:22 Chris Rebert napisał(a): On Wed, Jan 20, 2010 at 5:50 PM, Steven D'Aprano wrote: On Thu, 21 Jan 2010 02:02:02 +0100, Jan Kaliszewski wrote: http://code.activestate.com/recipes/576998/ What's the advantage of that over sorting the keys as needed? E.g. for ke

Re: Sorted dictionary

2010-01-21 Thread Jan Kaliszewski
21-01-2010, 07:21:22 Dennis Lee Bieber wrote: How does this differ from all the other "ordered dictionary" schemes out there (and maybe even included in 2.7? I'm still on 2.5) It's completely different, please read first paragraph of page I linked (http://code.activestate.com/recipe

Re: Sorted dictionary

2010-01-21 Thread Daniel Stutzbach
On Thu, Jan 21, 2010 at 2:27 AM, Raymond Hettinger wrote: > 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. > Indeed.

Re: Sorted dictionary

2010-01-21 Thread Bearophile
Raymond Hettinger: > 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. In the collections module it can be useful to have o

Re: Sorted dictionary

2010-01-21 Thread Raymond Hettinger
On Jan 20, 5:02 pm, "Jan Kaliszewski" 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:/

Re: Sorted dictionary

2010-01-20 Thread Chris Rebert
On Wed, Jan 20, 2010 at 5:50 PM, Steven D'Aprano wrote: > On Thu, 21 Jan 2010 02:02:02 +0100, Jan Kaliszewski wrote: > >> Hello, >> >> Inspired by some my needs as well as some discussions in the net, I've >> implemented a sorted dictionary (i.e. a dic

Re: Sorted dictionary

2010-01-20 Thread Steven D'Aprano
On Wed, 20 Jan 2010 22:21:22 -0800, Dennis Lee Bieber wrote: > On Thu, 21 Jan 2010 02:02:02 +0100, "Jan Kaliszewski" > declaimed the following in > gmane.comp.python.general: > >> Hello, >> >> Inspired by some my needs as well as some discussions

Re: Sorted dictionary

2010-01-20 Thread Steven D'Aprano
On Thu, 21 Jan 2010 02:02:02 +0100, Jan Kaliszewski 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://co

Sorted dictionary

2010-01-20 Thread Jan Kaliszewski
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.