Re: Proposed implementation for an Ordered Dictionary

Michele Simionato wrote: On Mar 1, 1:43 am, Paul Rubin wrote: "Colin J. Williams" writes: # print [mydict[x] for x in sorted(mydict.keys)] Instance object is not iterable It was a typo. Use: print [mydict[x] for x in sorted(mydict.keys())] Even bet

Re: Proposed implementation for an Ordered Dictionary

On Mar 1, 1:43 am, Paul Rubin wrote: > "Colin J. Williams" writes: > > >      # print [mydict[x] for x in sorted(mydict.keys)] Instance object > > is not iterable > > It was a typo.  Use: > >     print [mydict[x] for x in sorted(mydict.keys())] Even better print [m

Re: Proposed implementation for an Ordered Dictionary

"Colin J. Williams" writes: > # print [mydict[x] for x in sorted(mydict.keys)] Instance object > is not iterable It was a typo. Use: print [mydict[x] for x in sorted(mydict.keys())] -- http://mail.python.org/mailman/listinfo/python-list

Re: Proposed implementation for an Ordered Dictionary

Steven D'Aprano wrote: Colin J. Williams wrote: Sometimes, it's useful to be able to obtain the data in the sorted sequence. You might consider adding functionality like: def seqItems(self): '''To return the items, sorted by key. ''' return [self[k] for k in self.seqKeys()] Amazingly, the P

Re: Proposed implementation for an Ordered Dictionary

Colin J. Williams wrote: > Sometimes, it's useful to be able to > obtain the data in the sorted sequence. > > You might consider adding functionality > like: > > def seqItems(self): > '''To return the items, sorted > by key. ''' > return [self[k] for k in > self.seqKeys()] Amazingly, the Python

Re: Proposed implementation for an Ordered Dictionary

Raymond Hettinger wrote: [Paul Rubin] Ehh, I guess I'm not surprised at the slowdown and extra complexity from the second dict. Oh well. If the module really turns out to be really used a lot, another (messy) approach would be to write a C extension that uses a doubly linked list some day. T

Re: Proposed implementation for an Ordered Dictionary

>> A sort of premature pessimization, then. QOTW! +1 Malcolm -- http://mail.python.org/mailman/listinfo/python-list

Re: Proposed implementation for an Ordered Dictionary

[Steve Holden] > A sort of premature pessimization, then. QOTW! _ ~ @ @ \_/ Raymond -- http://mail.python.org/mailman/listinfo/python-list

Re: Proposed implementation for an Ordered Dictionary

Steve Holden: > A sort of premature pessimization, then. Maybe not, the save in memory may lead to higher speed anyway. So you need to test it to know the overall balance. And in data structures with general purpose you want all the speed you can get. Bye, bearophile -- http://mail.python.org/mai

Re: Proposed implementation for an Ordered Dictionary

bearophileh...@lycos.com wrote: > Paul Rubin: >> I don't see how to delete a randomly chosen node if you use that trick, >> since the hash lookup doesn't give you two consecutive nodes in the linked >> list to xor together.< > > Thank you, I think you are right, I am sorry. > So on 32-bit CPUs y

Re: Proposed implementation for an Ordered Dictionary

Paul Rubin: >I don't see how to delete a randomly chosen node if you use that trick, since >the hash lookup doesn't give you two consecutive nodes in the linked list to >xor together.< Thank you, I think you are right, I am sorry. So on 32-bit CPUs you need to add 8 bytes to each value. On 64-b

Re: Proposed implementation for an Ordered Dictionary

bearophileh...@lycos.com writes: > So using the XOR (or subtraction) trick to use only 1 pointer for > each key-value may be useful to keep performance not too much far > from the normal python dicts: http://en.wikipedia.org/wiki/XOR_linked_list I don't see how to delete a randomly chosen node if

Re: Proposed implementation for an Ordered Dictionary

Raymond Hettinger: >Paul Rubin: >>another (messy) approach would be to write a C >>extension that uses a doubly linked list some day. > > That seems like an ideal implementation to me. This was my Python implementation, where the delete too is O(1), but it's slow: http://code.activestate.com/recip

Re: Proposed implementation for an Ordered Dictionary

[Paul Rubin] > Ehh, I guess I'm not surprised at the slowdown and extra complexity > from the second dict.  Oh well.  If the module really turns out to be > really used a lot, another (messy) approach would be to write a C > extension that uses a doubly linked list some day. That seems like an ide

Re: Proposed implementation for an Ordered Dictionary

Raymond Hettinger writes: > > What about using a second dictionary > My first attempt used exactly that approach and it works fine > though it does complicate the code quite a bit and slows down > all of the common operations by a constant factor. Ehh, I guess I'm not surprised at the slowdown a

Re: Proposed implementation for an Ordered Dictionary

> > What about using a second dictionary (indexed by the incrementing > > counter) instead of a list to record the insertion order?  Then you > > have O(1) deletion, and traversal takes an O(n log n) sorting > > operation. > My first attempt used exactly that approach and it works fine > though it

Re: Proposed implementation for an Ordered Dictionary

[Paul Rubin] > What about using a second dictionary (indexed by the incrementing > counter) instead of a list to record the insertion order?  Then you > have O(1) deletion, and traversal takes an O(n log n) sorting > operation. My first attempt used exactly that approach and it works fine though i

Re: Proposed implementation for an Ordered Dictionary

Raymond Hettinger writes: > I don't see any fast/clean way. It's possible to tracking pending > deletions and do them all at once but that's a bit messy and slow. What about using a second dictionary (indexed by the incrementing counter) instead of a list to record the insertion order? Then you

Re: Proposed implementation for an Ordered Dictionary

[Hrvoje Niksic] > It seems that __delitem__ of an existing key is O(n), whereas it's > amortized constant time for dicts.  (__setitem__ is constant time for > both.)  Is there a way to avoid this? I don't see any fast/clean way. It's possible to tracking pending deletions and do them all at once

Re: Proposed implementation for an Ordered Dictionary

[Benjamin Peterson] > Why not just inherit from collections.MutableMapping? It makes the recipe shorter to inherit some methods from dict. Also, subclassing from dict gives a speedup for __getitem__(), __len__(), and get(). -- http://mail.python.org/mailman/listinfo/python-list

Re: Proposed implementation for an Ordered Dictionary

Raymond Hettinger writes: > Here's a proposed implementation for Py2.7 and Py3.1: > > http://code.activestate.com/recipes/576669/ Several methods like __contains__() and __getitem__() are not overridden, so their performance is just as fast as a regular dictionary. Methods l

Re: Proposed implementation for an Ordered Dictionary

Raymond Hettinger rcn.com> writes: > > Here's a proposed implementation for Py2.7 and Py3.1: > > http://code.activestate.com/recipes/576669/ > > Would like you guys to kick the tires, exercise it a bit, and let me > know what you think. The recipe runs under 2.6 and 3.0 without > modifica

Proposed implementation for an Ordered Dictionary

Here's a proposed implementation for Py2.7 and Py3.1: http://code.activestate.com/recipes/576669/ Would like you guys to kick the tires, exercise it a bit, and let me know what you think. The recipe runs under 2.6 and 3.0 without modification so it should be easy to play with. The main virt