pytho****@googl*****
pytho****@googl*****
2011年 11月 16日 (水) 17:48:12 JST
Revision: 7d22a28c5c65 Author: Arihiro TAKASE <hinac****@gmail*****> Date: Wed Nov 16 00:47:46 2011 Log: 差分翻訳 2.7.2: library/bisect http://code.google.com/p/python-doc-ja/source/detail?r=7d22a28c5c65 Modified: /library/bisect.rst ======================================= --- /library/bisect.rst Mon Feb 21 17:47:00 2011 +++ /library/bisect.rst Wed Nov 16 00:47:46 2011 @@ -5,6 +5,7 @@ .. module:: bisect :synopsis: バイナリサーチ用の配列二分法アルゴリズム。 .. sectionauthor:: Fred L. Drake, Jr. <fdrak****@acm*****> +.. sectionauthor:: Raymond Hettinger <pytho****@rcn*****> .. example based on the PyModules FAQ entry by Aaron Watters .. <arw****@pytho*****>. @@ -13,84 +14,117 @@ 動作に基本的な二分法アルゴリズムを使っているので、 :mod:`bisect` と呼ばれて います。 ソースコードはこのアルゴリズムの実例として一番役に立つかもしれません (境界 条件はすでに正しいです!)。 -次の関数が用意されています。 - - -.. function:: bisect_left(list, item[, lo[, hi]]) - - ソートされた順序を保ったまま *item* を *list* に挿入するのに適した挿入点 を探し当てます。 - リストの中から検索する部分集合を指定するには、パラメーターの *lo* と *hi* を使います。デフォルトでは、リスト全体が使われます。 *item* - がすでに *list* に含まれている場合、挿入点はどのエントリーよりも前(左)に なります。戻り値は、 ``list.insert()`` - の第一引数として使うのに適しています。 *list* はすでにソートされているも のとします。 - - .. versionadded:: 2.1 - - -.. function:: bisect_right(list, item[, lo[, hi]]) - - :func:`bisect_left` と似ていますが、 *list* に含まれる *item* - のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。 - - .. versionadded:: 2.1 - - -.. function:: bisect(...) - - :func:`bisect_right` のエイリアス。 - - -.. function:: insort_left(list, item[, lo[, hi]]) - - *item* を *list* にソートされた順序で(ソートされたまま)挿入します。これ は、 - ``list.insert(bisect.bisect_left(list, item, lo, hi), item)`` と同等で す。 *list* - はすでにソートされているものとします。 - - .. versionadded:: 2.1 +.. versionadded:: 2.1 + +.. seealso:: + + Latest version of the `bisect module Python source code + <http://svn.python.org/view/python/branches/release27-maint/Lib/bisect.py?view=markup>`_ + +次の関数が用意されています。 + + +.. function:: bisect_left(a, x, lo=0, hi=len(a)) + + ソートされた順序を保ったまま *x* を *a* に挿入できる点を探し当てます。 + リストの中から検索する部分集合を指定するには、パラメーターの *lo* と *hi* を使います。デフォルトでは、リスト全体が使われます。 *x* + がすでに *a* に含まれている場合、挿入点は既存のどのエントリーよりも前(左 )になります。戻り値は、 ``list.insert()`` + の第一引数として使うのに適しています。 *a* はすでにソートされているもの とします。 + + 返された挿入点 *i* は、配列 *a* を二つに分け、 + ``all(val < x for val in a[lo:i])`` が左側に、 + ``all(val >= x for val in a[i:hi])`` が右側になるようにします。 + +.. function:: bisect_right(a, x, lo=0, hi=len(a)) + bisect(a, x, lo=0, hi=len(a)) + + :func:`bisect_left` と似ていますが、 *a* に含まれる *x* + のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。 + +.. function:: insort_left(a, x, lo=0, hi=len(a)) + + *x* を *a* にソートされた順序で挿入します。これは、 + ``a.insert(bisect.bisect_left(a, x, lo, hi), x)`` と等価です。 *a* + はすでにソートされているものとします。なお、O(log n) の探索は + 遅い O(n) の挿入の段階に支配されます。 + +.. function:: insort_right(a, x, lo=0, hi=len(a)) + insort(a, x, lo=0, hi=len(a)) + + :func:`insort_left` と似ていますが、 *a* に含まれる *x* のうち、 + どのエントリーよりも後ろに *x* を挿入します。 + +.. seealso:: + + bisect を利用して、直接の探索ができ、キー関数をサポートする、 + 完全な機能を持つコレクションクラスを組み立てる `SortedCollection recipe + <http://code.activestate.com/recipes/577197-sortedcollection/>`_\ 。 + キーは、探索中に不必要な呼び出しをさせないために、予め計算しておきます。 -.. function:: insort_right(list, item[, lo[, hi]]) - - :func:`insort_left` と似ていますが、 *list* に含まれる *item* のうち、ど のエントリーよりも後ろに *item* を挿入します。 - - .. versionadded:: 2.1 - - -.. function:: insort(...) - - :func:`insort_right` のエイリアス。 - - -使用例 ------- +ソート済みリストの探索 +---------------------- + +上記の :func:`bisect` 関数群は挿入点を探索するのには便利ですが、普通の +探索タスクに使うのはトリッキーだったり不器用だったりします。以下の 5 関数 は、 +これらをどのように標準の探索やソート済みリストに変換するかを説明します:: + + 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 + + +その他の使用例 +-------------- .. _bisect-example: -一般には、 :func:`bisect` 関数は数値データを分類するのに役に立ちます。この 例では、 :func:`bisect` -を使って、(たとえば)順序のついた数値の区切り点の集合に基づいて、試験全体の 成績の文字を調べます。区切り点は 85 以上は 'A'、 75..84 は +:func:`bisect` 関数は数値テーブルの探索に役に立ちます。この例で は、 :func:`bisect` +を使って、(たとえば)順序のついた数値の区切り点の集合に基づいて、試験の成績 の +等級を表す文字を調べます。区切り点は 90 以上は 'A'、 80 から 89 は 'B'、などです。 - >>> grades = "FEDCBA" - >>> breakpoints = [30, 44, 66, 75, 85] - >>> from bisect import bisect - >>> def grade(total): - ... return grades[bisect(breakpoints, total)] + >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'): + ... i = bisect(breakpoints, score) + ... return grades[i] ... - >>> grade(66) - 'C' - >>> map(grade, [33, 99, 77, 44, 12, 88]) - ['E', 'A', 'B', 'D', 'F', 'A'] - -.. Unlike the :func:`sorted` function, it does not make sense for the :func:`bisect` - functions to have *key* or *reversed* arguments because that would lead to an - inefficent design (successive calls to bisect functions would not "remember" - all of the previous key lookups). + >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]] + ['F', 'A', 'C', 'C', 'B', 'A', 'A'] :func:`sorted` 関数と違い、 :func:`bisect` 関数に *key* や *reversed* 引数 を 用意するのは、設計が非効率になるので、非合理的です。 (連続する bisect 関数 の -呼び出しは前回の key 参照の結果を覚えません) - -.. Instead, it is better to search a list of precomputed keys to find the index - of the record in question:: +呼び出しは前回の key 参照の結果を "記憶" しません) 代わりに、事前に計算しておいたキーのリストから検索して、レコードのインデッ クスを 見つけます。
