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

Raymond Hettinger raymond.hettinger at gmail.com
Thu Feb 4 22:52:30 CET 2010

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')
>>> bisect_left( squares,'e4')

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


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

More information about the Python-checkins mailing list