Author: raymond.hettinger Date: Fri Jun 12 00:04:00 2009 New Revision: 73367 Log: Add example of how to do key lookups with bisect(). Modified: python/trunk/Doc/library/bisect.rst Modified: python/trunk/Doc/library/bisect.rst ============================================================================== --- python/trunk/Doc/library/bisect.rst (original) +++ python/trunk/Doc/library/bisect.rst Fri Jun 12 00:04:00 2009 @@ -85,4 +85,22 @@ >>> map(grade, [33, 99, 77, 44, 12, 88]) ['E', 'A', 'B', 'D', 'F', 'A'] +Unlike the :func:`sorted` function, it does not make sense for the :func:`bisect` +functions to have *key* or *reversed* arguments because that would lead to an +inefficent design (successive calls to bisect functions would not "remember" +all of the previous key lookups). +Instead, it is better to search a list of precomputed keys to find the index +of the record in question:: + + >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)] + >>> data.sort(key=lambda r: r[1]) # precomputed list of keys + >>> keys = [r[1] for r in data] + >>> data[bisect_left(keys, 0)] + ('black', 0) + >>> data[bisect_left(keys, 1)] + ('blue', 1) + >>> data[bisect_left(keys, 5)] + ('red', 5) + >>> data[bisect_left(keys, 8)] + ('yellow', 8)
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
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@python.org http://mail.python.org/mailman/listinfo/python-checkins
participants (3)
-
joop renes -
Raymond Hettinger -
raymond.hettinger