Hướng dẫn bisect python
Source code: Lib/bisect.py This module provides support for maintaining a list in sorted order without having to sort the list after each insertion. For long lists of items with expensive comparison operations, this can be an improvement over the more common approach. The module is called The following functions are provided: Locate the insertion point for x in a to maintain sorted order. The parameters lo and hi may be used to specify a subset of the list which should be considered; by
default the entire list is used. If x is already present in a, the insertion point will be before (to the left of) any existing entries. The return value is suitable for use as the first parameter to The returned insertion point i partitions the array a into two halves so that key specifies a key function of one argument that is used to extract a comparison key from
each element in the array. To support searching complex records, the key function is not applied to the x value. If key is Changed in version 3.10: Added the key parameter. Similar to The returned insertion point i partitions the array a into two halves so
that key specifies a key function of one argument that is used to extract a comparison key from each element in the array. To support searching complex records, the key function is not applied to the x value. If key is Changed in version 3.10: Added the key parameter. bisect. insort_left (a, x, lo=0, hi=len(a), *, key=None)¶Insert x in a in sorted order. This function first runs To support inserting records in a table, the key function (if any) is applied to x for the search step but not for the insertion step. Keep in mind that the Changed in version 3.10: Added the key parameter. bisect. insort_right (a, x, lo=0, hi=len(a), *,
key=None)¶ bisect. insort (a, x, lo=0, hi=len(a), *, key=None)¶Similar to This function first runs To support inserting records in a table, the key function (if any) is applied to x for the search step but not for the insertion step. Keep in mind that the Changed in version 3.10: Added the key parameter. Performance Notes¶When writing time sensitive code using bisect() and insort(), keep these thoughts in mind:
See also
Searching Sorted Lists¶The above def index(a, x): 'Locate the leftmost value exactly equal to x' i = bisect_left(a, x) if i != len(a) and a[i] == x: return i raise ValueError def find_lt(a, x): 'Find rightmost value less than x' i = bisect_left(a, x) if i: return a[i-1] raise ValueError def find_le(a, x): 'Find rightmost value less than or equal to x' i = bisect_right(a, x) if i: return a[i-1] raise ValueError def find_gt(a, x): 'Find leftmost value greater than x' i = bisect_right(a, x) if i != len(a): return a[i] raise ValueError def find_ge(a, x): 'Find leftmost item greater than or equal to x' i = bisect_left(a, x) if i != len(a): return a[i] raise ValueError Examples¶The >>> 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'] The >>> from collections import namedtuple >>> from operator import attrgetter >>> from bisect import bisect, insort >>> from pprint import pprint >>> Movie = namedtuple('Movie', ('name', 'released', 'director')) >>> movies = [ ... Movie('Jaws', 1975, 'Speilberg'), ... Movie('Titanic', 1997, 'Cameron'), ... Movie('The Birds', 1963, 'Hitchcock'), ... Movie('Aliens', 1986, 'Scott') ... ] >>> # Find the first movie released after 1960 >>> by_year = attrgetter('released') >>> movies.sort(key=by_year) >>> movies[bisect(movies, 1960, key=by_year)] Movie(name='The Birds', released=1963, director='Hitchcock') >>> # Insert a movie while maintaining sort order >>> romance = Movie('Love Story', 1970, 'Hiller') >>> insort(movies, romance, key=by_year) >>> pprint(movies) [Movie(name='The Birds', released=1963, director='Hitchcock'), Movie(name='Love Story', released=1970, director='Hiller'), Movie(name='Jaws', released=1975, director='Speilberg'), Movie(name='Aliens', released=1986, director='Scott'), Movie(name='Titanic', released=1997, director='Cameron')] If the key function is expensive, it is possible to avoid repeated function calls by searching a list of precomputed keys to find the index of a record: >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)] >>> data.sort(key=lambda r: r[1]) # Or use operator.itemgetter(1). >>> keys = [r[1] for r in data] # Precompute a 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) |