Sorted list as an alternative to dictionary for when you only need keys?
Tim Peters
tim.peters at gmail.com
Mon Jul 19 16:53:05 EDT 2004
[Jeff Epler]
> ...
> 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
mailing list