Raymond Hettinger python at rcn.com
Fri Sep 6 08:40:37 EDT 2002

Hello Issac,

Try looking at seqdict in the Vaults of Parnassus:

Also, I think there may be a sorted dictionary implementation in the Python

Your other ideas were good too.  The auxilliary map of
successors and precessors is likely to be the fastest.
To efficiently update a sorted python list, try the bisect module.

Raymond Hettinger

"Isaac To" <kkto at csis.hku.hk> wrote in message
news:7ir8g7xqqk.fsf at enark.csis.hku.hk...
> Hi,
> Some time ago I want to have a dictionary-like type that can support
> dictionary operation, plus that given any key, I want to know the
> predecessor and successor of any given key efficiently.  I've thought of
> using a Python list, but it is impossible to update quickly.  The closest
> thing I can think of is an auxillary map that implements the successor and
> predecessor functionalities.  But I'm wondering there is anything better.
> After all, Python dictionaries are implemented by height balancing tree,
> internally the needed data can be retrieved efficiently.  Any hint?
> Regards,
> Isaac.

More information about the Python-list mailing list