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

このモジュールは、挿入の度にリストをソートすることなく、リストをソートされた 順序に保つことをサポートします。 大量の比較操作を伴うような、アイテムがたくさんあるリストでは、より一般的な アプローチに比べて、パフォーマンスが向上します。

動作に基本的な二分法アルゴリズムを使っているので、bisect と呼ばれています。 ソースコードはこのアルゴリズムの実例として一番役に立つかもしれません (境界条件はすでに正しいです!)。

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

bisect_left( list, item[, lo[, hi]])

ソートされた順序を保ったまま itemlist に挿入するのに適した 挿入点を探し当てます。 リストの中から検索する部分集合を指定するには、パラメーターの lohi を使います。 デフォルトでは、リスト全体が使われます。 item がすでに list に含まれている場合、挿入点はどのエントリー よりも前(左)になります。 戻り値は、list.insert() の第一引数として使うのに適しています。 list はすでにソートされているものとします。 バージョン 2.1 で 新たに追加 された仕様です。

bisect_right( list, item[, lo[, hi]])
bisect_left() と似ていますが、list に含まれる item のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。 バージョン 2.1 で 新たに追加 された仕様です。

bisect( ...)
bisect_right() のエイリアス。

insort_left( list, item[, lo[, hi]])
itemlist にソートされた順序で(ソートされたまま)挿入します。 これは、 list.insert(bisect.bisect_left(list, item, lo, hi), item) と同等です。 list はすでにソートされているものとします。 バージョン 2.1 で 新たに追加 された仕様です。

insort_right( list, item[, lo[, hi]])
insort_left() と似ていますが、list に含まれる item のうち、どのエントリーよりも後ろに item を挿入します。 バージョン 2.1 で 新たに追加 された仕様です。

insort( ...)
insort_right() のエイリアス。



Subsections
ご意見やご指摘をお寄せになりたい方は、 このドキュメントについて... をご覧ください。