8000 gh-91966 Document where key functions are applied in the bisect modul… · python/cpython@b162f08 · GitHub
[go: up one dir, main page]

Skip to content
< 8000 header class="HeaderMktg header-logged-out js-details-container js-header Details f4 py-3" role="banner" data-is-top="true" data-color-mode=light data-light-theme=light data-dark-theme=dark>

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit b162f08

Browse files
gh-91966 Document where key functions are applied in the bisect module (GH-92602) (#92667)
1 parent 5135b6e commit b162f08

File tree

1 file changed

+52
-15
lines changed

1 file changed

+52
-15
lines changed

Doc/library/bisect.rst

Lines changed: 52 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -35,8 +35,11 @@ The following functions are provided:
3535
``all(val >= x for val in a[i : hi])`` for the right side.
3636

3737
*key* specifies a :term:`key function` of one argument that is used to
38-
extract a comparison key from each input element. The default value is
39-
``None`` (compare the elements directly).
38+
extract a comparison key from each element in the array. To support
39+
searching complex records, the key function is not applied to the *x* value.
40+
41+
If *key* is ``None``, the elements are compared directly with no
42+
intervening function call.
4043

4144
.. versionchanged:: 3.10
4245
Added the *key* parameter.
@@ -53,8 +56,11 @@ The following functions are provided:
5356
``all(val > x for val in a[i : hi])`` for the right side.
5457

5558
*key* specifies a :term:`key function` of one argument that is used to
56-
extract a comparison key from each input element. The default value is
57-
``None`` (compare the elements directly).
59+
extract a comparison key from each element in the array. To support
60+
searching complex records, the key function is not applied to the *x* value.
61+
62+
If *key* is ``None``, the elements are compared directly with no
63+
intervening function call.
5864

5965
.. versionchanged:: 3.10
6066
Added the *key* parameter.
@@ -64,14 +70,13 @@ The following functions are provided:
6470

6571
Insert *x* in *a* in sorted order.
6672

67-
*key* specifies a :term:`key function` of one argument that is used to
68-
extract a comparison key from each input element. The default value is
69-
``None`` (compare the elements directly).
70-
7173
This function first runs :func:`bisect_left` to locate an insertion point.
7274
Next, it runs the :meth:`insert` method on *a* to insert *x* at the
7375
appropriate position to maintain sort order.
7476

77+
To support inserting records in a table, the *key* function (if any) is
78+
applied to *x* for the search step but not for the insertion step.
79+
7580
Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
7681
insertion step.
7782

@@ -85,14 +90,13 @@ The following functions are provided:
8590
Similar to :func:`insort_left`, but inserting *x* in *a* after any existing
8691
entries of *x*.
8792

88-
*key* specifies a :term:`key function` of one argument that is used to
89-
extract a comparison key from each input element. The default value is
90-
``None`` (compare the elements directly).
91-
9293
This function first runs :func:`bisect_right` to locate an insertion point.
9394
Next, it runs the :meth:`insert` method on *a* to insert *x* at the
9495
appropriate position to maintain sort order.
9596

97+
To support inserting records in a table, the *key* function (if any) is
98+
applied to *x* for the search step but not for the insertion step.
99+
96100
Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
97101
insertion step.
98102

@@ -194,8 +198,42 @@ a 'B', and so on::
194198
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
195199
['F', 'A', 'C', 'C', 'B', 'A', 'A']
196200

197-
One technique to avoid repeated calls to a key function is to search a list of
198-
precomputed keys to find the index of a record::
201+
The :func:`bisect`function and :func:`insort` functions also work with lists of
202+
tuples. The *key* argument can serve to extract the field used for ordering
203+
records in a table::
204+
205+
>>> from collections import namedtuple
206+
>>> from operator import attrgetter
207+
>>> from bisect import bisect, insort
208+
>>> from pprint import pprint
209+
210+
>>> Movie = namedtuple('Movie', ('name', 'released', 'director'))
211+
212+
>>> movies = [
213+
... Movie('Jaws', 1975, 'Speilberg'),
214+
... Movie('Titanic', 1997, 'Cameron'),
215+
... Movie('The Birds', 1963, 'Hitchcock'),
216+
... Movie('Aliens', 1986, 'Scott')
217+
... ]
218+
219+
>>> # Find the first movie released on or after 1960
220+
>>> by_year = attrgetter('released')
221+
>>> movies.sort(key=by_year)
222+
>>> movies[bisect(movies, 1960, key=by_year)]
223+
Movie(name='The Birds', released=1963, director='Hitchcock')
224+
225+
>>> # Insert a movie while maintaining sort order
226+
>>> romance = Movie('Love Story', 1970, 'Hiller')
227+
>>> insort(movies, romance, key=by_year)
228+
>>> pprint(movies)
229+
[Movie(name='The Birds', released=1963, director='Hitchcock'),
230+
Movie(name='Love Story', released=1970, director='Hiller'),
231+
Movie(name='Jaws', released=1975, director='Speilberg'),
232+
Movie(name='Aliens', released=1986, director='Scott'),
233+
Movie(name='Titanic', released=1997, director='Cameron')]
234+
235+
If the key function is expensive, it is possible to avoid repeated function
236+
calls by searching a list of precomputed keys to find the index of a record::
199237

200238
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
201239
>>> data.sort(key=lambda r: r[1]) # Or use operator.itemgetter(1).
@@ -208,4 +246,3 @@ precomputed keys to find the index of a record::
208246
('red', 5)
209247
>>> data[bisect_left(keys, 8)]
210248
('yellow', 8)
211-

0 commit comments

Comments
 (0)
0