Sorted list as an alternative to dictionary for when you only need keys?
tim.peters at gmail.com
Mon Jul 19 22:53:05 CEST 2004
> Python 2.2 and above also have a "bisect" module which can be used for O(lg n)
> insertions, deletions, and searches for items in sorted lists, but
> there's not a simple OO interface for it.
The bisect module is much older than 2.2 (I can't remember a time when
Python didn't have it), but insertion and deletion are O(n), only
lookup is O(log n) with bisect. Expected time is O(1) for insertion,
deletion, and lookup with a dict. Sets are the same as dicts.
More information about the Python-list