The bisect module maintains an ordered list

bisect – Maintain an ordered list

Purpose: There is no need to call sort every time to maintain an ordered list.

The bisect module implements an algorithm for inserting elements into an ordered list. In some cases, this is more efficient than sorting the list repeatedly or constructing a large list and then sorting it. Bisect means dichotomy. The bisection method is used here to sort. The source code of bisect is a template for bisection sorting. This module has less than 100 lines of code.

Insert

import bisect
import random
   
# Use aconstant seed to ensure that
# the samepseudo-random numbers
# are usedeach time the loop is run.
random.seed(1)
   
print'New  Pos Contents'
print'---  --- --------'
   
# Generaterandom numbers and
# insert theminto a list in sorted
# order.
l = []
for i inrange(1, 15):
#产生1-100的随机数
    r = random.randint(1, 100)
    position = bisect.bisect(l, r)
    bisect.insort(l, r)
print'%3d  %3d' % (r, position), l

Execution result:

#./bisect_example.py

New Pos Contents

--- -----------

14 0[14]

85 1[ 14, 85]

77 1[14, 77, 85]

26 1[14, 26, 77, 85]

50 2[14, 26, 50, 77, 85]

45 2[14, 26, 45, 50, 77, 85]

66 4[14, 26, 45, 50, 66, 77, 85]

79 6[14, 26, 45, 50, 66, 77, 79, 85]

10 0[10, 14, 26, 45, 50, 66, 77, 79, 85]

3 0[3, 10, 14, 26, 45, 50, 66, 77, 79, 85]

84 9[3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]

44 4[3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]

77 9[3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

1 0[1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]

The functions provided by the Bisect module are:

bisect.bisect_left(a,x, lo=0, hi=len(a) ):

Find the index of inserting x in the ordered list a. lo and hi are used to specify the range of the list, and the default is to use the entire list. If x already exists, insert it to the left. The return value is index.

bisect.bisect_right(a,x, lo=0, hi=len(a))

bisect.bisect(a, x,lo=0, hi=len(a))

These two are similar to bisect_left , but if x already exists, insert it to the right.

bisect.insort_left(a,x, lo=0, hi=len(a))

Insert x into the ordered list a. The effect is the same as a.insert(bisect.bisect_left(a,x, lo, hi), x).

bisect.insort_right(a,x, lo=0, hi=len(a))

bisect.insort(a, x,lo=0, hi=len(a))

Similar to insort_left, but if x already exists, insert it to its right.

Functions can be divided into 2 categories, bisect*, which is used to find index. Insort* is used for actual insertion. By default, repeats are inserted from the right. The most commonly used one is probably insort.

There is an example of calculating grades based on scores in the standard:

>>> def grade(score,breakpoints=[60, 70, 80, 90], grades='FDCBA'):

... i = bisect(breakpoints, score)

... return grades[i]

...

>>> [grade(score)for score in [33, 99, 77, 70, 89, 90, 100]]

['F', 'A', 'C','C', 'B', 'A', 'A']

Bisect does not support keyword parameters like sort. It is recommended to handle it as follows:

>>> data =[('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
>>> data.sort(key=lambdar: r[1])
>>> keys =[r[1] for r in data]         #precomputed list of keys
>>> 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)