Sorted dictionary

Bearophile bearophileHUGS at lycos.com
Thu Jan 21 10:24:25 CET 2010


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 ordered dicts and
sets based on search trees.
I'm thinking about B+ trees to use CPU cache locality better. It can
be fun :-)

Bye,
bearophile



More information about the Python-list mailing list