| 1 |
:mod:`!bisect` --- Array bisection algorithm |
| 2 |
============================================ |
| 3 |
|
| 4 |
.. module:: bisect |
| 5 |
:synopsis: Array bisection algorithms for binary searching. |
| 6 |
.. sectionauthor:: Fred L. Drake, Jr. <[email protected]> |
| 7 |
.. sectionauthor:: Raymond Hettinger <python at rcn.com> |
| 8 |
.. example based on the PyModules FAQ entry by Aaron Watters <[email protected]> |
| 9 |
|
| 10 |
**Source code:** :source:`Lib/bisect.py` |
| 11 |
|
| 12 |
-------------- |
| 13 |
|
| 14 |
This module provides support for maintaining a list in sorted order without |
| 15 |
having to sort the list after each insertion. For long lists of items with |
| 16 |
expensive comparison operations, this can be an improvement over |
| 17 |
linear searches or frequent resorting. |
| 18 |
|
| 19 |
The module is called :mod:`!bisect` because it uses a basic bisection |
| 20 |
algorithm to do its work. Unlike other bisection tools that search for a |
| 21 |
specific value, the functions in this module are designed to locate an |
| 22 |
insertion point. Accordingly, the functions never call an :meth:`~object.__eq__` |
| 23 |
method to determine whether a value has been found. Instead, the |
| 24 |
functions only call the :meth:`~object.__lt__` method and will return an insertion |
| 25 |
point between values in an array. |
| 26 |
|
| 27 |
.. note:: |
| 28 |
|
| 29 |
The functions in this module are not thread-safe. If multiple threads |
| 30 |
concurrently use :mod:`!bisect` functions on the same sequence, this |
| 31 |
may result in undefined behaviour. Likewise, if the provided sequence |
| 32 |
is mutated by a different thread while a :mod:`!bisect` function |
| 33 |
is operating on it, the result is undefined. For example, using |
| 34 |
:py:func:`~bisect.insort_left` on the same list from multiple threads |
| 35 |
may result in the list becoming unsorted. |
| 36 |
|
| 37 |
.. _bisect functions: |
| 38 |
|
| 39 |
The following functions are provided: |
| 40 |
|
| 41 |
|
| 42 |
.. function:: bisect_left(a, x, lo=0, hi=len(a), *, key=None) |
| 43 |
|
| 44 |
Locate the insertion point for *x* in *a* to maintain sorted order. |
| 45 |
The parameters *lo* and *hi* may be used to specify a subset of the list |
| 46 |
which should be considered; by default the entire list is used. If *x* is |
| 47 |
already present in *a*, the insertion point will be before (to the left of) |
| 48 |
any existing entries. The return value is suitable for use as the first |
| 49 |
parameter to ``list.insert()`` assuming that *a* is already sorted. |
| 50 |
|
| 51 |
The returned insertion point *ip* partitions the array *a* into two |
| 52 |
slices such that ``all(elem < x for elem in a[lo : ip])`` is true for the |
| 53 |
left slice and ``all(elem >= x for elem in a[ip : hi])`` is true for the |
| 54 |
right slice. |
| 55 |
|
| 56 |
*key* specifies a :term:`key function` of one argument that is used to |
| 57 |
extract a comparison key from each element in the array. To support |
| 58 |
searching complex records, the key function is not applied to the *x* value. |
| 59 |
|
| 60 |
If *key* is ``None``, the elements are compared directly and |
| 61 |
no key function is called. |
| 62 |
|
| 63 |
.. versionchanged:: 3.10 |
| 64 |
Added the *key* parameter. |
| 65 |
|
| 66 |
|
| 67 |
.. function:: bisect_right(a, x, lo=0, hi=len(a), *, key=None) |
| 68 |
bisect(a, x, lo=0, hi=len(a), *, key=None) |
| 69 |
|
| 70 |
Similar to :py:func:`~bisect.bisect_left`, but returns an insertion point which comes |
| 71 |
after (to the right of) any existing entries of *x* in *a*. |
| 72 |
|
| 73 |
The returned insertion point *ip* partitions the array *a* into two slices |
| 74 |
such that ``all(elem <= x for elem in a[lo : ip])`` is true for the left slice and |
| 75 |
``all(elem > x for elem in a[ip : hi])`` is true for the right slice. |
| 76 |
|
| 77 |
.. versionchanged:: 3.10 |
| 78 |
Added the *key* parameter. |
| 79 |
|
| 80 |
|
| 81 |
.. function:: insort_left(a, x, lo=0, hi=len(a), *, key=None) |
| 82 |
|
| 83 |
Insert *x* in *a* in sorted order. |
| 84 |
|
| 85 |
This function first runs :py:func:`~bisect.bisect_left` to locate an insertion point. |
| 86 |
Next, it runs the :meth:`~sequence.insert` method on *a* to insert *x* at the |
| 87 |
appropriate position to maintain sort order. |
| 88 |
|
| 89 |
To support inserting records in a table, the *key* function (if any) is |
| 90 |
applied to *x* for the search step but not for the insertion step. |
| 91 |
|
| 92 |
Keep in mind that the *O*\ (log *n*) search is dominated by the slow *O*\ (*n*) |
| 93 |
insertion step. |
| 94 |
|
| 95 |
.. versionchanged:: 3.10 |
| 96 |
Added the *key* parameter. |
| 97 |
|
| 98 |
|
| 99 |
.. function:: insort_right(a, x, lo=0, hi=len(a), *, key=None) |
| 100 |
insort(a, x, lo=0, hi=len(a), *, key=None) |
| 101 |
|
| 102 |
Similar to :py:func:`~bisect.insort_left`, but inserting *x* in *a* after any existing |
| 103 |
entries of *x*. |
| 104 |
|
| 105 |
This function first runs :py:func:`~bisect.bisect_right` to locate an insertion point. |
| 106 |
Next, it runs the :meth:`~sequence.insert` method on *a* to insert *x* at the |
| 107 |
appropriate position to maintain sort order. |
| 108 |
|
| 109 |
To support inserting records in a table, the *key* function (if any) is |
| 110 |
applied to *x* for the search step but not for the insertion step. |
| 111 |
|
| 112 |
Keep in mind that the *O*\ (log *n*) search is dominated by the slow *O*\ (*n*) |
| 113 |
insertion step. |
| 114 |
|
| 115 |
.. versionchanged:: 3.10 |
| 116 |
Added the *key* parameter. |
| 117 |
|
| 118 |
|
| 119 |
Performance Notes |
| 120 |
----------------- |
| 121 |
|
| 122 |
When writing time sensitive code using *bisect()* and *insort()*, keep these |
| 123 |
thoughts in mind: |
| 124 |
|
| 125 |
* Bisection is effective for searching ranges of values. |
| 126 |
For locating specific values, dictionaries are more performant. |
| 127 |
|
| 128 |
* The *insort()* functions are *O*\ (*n*) because the logarithmic search step |
| 129 |
is dominated by the linear time insertion step. |
| 130 |
|
| 131 |
* The search functions are stateless and discard key function results after |
| 132 |
they are used. Consequently, if the search functions are used in a loop, |
| 133 |
the key function may be called again and again on the same array elements. |
| 134 |
If the key function isn't fast, consider wrapping it with |
| 135 |
:py:func:`functools.cache` to avoid duplicate computations. Alternatively, |
| 136 |
consider searching an array of precomputed keys to locate the insertion |
| 137 |
point (as shown in the examples section below). |
| 138 |
|
| 139 |
.. seealso:: |
| 140 |
|
| 141 |
* `Sorted Collections |
| 142 |
<https://grantjenks.com/docs/sortedcollections/>`_ is a high performance |
| 143 |
module that uses *bisect* to managed sorted collections of data. |
| 144 |
|
| 145 |
* The `SortedCollection recipe |
| 146 |
<https://code.activestate.com/recipes/577197-sortedcollection/>`_ uses |
| 147 |
bisect to build a full-featured collection class with straight-forward search |
| 148 |
methods and support for a key-function. The keys are precomputed to save |
| 149 |
unnecessary calls to the key function during searches. |
| 150 |
|
| 151 |
|
| 152 |
Searching Sorted Lists |
| 153 |
---------------------- |
| 154 |
|
| 155 |
The above `bisect functions`_ are useful for finding insertion points but |
| 156 |
can be tricky or awkward to use for common searching tasks. The following five |
| 157 |
functions show how to transform them into the standard lookups for sorted |
| 158 |
lists:: |
| 159 |
|
| 160 |
def index(a, x): |
| 161 |
'Locate the leftmost value exactly equal to x' |
| 162 |
i = bisect_left(a, x) |
| 163 |
if i != len(a) and a[i] == x: |
| 164 |
return i |
| 165 |
raise ValueError |
| 166 |
|
| 167 |
def find_lt(a, x): |
| 168 |
'Find rightmost value less than x' |
| 169 |
i = bisect_left(a, x) |
| 170 |
if i: |
| 171 |
return a[i-1] |
| 172 |
raise ValueError |
| 173 |
|
| 174 |
def find_le(a, x): |
| 175 |
'Find rightmost value less than or equal to x' |
| 176 |
i = bisect_right(a, x) |
| 177 |
if i: |
| 178 |
return a[i-1] |
| 179 |
raise ValueError |
| 180 |
|
| 181 |
def find_gt(a, x): |
| 182 |
'Find leftmost value greater than x' |
| 183 |
i = bisect_right(a, x) |
| 184 |
if i != len(a): |
| 185 |
return a[i] |
| 186 |
raise ValueError |
| 187 |
|
| 188 |
def find_ge(a, x): |
| 189 |
'Find leftmost item greater than or equal to x' |
| 190 |
i = bisect_left(a, x) |
| 191 |
if i != len(a): |
| 192 |
return a[i] |
| 193 |
raise ValueError |
| 194 |
|
| 195 |
|
| 196 |
Examples |
| 197 |
-------- |
| 198 |
|
| 199 |
.. _bisect-example: |
| 200 |
|
| 201 |
The :py:func:`~bisect.bisect` function can be useful for numeric table lookups. This |
| 202 |
example uses :py:func:`~bisect.bisect` to look up a letter grade for an exam score (say) |
| 203 |
based on a set of ordered numeric breakpoints: 90 and up is an 'A', 80 to 89 is |
| 204 |
a 'B', and so on:: |
| 205 |
|
| 206 |
>>> def grade(score): |
| 207 |
... i = bisect([60, 70, 80, 90], score) |
| 208 |
... return "FDCBA"[i] |
| 209 |
... |
| 210 |
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]] |
| 211 |
['F', 'A', 'C', 'C', 'B', 'A', 'A'] |
| 212 |
|
| 213 |
The :py:func:`~bisect.bisect` and :py:func:`~bisect.insort` functions also work with |
| 214 |
lists of tuples. The *key* argument can serve to extract the field used for ordering |
| 215 |
records in a table:: |
| 216 |
|
| 217 |
>>> from collections import namedtuple |
| 218 |
>>> from operator import attrgetter |
| 219 |
>>> from bisect import bisect, insort |
| 220 |
>>> from pprint import pprint |
| 221 |
|
| 222 |
>>> Movie = namedtuple('Movie', ('name', 'released', 'director')) |
| 223 |
|
| 224 |
>>> movies = [ |
| 225 |
... Movie('Jaws', 1975, 'Spielberg'), |
| 226 |
... Movie('Titanic', 1997, 'Cameron'), |
| 227 |
... Movie('The Birds', 1963, 'Hitchcock'), |
| 228 |
... Movie('Aliens', 1986, 'Cameron') |
| 229 |
... ] |
| 230 |
|
| 231 |
>>> # Find the first movie released after 1960 |
| 232 |
>>> by_year = attrgetter('released') |
| 233 |
>>> movies.sort(key=by_year) |
| 234 |
>>> movies[bisect(movies, 1960, key=by_year)] |
| 235 |
Movie(name='The Birds', released=1963, director='Hitchcock') |
| 236 |
|
| 237 |
>>> # Insert a movie while maintaining sort order |
| 238 |
>>> romance = Movie('Love Story', 1970, 'Hiller') |
| 239 |
>>> insort(movies, romance, key=by_year) |
| 240 |
>>> pprint(movies) |
| 241 |
[Movie(name='The Birds', released=1963, director='Hitchcock'), |
| 242 |
Movie(name='Love Story', released=1970, director='Hiller'), |
| 243 |
Movie(name='Jaws', released=1975, director='Spielberg'), |
| 244 |
Movie(name='Aliens', released=1986, director='Cameron'), |
| 245 |
Movie(name='Titanic', released=1997, director='Cameron')] |
| 246 |
|
| 247 |
If the key function is expensive, it is possible to avoid repeated function |
| 248 |
calls by searching a list of precomputed keys to find the index of a record:: |
| 249 |
|
| 250 |
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)] |
| 251 |
>>> data.sort(key=lambda r: r[1]) # Or use operator.itemgetter(1). |
| 252 |
>>> keys = [r[1] for r in data] # Precompute a list of keys. |
| 253 |
>>> data[bisect_left(keys, 0)] |
| 254 |
('black', 0) |
| 255 |
>>> data[bisect_left(keys, 1)] |
| 256 |
('blue', 1) |
| 257 |
>>> data[bisect_left(keys, 5)] |
| 258 |
('red', 5) |
| 259 |
>>> data[bisect_left(keys, 8)] |
| 260 |
('yellow', 8) |