[EMAIL PROTECTED] wrote: > I have found that in certain situations ordered dicts are useful. I use > an Odict class written in Python by ROwen that I have improved and > updated some for personal use. > > So I'm thinking about a possible C version of Odict (maybe fit for the > collections module). > > On a 32 bit Win Python 2.5 requires about: > 28.2 bytes/element for set(int) > 36.2 bytes/element for dict(int:None) > > Deleted keys from a dict/set aren't removed, they are tagged as > deleted. > My experience of CPython sources is tiny, I have just read few parts, > so a person much more expert than me can comment the following lines. > > During the printing of the set/dict I think such flags are just read > and skipped one after the other. > > So I think to keep the insertion order of the keys a simple chained > list is enough, each inserted key has a pointer to the successive one > (even deleted keys). So theoretically an Odict of (int:None) can > require just 40.2 bytes/element :-) (Python Odicts require much more > memory, because they ). > (I don't know if some extra memory for the garbage collector is > necessary, I don't think so.) > > The simple linked list has to be managed (tail insertions only), and > scanned from the listHead inside iterating methods like iteritems, > items, values, etc. > > If such solution is possibile, then how much difficult is such > implementation?
FYI there was a *long* discussion around the need for Speed sprint about implementing ordered dicts. As the discussion started by your thread has started to reveal, everyone has just-ever-so-slightly-different requirements. IIRC the goal was dropped because it wasn't possible to agree on a specification. regards Steve -- Steve Holden +44 150 684 7255 +1 800 494 3119 Holden Web LLC/Ltd http://www.holdenweb.com Skype: holdenweb http://holdenweb.blogspot.com Recent Ramblings http://del.icio.us/steve.holden -- http://mail.python.org/mailman/listinfo/python-list
