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

[joop renes]

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
-------------- next part --------------
joop at joop-desktop:~$ python
Python 2.6.4 (r264:75706, Dec  7 2009, 18:43:55) 
[GCC 4.4.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from bisect import *
>>> squares = [f + r for r in '12345678' for f in 'abcdefgh']
>>> squares
['a1', 'b1', 'c1', 'd1', 'e1', 'f1', 'g1', 'h1', 'a2', 'b2', 'c2', 'd2', 'e2', 'f2', 'g2', 'h2', 'a3', 'b3', 'c3', 'd3', 'e3', 'f3', 'g3', 'h3', 'a4', 'b4', 'c4', 'd4', 'e4', 'f4', 'g4', 'h4', 'a5', 'b5', 'c5', 'd5', 'e5', 'f5', 'g5', 'h5', 'a6', 'b6', 'c6', 'd6', 'e6', 'f6', 'g6', 'h6', 'a7', 'b7', 'c7', 'd7', 'e7', 'f7', 'g7', 'h7', 'a8', 'b8', 'c8', 'd8', 'e8', 'f8', 'g8', 'h8']
>>> squares.index('e4')
28
>>> squares[28]
'e4'
>>> bisect_left( squares,'e4')
60
>>> 
joop at joop-desktop:~$