"bisect" --- 配列二分法アルゴリズム
***********************************

**ソースコード:** Lib/bisect.py

======================================================================

このモジュールは、挿入のたびにリストをソートすることなく、ソートされた
順序でリストを維持するためのサポートを提供します。 コストのかかる比較
演算を伴う長いリストの場合、これは線形検索や頻繁な並べ替えよりも改善さ
れる可能性があります。

The module is called "bisect" because it uses a basic bisection
algorithm to do its work.  Unlike other bisection tools that search
for a specific value, the functions in this module are designed to
locate an insertion point. Accordingly, the functions never call an
"__eq__()" method to determine whether a value has been found.
Instead, the functions only call the "__lt__()" method and will return
an insertion point between values in an array.

注釈:

  The functions in this module are not thread-safe. If multiple
  threads concurrently use "bisect" functions on the same sequence,
  this may result in undefined behaviour. Likewise, if the provided
  sequence is mutated by a different thread while a "bisect" function
  is operating on it, the result is undefined. For example, using
  "insort_left()" on the same list from multiple threads may result in
  the list becoming unsorted.

次の関数が用意されています:

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

   ソートされた順序を保ったまま *x* を *a* に挿入できる点を探し当てま
   す。リストの中から検索する部分集合を指定するには、パラメータの *lo*
   と *hi* を使います。デフォルトでは、リスト全体が使われます。*x* が
   すでに *a* に含まれている場合、挿入点は既存のどのエントリーよりも前
   (左)になります。戻り値は、"list.insert()" の第一引数として使うのに
   適しています。*a* はすでにソートされているものとします。

   返された挿入点 *ip* パーティションは、左のスライスでは "all(elem <
   x for elem in a[lo : ip])" が真となり、右のスライスでは "all(elem
   >= x for elem in a[ip : hi])" が真となるように、配列 *a* を2つのス
   ライスに分割します。

   *key* specifies a *key function* of one argument that is used to
   extract a comparison key from each element in the array.  To
   support searching complex records, the key function is not applied
   to the *x* value.

   If *key* is "None", the elements are compared directly and no key
   function is called.

   バージョン 3.10 で変更: *key* パラメータが追加されました。

bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.bisect(a, x, lo=0, hi=len(a), *, key=None)

   "bisect_left()" と似ていますが、 *a* に含まれる *x* のうち、どのエ
   ントリーよりも後ろ(右)にくるような挿入点を返します。

   返された挿入点 *ip* パーティションは、左のスライスでは "all(elem <=
   x for elem in a[lo : ip])" が真となり、右のスライスでは "all(elem >
   x for elem in a[ip : hi])" が真となるように、配列 *a* を2つのスライ
   スに分割します。

   バージョン 3.10 で変更: *key* パラメータが追加されました。

bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)

   *x* を *a* にソート順で挿入します。

   This function first runs "bisect_left()" to locate an insertion
   point. Next, it runs the "insert()" method on *a* to insert *x* at
   the appropriate position to maintain sort order.

   To support inserting records in a table, the *key* function (if
   any) is applied to *x* for the search step but not for the
   insertion step.

   Keep in mind that the *O*(log *n*) search is dominated by the slow
   *O*(*n*) insertion step.

   バージョン 3.10 で変更: *key* パラメータが追加されました。

bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
bisect.insort(a, x, lo=0, hi=len(a), *, key=None)

   "insort_left()" と似ていますが、 *a* に含まれる *x* のうち、どのエ
   ントリーよりも後ろに *x* を挿入します。

   This function first runs "bisect_right()" to locate an insertion
   point. Next, it runs the "insert()" method on *a* to insert *x* at
   the appropriate position to maintain sort order.

   To support inserting records in a table, the *key* function (if
   any) is applied to *x* for the search step but not for the
   insertion step.

   Keep in mind that the *O*(log *n*) search is dominated by the slow
   *O*(*n*) insertion step.

   バージョン 3.10 で変更: *key* パラメータが追加されました。


パフォーマンスに関するメモ
==========================

*bisect()* と *insort()* を使って時間的制約のあるコードを書くときは、
以下のことを念頭に置いてください:

* 二分法は、値の範囲を検索するのに有効です。 特定の値を検索する場合は
  、辞書の方が効率的です。

* The *insort()* functions are *O*(*n*) because the logarithmic search
  step is dominated by the linear time insertion step.

* The search functions are stateless and discard key function results
  after they are used.  Consequently, if the search functions are used
  in a loop, the key function may be called again and again on the
  same array elements. If the key function isn't fast, consider
  wrapping it with "functools.cache()" to avoid duplicate
  computations.  Alternatively, consider searching an array of
  precomputed keys to locate the insertion point (as shown in the
  examples section below).

参考:

  * Sorted Collections is a high performance module that uses *bisect*
    to managed sorted collections of data.

  * bisect を利用して、直接の探索ができ、キー関数をサポートする、完全
    な機能を持つコレクションクラスを組み立てる SortedCollection recipe
    。キーは、探索中に不必要な呼び出しをさせないために、予め計算してお
    きます。


ソート済みリストの探索
======================

上記の bisect 関数 は挿入点を見つけるには便利ですが、一般的な検索タス
クに使うには厄介であったり、使いにくい場合があります。 以下の5つの関数
は、それらをソートされたリストの標準的な検索に変換する方法を示していま
す:

   def index(a, x):
       'xにちょうど等しい左端の値を見つける'
       i = bisect_left(a, x)
       if i != len(a) and a[i] == x:
           return i
       raise ValueError

   def find_lt(a, x):
       'xより小さい右端の値を見つける'
       i = bisect_left(a, x)
       if i:
           return a[i-1]
       raise ValueError

   def find_le(a, x):
       'x以下の右端の値を見つける'
       i = bisect_right(a, x)
       if i:
           return a[i-1]
       raise ValueError

   def find_gt(a, x):
       'xより大きい左端の値を見つける'
       i = bisect_right(a, x)
       if i != len(a):
           return a[i]
       raise ValueError

   def find_ge(a, x):
       '左端の項目がx以上であることを確認する'
       i = bisect_left(a, x)
       if i != len(a):
           return a[i]
       raise ValueError


使用例
======

"bisect()" 関数は数値テーブルの探索に役に立ちます。この例では、
"bisect()" を使って、(たとえば)順序のついた数値の区切り点の集合に基づ
いて、試験の成績の等級を表す文字を調べます。区切り点は 90 以上は 'A'、
80 から 89 は 'B'、などです:

   >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
   ...     i = bisect(breakpoints, score)
   ...     return grades[i]
   ...
   >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
   ['F', 'A', 'C', 'C', 'B', 'A', 'A']

"bisect()" と "insort()" 関数もタプルのリストで動作します。 引数 *key*
はテーブルのレコードの順序付けに使用されるフィールドを抽出します:

   >>> from collections import namedtuple
   >>> from operator import attrgetter
   >>> from bisect import bisect, insort
   >>> from pprint import pprint

   >>> Movie = namedtuple('Movie', ('name', 'released', 'director'))

   >>> movies = [
   ...     Movie('Jaws', 1975, 'Spielberg'),
   ...     Movie('Titanic', 1997, 'Cameron'),
   ...     Movie('The Birds', 1963, 'Hitchcock'),
   ...     Movie('Aliens', 1986, 'Cameron')
   ... ]

   >>> # Find the first movie released after 1960
   >>> by_year = attrgetter('released')
   >>> movies.sort(key=by_year)
   >>> movies[bisect(movies, 1960, key=by_year)]
   Movie(name='The Birds', released=1963, director='Hitchcock')

   >>> # Insert a movie while maintaining sort order
   >>> romance = Movie('Love Story', 1970, 'Hiller')
   >>> insort(movies, romance, key=by_year)
   >>> pprint(movies)
   [Movie(name='The Birds', released=1963, director='Hitchcock'),
    Movie(name='Love Story', released=1970, director='Hiller'),
    Movie(name='Jaws', released=1975, director='Spielberg'),
    Movie(name='Aliens', released=1986, director='Cameron'),
    Movie(name='Titanic', released=1997, director='Cameron')]

キー関数がコストがかかる場合は、レコードのインデックスを見つけるために
事前に計算されたキーのリストを検索することにより、関数呼び出しの繰り返
しを回避することが可能です:

   >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
   >>> data.sort(key=lambda r: r[1])       # Or use operator.itemgetter(1).
   >>> keys = [r[1] for r in data]         # Precompute a list of keys.
   >>> data[bisect_left(keys, 0)]
   ('black', 0)
   >>> data[bisect_left(keys, 1)]
   ('blue', 1)
   >>> data[bisect_left(keys, 5)]
   ('red', 5)
   >>> data[bisect_left(keys, 8)]
   ('yellow', 8)
