Talk about Python’s Bisect module

The BISect module contains two main functions (BISect and Insort), which internally utilize binary lookup algorithms for finding and inserting elements in ordered sequences, respectively.

Bisect/ba ɪ ˈ sekt /

We are divided into two equal parts. halving

1 bisect function

Luciano Ramalho gives an example of looking for a needle in a haystack to illustrate how to use bisect.bisect and bisect.bisect_left.

HAYSTACK = [1, 4, 5, 6, 8, 12, 15, 20, 21, 23, 23, 26, 29, 30]
NEEDLES = [0, 1, 2, 5, 8, 10, 22, 23, 29, 30, 31]

ROW_FMT = '{0:2d} @ {1:2d}    {2}{0:<2d}'


def demo(bisect_fn):
    for needle in reversed(NEEDLES):
        position = bisect_fn(HAYSTACK, needle)
        offset = position * '  |'
        print(ROW_FMT.format(needle, position, offset))


if __name__ == '__main__':

    if sys.argv[-1] == 'left':
        bisect_fn = bisect.bisect_left
    else:
        bisect_fn = bisect.bisect

    print('DEMO:', bisect_fn.__name__)
    print('haystack ->', ' '.join('%2d' % n for n in HAYSTACK))
    demo(bisect_fn)
Copy the code

Running results:

DEMO: bisect_right haystack -> 1 4 5 6 8 12 15 20 21 23 23 26 29 30 31 @ 14 | | | | | | | | | | | | | |31 30 @ 14 | | | | | | | | | | | | | | 30 29 @ 13 | | | | | | | | | | | | | 29 23 @ 11 | | | | | | | | | | | 22 23 @ 9 | | | | | | | | | 22 10 @ 5 | | | | | 10 8 @ 5 | | | | | 8 5 @ 3 | | | @ @ 1 | 1 | 2 2 5 @ 1 0 0 0Copy the code

One feature of Python functions is that they can take the function name as an input parameter, such as bisect_fn in the example. This makes functions more flexible and allows them to be dynamically loaded with function names as program run parameters.

HAYSTACK is a HAYSTACK. NEEDLES are NEEDLES. Looking for a needle in a haystack is essentially looking for a number in an ordered sequence.

A custom demo(bisect_fn) function that first evaluates position, then uses the position to calculate how many delimiters are required to print offsets, and finally prints them in the defined format.

Str.format () is used to format strings, which can specify argument positions. In syntax like {0:2d}, 0 represents the first input argument, :2d represents the total length, and space is used as a placeholder if it is insufficient. D represents a signed integer in decimal.

Alignment can also be set in the str.format() format. ^, <, and > are centered, left, and right, respectively. So {0:<2d} represents the left-aligned, two-digit decimal signed integer of the first entry.

__name__ is a python built-in class attribute that exists in a Python program and represents the program name. If it is the main thread, its built-in name is __main__.

If you run the program with the left argument, the bisect_left function is called inside the program’s custom functions. The bisect function is actually an alias for the bisect_right function.

The difference between the bisect_left function and the bisect function is:

1. The bisect_left function returns the position of the element in the original sequence that is equal to the inserted element. If a new element is inserted, the new element is placed before its equal element.

2. The bisect function returns the position of the element equal to the inserted element in the original sequence. If a new element is inserted, the new element is placed after its equal element.

Result of bisect_left function:

DEMO: bisect_left haystack -> 1 4 5 6 8 12 15 20 21 23 23 26 29 30 31 @ 14 | | | | | | | | | | | | | |31 30 @ 13 | | | | | | | 30 29 @ 12 | | | | | | | | | | | | | | | | | | 29 23 @ 9 | | | | | | | | | 22 23 @ 9 | | | | | | | | | 22 10 @ 5 | | | | | 10 8 @ 4 | | | | 8 5 @ 2 | | 5 @ | 1 2 1 @ @ 1 0 0 0 0Copy the code

The Python documentation also includes an example program that uses the bisect function to output test scores:

def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    i = bisect.bisect(breakpoints, score)
    return grades[i]

if __name__ == '__main__':
  results = [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
    logging.info('results -> %s', results)
Copy the code

Running results:

INFO - results -> ['F', 'A', 'C', 'C', 'B', 'A', 'A']
Copy the code

The custom grade() defines three parameters:

The grades () function first finds the position of the incoming grades through the bisect() function and then passes that position into the grades sequence to get the score.

In the main thread, the sequence representing students’ scores is iterated through the for in syntax, and the scores are passed into the grade() function to calculate the scores. Finally, the scores are output once through the sequence.

2 insort function

Because sorting is a time-consuming task, it is best for an ordered sequence to remain ordered when a new element is added. The insort function ensures that the sequence is always in order when inserting.

    SIZE=10
    my_list=[]
    for i in range(SIZE):
        new_item=random.randrange(SIZE*3)
        bisect.insort(my_list,new_item)
        print('%2d -> '% new_item,my_list)
Copy the code

Running results:

8 - > 18 - > [18] [18] 8, 21 - > [8, 18, 21] 5 - > [5, 8, 18, 21] 19 - > [5, 8, 18, 19, 21] 13 - > [5, 8, 13, 18, 19, 21] 20 - > [5, 8, 13, 18, 19, 20, 21] 4 - > [4, 5, 8, 13, 18, 19, 20, 21] 15 - > [4, 5, 8, 13, 15, 18, 19, 20, 21] 2 -> [2, 4, 5, 8, 13, 15, 18, 19, 20, 21]Copy the code

Randrange () returns random numbers within the given input parameter range, but does not include boundary values.

You can see that the sequence remains in order every time you insert it.

Print (‘%2d -> ‘% new_item,my_list) uses %s formatting syntax. %2d defines the format of the new_item value, and my_list automatically hangs after the format. So there are no parentheses after the second percent sign, enclosing the parameters that need to be formatted.

Insort also has a sibling called insort_left, which uses bisect_left at the bottom. The insort_left function places the new element in front of its equal element.

In addition, bisect and Insort both have two optional arguments (LO and hi) to narrow down the sequence to be searched. The default value for lo is 0, and the default value for hi is the length of the sequence.