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

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

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

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

基本的な二分法アルゴリズムで処理するため、このモジュールは "bisect" と
呼ばれます。 特定の値を探す他の二分探索ツールとは異なり、このモジュー
ルの関数は挿入位置を探すように設計されています。 そのため、値が見つか
ったかを判断するために "__eq__()" メソッドを呼び出すことはありません。
代わりに "__lt__()" メソッドだけを呼び出し、配列内の値の間にある挿入位
置を返します。

注釈:

  このモジュールの関数はスレッドセーフではありません。 複数のスレッド
  から同じシーケンスに対して "bisect" の関数を同時に使うと、動作が未定
  義になる可能性があります。 同様に、"bisect" の関数がシーケンスを操作
  している間に別のスレッドがそのシーケンスを変更した場合も、結果は未定
  義です。 例えば、複数のスレッドから同じリストに対して
  "insort_left()" を使うと、リストのソート順が崩れる可能性があります。

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

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

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

   返された挿入位置 *ip* は、配列 *a* を 2 つのスライスに分割します。
   左側のスライスでは "all(elem < x for elem in a[lo : ip])" が真とな
   り、右側のスライスでは "all(elem >= x for elem in a[ip : hi])" が真
   となります。

   *key* は、配列の各要素から比較用のキーを取り出す、引数を 1 つ受け取
   る *キー関数* を指定します。 複雑なレコードを検索できるように、キー
   関数は値 *x* には適用しません。

   *key* が "None" の場合は要素を直接比較し、キー関数を呼び出しません
   。

   バージョン 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* は、配列 *a* を 2 つのスライスに分割します。
   左側のスライスでは "all(elem <= x for elem in a[lo : ip])" が真とな
   り、右側のスライスでは "all(elem > x for elem in a[ip : hi])" が真
   となります。

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

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

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

   まず "bisect_left()" で挿入位置を探します。 次に *a* の "insert()"
   メソッドを呼び出し、ソート順を保つ適切な位置に *x* を挿入します。

   テーブルへのレコードの挿入に対応するため、*key* 関数を指定した場合
   は、探索の段階で *x* に適用し、挿入の段階では適用しません。

   *O*(log *n*) の探索よりも、遅い *O*(*n*) の挿入処理が全体の実行時間
   を支配することに注意してください。

   バージョン 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* を挿入します。

   まず "bisect_right()" で挿入位置を探します。 次に *a* の "insert()"
   メソッドを呼び出し、ソート順を保つ適切な位置に *x* を挿入します。

   テーブルへのレコードの挿入に対応するため、*key* 関数を指定した場合
   は、探索の段階で *x* に適用し、挿入の段階では適用しません。

   *O*(log *n*) の探索よりも、遅い *O*(*n*) の挿入処理が全体の実行時間
   を支配することに注意してください。

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


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

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

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

* *insort()* 関数の計算量は *O*(*n*) です。 対数時間の探索よりも、線形
  時間の挿入処理が全体の実行時間を支配するためです。

* 探索関数は状態を保持せず、キー関数の結果を使用後に破棄します。 その
  ため、ループ内で探索関数を使うと、配列の同じ要素に対してキー関数を繰
  り返し呼び出す可能性があります。 キー関数が遅い場合は、
  "@functools.cache" でラップして重複した計算を避けることを検討してく
  ださい。 または、あらかじめ計算したキーの配列を探索して挿入位置を求
  める方法もあります (後の使用例を参照してください)。

参考:

  * Sorted Collections は、*bisect* を使ってソート済みのデータのコレク
    ションを管理する高性能なモジュールです。

  * 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):
   ...     i = bisect([60, 70, 80, 90], score)
   ...     return "FDCBA"[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')
   ... ]

   >>> # 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')

   >>> # ソート順を保ったまま映画を挿入する
   >>> 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])       # または operator.itemgetter(1) を使う。
   >>> keys = [r[1] for r in data]         # キーのリストを事前に計算する。
   >>> 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)
