[Python-checkins] r73367 - python/trunk/Doc/library/bisect.rst

[Raymond Hettinger]

Hello Joop,

To get bisect to work, the underlying list needs to be in sorted order.
The one in your example is not in sorted order because the for-loops
are in opposite order of the joined string (f needs to be first and r second).  
Swapping the two will fix the "oddities" you've observed:

>>> squares = [f + r for f in 'abcdefgh' for r in '12345678']
>>> squares
['a1', 'a2', 'a3', 'a4', 'a5', 'a6', 'a7', 'a8', 'b1', 'b2', 'b3', 'b4', 'b5', 'b6', 'b7', 'b8', 'c1', 'c2', 'c3', 'c4', 'c5', 'c6', 'c7', 'c8', 'd1', 'd2', 'd3', 'd4', 'd5', 'd6', 'd7', 'd8', 'e1', 'e2', 'e3', 'e4', 'e5', 'e6', 'e7', 'e8', 'f1', 'f2', 'f3', 'f4', 'f5', 'f6', 'f7', 'f8', 'g1', 'g2', 'g3', 'g4', 'g5', 'g6', 'g7', 'g8', 'h1', 'h2', 'h3', 'h4', 'h5', 'h6', 'h7', 'h8']
>>> squares.index('e4')
35
>>> bisect_left( squares,'e4')
35

Feel free to email me directly if you have more questions.
No need to cc the checkins list.


Raymond
 


On Jan 19, 2010, at 6:19 AM, joop renes wrote:

> hi raymond,
> i am trying to develop an efficient dropin replacement for dict() in the
> use case: few updates( which are linear in time complexity) and many
> lookups(which can be made of logarithmic time complexity,provided binary
> search is applicable). some experimentation revealed unexpected results
> as the attached example shows. I have developed a class assoc_vector
> that maintains a sorted list of (key,value) tuples, where key "must" be
> an int. 'I would have expected any type with logical comparison
> semantics to work as it does in C++
> Part of the trick is that the insertion_point can be found by
> bisect( __tuples,(key,) ), where __tuples is a private variable that
> holds the standard python list of (key,value) tuples.
> best regards
> joop renes
> <bisect_test.txt>_______________________________________________
> Python-checkins mailing list
> Python-checkins at python.org
> http://mail.python.org/mailman/listinfo/python-checkins