Mercurial > cpython-lru_cache-weakref

annotate Doc/lib/libbisect.tex @ 25838:8540887bcec6 2.2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Backport of 2.183: Fix memory leak in add_subclass() found by NealN with valgrind.
author Guido van Rossum <guido@python.org>
date Fri, 18 Oct 2002 13:42:21 +0000
parents eeb2e77c5bad
children 703e63ae0f01
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
8918
acfffe14628e New section header style.
Fred Drake <fdrake@acm.org>
parents: 8770
diff changeset
1 \section{\module{bisect} ---
10251
d83935d14084 Shorten a few section titles.
Fred Drake <fdrake@acm.org>
parents: 10243
diff changeset
2 Array bisection algorithm}
8716
760dcf197048 Adjusted to use the new module synopsis support macros.
Fred Drake <fdrake@acm.org>
parents: 8189
diff changeset
3
10251
d83935d14084 Shorten a few section titles.
Fred Drake <fdrake@acm.org>
parents: 10243
diff changeset
4 \declaremodule{standard}{bisect}
8770
256a80f39a88 Added the bisect synopsis.
Fred Drake <fdrake@acm.org>
parents: 8716
diff changeset
5 \modulesynopsis{Array bisection algorithms for binary searching.}
12223
e82e82b3b9ad Merged changes from the 1.5.2p2 release.
Fred Drake <fdrake@acm.org>
parents: 10251
diff changeset
6 \sectionauthor{Fred L. Drake, Jr.}{fdrake@acm.org}
e82e82b3b9ad Merged changes from the 1.5.2p2 release.
Fred Drake <fdrake@acm.org>
parents: 10251
diff changeset
7 % LaTeX produced by Fred L. Drake, Jr. <fdrake@acm.org>, with an
e82e82b3b9ad Merged changes from the 1.5.2p2 release.
Fred Drake <fdrake@acm.org>
parents: 10251
diff changeset
8 % example based on the PyModules FAQ entry by Aaron Watters
e82e82b3b9ad Merged changes from the 1.5.2p2 release.
Fred Drake <fdrake@acm.org>
parents: 10251
diff changeset
9 % <arw@pythonpros.com>.
8716
760dcf197048 Adjusted to use the new module synopsis support macros.
Fred Drake <fdrake@acm.org>
parents: 8189
diff changeset
10
8189
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
11
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
12 This module provides support for maintaining a list in sorted order
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
13 without having to sort the list after each insertion. For long lists
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
14 of items with expensive comparison operations, this can be an
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
15 improvement over the more common approach. The module is called
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
16 \module{bisect} because it uses a basic bisection algorithm to do its
10243
575c4ea2542b Fix an amazing number of typos & malformed sentences reported by Detlef
Fred Drake <fdrake@acm.org>
parents: 8918
diff changeset
17 work. The source code may be most useful as a working example of the
18411
eeb2e77c5bad Fix up a few style nits -- avoid "e.g." and "i.e." -- these make
Fred Drake <fdrake@acm.org>
parents: 15735
diff changeset
18 algorithm (the boundary conditions are already right!).
8189
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
19
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
20 The following functions are provided:
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
21
15729
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
22 \begin{funcdesc}{bisect_left}{list, item\optional{, lo\optional{, hi}}}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
23 Locate the proper insertion point for \var{item} in \var{list} to
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
24 maintain sorted order. The parameters \var{lo} and \var{hi} may be
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
25 used to specify a subset of the list which should be considered; by
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
26 default the entire list is used. If \var{item} is already present
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
27 in \var{list}, the insertion point will be before (to the left of)
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
28 any existing entries. The return value is suitable for use as the
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
29 first parameter to \code{\var{list}.insert()}. This assumes that
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
30 \var{list} is already sorted.
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
31 \versionadded{2.1}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
32 \end{funcdesc}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
33
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
34 \begin{funcdesc}{bisect_right}{list, item\optional{, lo\optional{, hi}}}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
35 Similar to \function{bisect_left()}, but returns an insertion point
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
36 which comes after (to the right of) any existing entries of
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
37 \var{item} in \var{list}.
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
38 \versionadded{2.1}
8189
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
39 \end{funcdesc}
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
40
15729
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
41 \begin{funcdesc}{bisect}{\unspecified}
15735
85dc0ce0162e Based on comments from Guido, do not describe bisect() and insert() as
Fred Drake <fdrake@acm.org>
parents: 15729
diff changeset
42 Alias for \function{bisect_right()}.
15729
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
43 \end{funcdesc}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
44
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
45 \begin{funcdesc}{insort_left}{list, item\optional{, lo\optional{, hi}}}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
46 Insert \var{item} in \var{list} in sorted order. This is equivalent
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
47 to \code{\var{list}.insert(bisect.bisect_left(\var{list}, \var{item},
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
48 \var{lo}, \var{hi}), \var{item})}. This assumes that \var{list} is
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
49 already sorted.
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
50 \versionadded{2.1}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
51 \end{funcdesc}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
52
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
53 \begin{funcdesc}{insort_right}{list, item\optional{, lo\optional{, hi}}}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
54 Similar to \function{insort_left()}, but inserting \var{item} in
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
55 \var{list} after any existing entries of \var{item}.
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
56 \versionadded{2.1}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
57 \end{funcdesc}
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
58
2b3bc08d4d85 Update documentation to include the new functions, and use the more
Fred Drake <fdrake@acm.org>
parents: 12223
diff changeset
59 \begin{funcdesc}{insort}{\unspecified}
15735
85dc0ce0162e Based on comments from Guido, do not describe bisect() and insert() as
Fred Drake <fdrake@acm.org>
parents: 15729
diff changeset
60 Alias for \function{insort_right()}.
8189
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
61 \end{funcdesc}
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
62
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
63
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
64 \subsection{Example}
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
65 \nodename{bisect-example}
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
66
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
67 The \function{bisect()} function is generally useful for categorizing
15735
85dc0ce0162e Based on comments from Guido, do not describe bisect() and insert() as
Fred Drake <fdrake@acm.org>
parents: 15729
diff changeset
68 numeric data. This example uses \function{bisect()} to look up a
8189
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
69 letter grade for an exam total (say) based on a set of ordered numeric
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
70 breakpoints: 85 and up is an `A', 75..84 is a `B', etc.
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
71
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
72 \begin{verbatim}
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
73 >>> grades = "FEDCBA"
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
74 >>> breakpoints = [30, 44, 66, 75, 85]
15735
85dc0ce0162e Based on comments from Guido, do not describe bisect() and insert() as
Fred Drake <fdrake@acm.org>
parents: 15729
diff changeset
75 >>> from bisect import bisect
8189
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
76 >>> def grade(total):
15735
85dc0ce0162e Based on comments from Guido, do not describe bisect() and insert() as
Fred Drake <fdrake@acm.org>
parents: 15729
diff changeset
77 ... return grades[bisect(breakpoints, total)]
8189
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
78 ...
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
79 >>> grade(66)
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
80 'C'
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
81 >>> map(grade, [33, 99, 77, 44, 12, 88])
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
82 ['E', 'A', 'B', 'D', 'F', 'A']
ce2d120c3903 Section for bisect module.
Fred Drake <fdrake@acm.org>
parents:
diff changeset
83 \end{verbatim}