Sorted list as an alternative to dictionary for when youonly need keys?

[Scott David Daniels]

Daniel Eloff wrote:
[about ordered list and bisect vs. dict- or set- based sets]
> Sad that sets are really just dicts. But why is only lookup O(log n) ?
> Insertion is just lookup + list.insert(). 
Insert at an arbitrary point is O(N).  append may be less, but insert
is stuck with worst case at-front, and average case in-middle.  These
take respectively len(list) and line(list/2) time just to do the tail
copy, and both of those are O(N).

> Similar for removing elements.
Indeed, the similarity has to do with the compact-back cost.

> All bisect should be doing is taking len() and dividing it by two ( //
> for integer divide). That's the mid point, you can then compare the
> element at that index with the key to see if it's place above or below
> and you continue almost recursively dividing that subset of the list in
> half via index calculations and comparing elements. I don't think that
> could be very slow, even in python.
Slow enough, because you are looking at a fairly high multiplier for
the per look.  Say you could manage to do a loop, divide, compare,
resubstitute in 10 operations.  You need a fairly big set before a
comparison-increment pair that blasts down the list is better.  Less
if the cost of a compare is high, but remember with bisect you have to
do two comparisons about half the time (to check for equal as well as
which side).  So even with very tight loops, you probably need a list
of length eight to do better than break even.

The dictionary prunes far more than bisect can -- it depends on hash
bins, and the odds are you go from hash to match-mismatch almost aways.
There is a theoretical argument that says the cost is still log N (the
address grows the more you have in the dictionary), but Python avoids
that hassle by crashing when you exceed you virtual address space.

-Scott David Daniels
Scott.Daniels at Acm.Org