PEP 372 -- Adding an ordered directory to collections

bearophileHUGS at bearophileHUGS at
Thu Jun 19 00:15:35 CEST 2008

> Why keep the normal dict operations at the same speed? There is a
> substantial cost this entails.

I presume now we can create a list of possible odict usages, because I
think that despite everyone using it for different purposes, we may
find some main groups of its usage. I use odicts is situations where
an dict is nearly the right data structure, so keeping all operations
close to the time complexity of dicts has a purpose.

> but the storage requirements are reduced to 2n from 4n.

In Python 2.5 a dict(int:None) needs about 36.2 bytes/element. I am
suggesting to add 2 pointers, to create a linked list, so it probably
becomes (on 32 bit systems) about 44.2 bytes/pair.

Note that computer science is full of strange data structures, so
maybe a skip list can be used here, to increase some operation
timings, and reduce other ones... :-)


More information about the Python-list mailing list