Debian Codegraph @

Doc/library/bisect.rst

raw
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)