Re: sorteddict PEP proposal [started off as orderedict]

On 12 Oct, 09:17, Paul Rubin wrote: > Mark Summerfield <[EMAIL PROTECTED]> writes: > > Below is a PEP proposal for a sorteddict. ... > > Is this proposal dead? I'd been meaning to post some thoughts which I > still haven't gotten around to writing up, and am wondering wh

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield <[EMAIL PROTECTED]> writes: > Below is a PEP proposal for a sorteddict. ... Is this proposal dead? I'd been meaning to post some thoughts which I still haven't gotten around to writing up, and am wondering whether to keep it on my todo list. -- http://mail.python.org/mailman/lis

Re: sorteddict PEP proposal [started off as orderedict]

Duncan Booth <[EMAIL PROTECTED]> writes: > Ok, your choice, just be aware that by using such a restrictive license you > will dissuade a lot of people from using your code. You've prevented your > module being used in any existing projects with Python license, GPL v2, or > probably any license o

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield <[EMAIL PROTECTED]> wrote: > As for the license, while it is on PyPI, I'll leave it as GPL v 3. If > it was wanted for the standard library (and I can't see that ever > happening), I will happily change it to the one that is preferred for > Python modules. Ok, your choice, just b

Re: sorteddict PEP proposal [started off as orderedict]

On 27 Sep, 08:32, Duncan Booth <[EMAIL PROTECTED]> wrote: > Paul Hankin <[EMAIL PROTECTED]> wrote: > >> A key which is in dict must be either in __keycache or in __addkeys, but > >> never in both. > > > Yes, I'm sorry: you're right. > > > But there's a different bug: if you delete a key that's not

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield wrote: > The sorteddict API that has emerged so far is (1) apart from the > constructor, everything is identical to dict, (2) the constructor > takes the same args as sorted(), so if you want to seed with a dict or > with keywords you write sorteddict(dict(a=1,b=2), ...), (or you c

Re: sorteddict PEP proposal [started off as orderedict]

Paul Hankin <[EMAIL PROTECTED]> wrote: >> A key which is in dict must be either in __keycache or in __addkeys, but >> never in both. > > Yes, I'm sorry: you're right. > > But there's a different bug: if you delete a key that's not in the > dict, you'll add it to the deleted list before the excep

Re: sorteddict PEP proposal [started off as orderedict]

On 2007-09-26, Mark Summerfield <[EMAIL PROTECTED]> wrote: > On 26 Sep, 13:22, Antoon Pardon <[EMAIL PROTECTED]> wrote: >> >> Well you should decide what you want. In a previous exchange one of the >> things that was wanted was that you could already seed a tree by using >> key word arguments so th

Re: sorteddict PEP proposal [started off as orderedict]

On Sep 26, 9:52 pm, Duncan Booth <[EMAIL PROTECTED]> wrote: > Paul Hankin <[EMAIL PROTECTED]> wrote: > >> So should Duncan's > > >> def __removekey(self, key): > >> if key in self.__addkeys: > >> del self.__addkeys[key] > >> else: > >> self.__delkeys.add(

Re: sorteddict PEP proposal [started off as orderedict]

Paul Hankin <[EMAIL PROTECTED]> wrote: >> So should Duncan's >> >> def __removekey(self, key): >> if key in self.__addkeys: >> del self.__addkeys[key] >> else: >> self.__delkeys.add(key) >> >> be changed to: >> >> def __removekey(self, key): >>

Re: sorteddict PEP proposal [started off as orderedict]

[James Stroud ] > Maybe its the PEP killers who act prematurely because I friggin' love > genexps and the little generators they generate. No, it's the PEP author who controls when they ask for pronouncement. The natural instinct is to ask for pronouncement as soon as you have an implementation an

Re: sorteddict PEP proposal [started off as orderedict]

Raymond Hettinger wrote: > As one who was submitted many PEPs, I can advise that the quickest way > to irrevocably kill an idea is to submit a PEP to early (we almost > didn't get genexps because the PEP was submitted pre-maturely). Maybe its the PEP killers who act prematurely because I friggin'

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield <[EMAIL PROTECTED]> writes: > The sorteddict API that has emerged so far is (1) apart from the > constructor, everything is identical to dict, I don't see this as necessary, it's ok if it resembles dict as much as dbm does. > (2) the constructor takes the same args as sorted(),

Re: sorteddict PEP proposal [started off as orderedict]

[Mark Summerfield] > Below is a PEP proposal for a sorteddict. It arises out of a > discussion on this list that began a few weeks ago with the subject of > "An ordered dictionary for the Python library?" It is worth remembering that the long sought after datatype was a dict that could loop over k

Re: sorteddict PEP proposal [started off as orderedict]

On 26 Sep, 16:20, Paul Hankin <[EMAIL PROTECTED]> wrote: > On Sep 26, 3:24 pm, Mark Summerfield <[EMAIL PROTECTED]> > wrote: > > > On 26 Sep, 14:59, Paul Hankin <[EMAIL PROTECTED]> wrote: > > > > On Sep 26, 2:46 pm, Duncan Booth <[EMAIL PROTECTED]> wrote: > > > > > Paul Hankin <[EMAIL PROTECTED]> w

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield wrote: > The sorteddict API that has emerged so far is (1) apart from the > constructor, everything is identical to dict, (2) the constructor > takes the same args as sorted(), so if you want to seed with a dict or > with keywords you write sorteddict(dict(a=1,b=2), ...), (or you

Re: sorteddict PEP proposal [started off as orderedict]

On Sep 26, 3:24 pm, Mark Summerfield <[EMAIL PROTECTED]> wrote: > On 26 Sep, 14:59, Paul Hankin <[EMAIL PROTECTED]> wrote: > > > > > On Sep 26, 2:46 pm, Duncan Booth <[EMAIL PROTECTED]> wrote: > > > > Paul Hankin <[EMAIL PROTECTED]> wrote: > > > > More flexibly, keep a set of inserted keys that hav

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield wrote: > On 26 Sep, 13:22, Antoon Pardon <[EMAIL PROTECTED]> wrote: [...] >> So it seems the API needs some more sorting out. > > I think you missed some of the previous postings. > > The sorteddict API that has emerged so far is (1) apart from the > constructor, everything is id

Re: sorteddict PEP proposal [started off as orderedict]

On 26 Sep, 14:59, Paul Hankin <[EMAIL PROTECTED]> wrote: > On Sep 26, 2:46 pm, Duncan Booth <[EMAIL PROTECTED]> wrote: > > > Paul Hankin <[EMAIL PROTECTED]> wrote: > > > More flexibly, keep a set of inserted keys that haven't yet been > > > included in the sorted list, and a set of deleted keys tha

Re: sorteddict PEP proposal [started off as orderedict]

On Sep 26, 2:46 pm, Duncan Booth <[EMAIL PROTECTED]> wrote: > Paul Hankin <[EMAIL PROTECTED]> wrote: > > More flexibly, keep a set of inserted keys that haven't yet been > > included in the sorted list, and a set of deleted keys that haven't > > yet been removed from the sorted list. The cache is i

Re: sorteddict PEP proposal [started off as orderedict]

Paul Hankin <[EMAIL PROTECTED]> wrote: >> I suspect that for many use patterns you could improve performance >> significantly by having two levels of invalidation for the the key >> list: in __setitem__, if the key already exists you don't need to >> discard the list in __keycache (although if a k

Re: sorteddict PEP proposal [started off as orderedict]

On 26 Sep, 13:22, Antoon Pardon <[EMAIL PROTECTED]> wrote: > On 2007-09-26, Mark Summerfield <[EMAIL PROTECTED]> wrote: > > > > > On 26 Sep, 11:27, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: > >> Mark Summerfield <[EMAIL PROTECTED]> writes: > >> > On 26 Sep, 09:51, Hrvoje Niksic <[EMAIL PROTECTED]> w

Re: sorteddict PEP proposal [started off as orderedict]

Paul Hankin <[EMAIL PROTECTED]> writes: >> An implementation of sorted dict using a balanced tree as the >> underlying data structure would give decent performance in all the >> mentioned use cases. For example, red-black trees search, insert, >> and delete in O(log n) time. > > But dicts do sear

Re: sorteddict PEP proposal [started off as orderedict]

On 2007-09-26, Mark Summerfield <[EMAIL PROTECTED]> wrote: > On 26 Sep, 11:27, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: >> Mark Summerfield <[EMAIL PROTECTED]> writes: >> > On 26 Sep, 09:51, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: >> >> Duncan Booth <[EMAIL PROTECTED]> writes: >> >> > I that's the

Re: sorteddict PEP proposal [started off as orderedict]

On Sep 26, 9:51 am, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: > Duncan Booth <[EMAIL PROTECTED]> writes: > > I that's the point though: you can't write one implementation that has good > > performance for all patterns of use > > An implementation of sorted dict using a balanced tree as the > underly

Re: sorteddict PEP proposal [started off as orderedict]

On Sep 26, 9:31 am, Duncan Booth <[EMAIL PROTECTED]> wrote: > Mark Summerfield <[EMAIL PROTECTED]> wrote: > > 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

Re: sorteddict PEP proposal [started off as orderedict]

On 26 Sep, 11:27, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: > Mark Summerfield <[EMAIL PROTECTED]> writes: > > On 26 Sep, 09:51, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: > >> Duncan Booth <[EMAIL PROTECTED]> writes: > >> > I that's the point though: you can't write one implementation > >> > that has

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield <[EMAIL PROTECTED]> writes: > On 26 Sep, 09:51, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: >> Duncan Booth <[EMAIL PROTECTED]> writes: >> > I that's the point though: you can't write one implementation >> > that has good performance for all patterns of use >> >> An implementation of

Re: sorteddict PEP proposal [started off as orderedict]

On 26 Sep, 09:51, Hrvoje Niksic <[EMAIL PROTECTED]> wrote: > Duncan Booth <[EMAIL PROTECTED]> writes: > > I that's the point though: you can't write one implementation that has good > > performance for all patterns of use > > An implementation of sorted dict using a balanced tree as the > underlyin

Re: sorteddict PEP proposal [started off as orderedict]

Duncan Booth <[EMAIL PROTECTED]> writes: > I that's the point though: you can't write one implementation that has good > performance for all patterns of use An implementation of sorted dict using a balanced tree as the underlying data structure would give decent performance in all the mentioned

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield <[EMAIL PROTECTED]> wrote: > 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

Re: sorteddict PEP proposal [started off as orderedict]

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, > >

Re: sorteddict PEP proposal [started off as orderedict]

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

Re: sorteddict PEP proposal [started off as orderedict]

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):

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield wrote: > Hmmm, managed to confuse myself with 'b' and 'd'! > > d = sorteddict({1:"one", 3:"three", 5:"five", 99:"ninetynine"}) > > d.items() > > [(1, 'one'), (3, 'three'), (5, 'five'), (99, 'ninetynine')] > > d[3], d.value(3) > > ('three', 'ninetynine') > > So using [] return

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield wrote: > On 2007-09-25, Andrew Durdin wrote: >> e.g. sorteddict({1:'a', 3:'b': 5:'c', 99:'d'})[3] should return 'b', not >> 'd'. > > The sorteddict really does work in key order, so: > > d = sorteddict({1:'a', 3:'b', 5:'c', 99:'d'}) > d.items() > [(1, 'a'), (3, 'b'),

Re: sorteddict PEP proposal [started off as orderedict]

On Sep 25, 1:35 pm, thebjorn <[EMAIL PROTECTED]> wrote: > On Sep 25, 10:53 am, Mark Summerfield <[EMAIL PROTECTED]> > wrote: > > > Hi, > > > Below is a PEP proposal for a sorteddict. It arises out of a > > discussion on this list that began a few weeks ago with the subject of > > "An ordered dictio

Re: sorteddict PEP proposal [started off as orderedict]

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 de

Re: sorteddict PEP proposal [started off as orderedict]

Steven Bethard <[EMAIL PROTECTED]> writes: > 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. Agreed. A true sorted dict would keep its keys so

Re: sorteddict PEP proposal [started off as orderedict]

Paul Hankin wrote: > On Sep 25, 12:51 pm, Mark Summerfield <[EMAIL PROTECTED]> > wrote: >> On 25 Sep, 12:19, Paul Hankin <[EMAIL PROTECTED]> wrote: >> >> >> >>> Recall sorted... >>> sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted >>> list >>> So why not construct sorteddicts

RE: sorteddict PEP proposal [started off as orderedict]

> From: Paul Hankin > > > Here's a first go. Sorting occurs when the keys are iterated over, > making it fast (almost as a dict) for construction, insertion, and > deletion, but slow if you're iterating a lot. You should look at some > use cases to decide if this approach is best, or if a sorted

Re: sorteddict PEP proposal [started off as orderedict]

On Sep 25, 12:51 pm, Mark Summerfield <[EMAIL PROTECTED]> wrote: > On 25 Sep, 12:19, Paul Hankin <[EMAIL PROTECTED]> wrote: > > > > > Recall sorted... > > sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted > > list > > > So why not construct sorteddicts using the same idea of so

Re: sorteddict PEP proposal [started off as orderedict]

On Sep 25, 10:53 am, Mark Summerfield <[EMAIL PROTECTED]> wrote: > Hi, > > Below is a PEP proposal for a sorteddict. It arises out of a > discussion on this list that began a few weeks ago with the subject of > "An ordered dictionary for the Python library?", and a similar one on > the P3K mailing

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield wrote: > PEP: XXX > Title: Sorted Dictionary [snip] > In addition, the keys() method has two optional arguments: > > keys(firstindex : int = None, secondindex : int = None) -> list of keys > > The parameter names aren't nice, but using say "start" and "end" would >

Re: sorteddict PEP proposal [started off as orderedict]

On 25 Sep, 12:19, Paul Hankin <[EMAIL PROTECTED]> wrote: > Recall sorted... > sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted > list > > So why not construct sorteddicts using the same idea of sortedness? > > sorteddict((mapping | sequence | nothing), cmp=None, key=None, > re

Re: sorteddict PEP proposal [started off as orderedict]

On 25 Sep, 12:11, Jeremy Sanders wrote: > Mark Summerfield wrote: > > If there is positive feedback I will submit the PEP to the reviewers, > > so if you think it is a good idea please say so. (I'm sure that if you > > _don't_ like it you'll tell me anyway:-) > > It would be nice to have the abili

Re: sorteddict PEP proposal [started off as orderedict]

Recall sorted... sorted(iterable, cmp=None, key=None, reverse=False) --> new sorted list So why not construct sorteddicts using the same idea of sortedness? sorteddict((mapping | sequence | nothing), cmp=None, key=None, reverse=None) Then we can specify the exact behaviour of sorteddicts: it

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield wrote: > If there is positive feedback I will submit the PEP to the reviewers, > so if you think it is a good idea please say so. (I'm sure that if you > _don't_ like it you'll tell me anyway:-) It would be nice to have the ability to use numerical indexes and the key, but I don'

Re: sorteddict PEP proposal [started off as orderedict]

Mark Summerfield <[EMAIL PROTECTED]> wrote: > When handling collections of key-value data, it is often > convenient to access the data in key order. One way to do this is > to use an unsorted data structure (e.g., a Python dict), and then > sort the keys as needed. Another way is

Re: sorteddict PEP proposal [started off as orderedict]

On 2007-09-25, Andrew Durdin wrote: > On 9/25/07, Mark Summerfield <[EMAIL PROTECTED]> wrote: > > Since the sorteddict's data is always kept in key order, indexes > > (integer offsets) into the sorteddict make sense. Five additional > > methods are proposed to take advantage of this: >

Re: sorteddict PEP proposal [started off as orderedict]

On 2007-09-25, Andrew Durdin wrote: > On 9/25/07, Mark Summerfield <[EMAIL PROTECTED]> wrote: > > Since the sorteddict's data is always kept in key order, indexes > > (integer offsets) into the sorteddict make sense. Five additional > > methods are proposed to take advantage of this: >

Re: sorteddict PEP proposal [started off as orderedict]

On 25 Sep, 10:53, "A.T.Hofkamp" <[EMAIL PROTECTED]> wrote: > On 2007-09-25, Mark Summerfield <[EMAIL PROTECTED]> wrote: > > > If there is positive feedback I will submit the PEP to the reviewers, > > so if you think it is a good idea please say so. (I'm sure that if you > > _don't_ like it you'll t

Re: sorteddict PEP proposal [started off as orderedict]

On 9/25/07, Mark Summerfield <[EMAIL PROTECTED]> wrote: > > Since the sorteddict's data is always kept in key order, indexes > (integer offsets) into the sorteddict make sense. Five additional > methods are proposed to take advantage of this: > > key(index : int) -> value > > i

Re: sorteddict PEP proposal [started off as orderedict]

On 2007-09-25, Mark Summerfield <[EMAIL PROTECTED]> wrote: > If there is positive feedback I will submit the PEP to the reviewers, > so if you think it is a good idea please say so. (I'm sure that if you > _don't_ like it you'll tell me anyway:-) I like the idea, ie +1. > This PEP proposes th