リストの中にある値を探すとき、多くの方はまずinを使うと思います。書きやすくて読みやすいので、それで困らない場面もたくさんあります。
ところが、データが何十万件にもなると話が変わってきます。inは先頭から1つずつ順番に調べるので、件数に比例して時間がかかるからです。
もしそのリストがすでに小さい順に並んでいるなら、もっと賢い探し方があります。それが二分探索で、Pythonではbisectという標準ライブラリで手軽に使えます。
今回は、二分探索の考え方から、bisectの基本の関数、実務で役立つ使い方と注意点までを順番に見ていきましょう。
bisectは、並べ替え済みのリストを二分探索する道具¶
bisectは、並べ替え済みのリストに対して、ある値を入れるならどこが正しい位置かを教えてくれるモジュールです。インストールは不要で、importするだけで使えます。
名前のbisectは、英語で2つに分けるという意味です。その名のとおり、リストを半分ずつに分けながら目的の位置を絞り込んでいきます。
二分探索は、辞書を引くときの探し方と同じ¶
二分探索の考え方は、紙の辞書を引くときの動きに似ています。最初のページから1枚ずつめくる人はいませんよね。
まず真ん中あたりを開き、探している単語がそれより前か後ろかを判断します。これを繰り返すと、調べる範囲が毎回半分になっていきます。
100万件のリストでも、半分にする操作を20回ほど繰り返せば1件まで絞り込めます。件数が増えても、調べる回数はほとんど増えないのが二分探索の強みです。
計算量という考え方を知っておくと、この違いがもっとはっきり見えてきます。【関連記事】「実行時間が終わらない…」を卒業する！あなたのコードを100倍速くする計算量の考え方
前提は、リストが並べ替え済みであること¶
二分探索には、ひとつだけ大事な前提があります。リストが小さい順に並んでいなければなりません。
真ん中の値と比べて前か後ろかを判断する仕組みなので、順番がバラバラだと判断そのものが成り立たないのです。bisectは並び順をチェックしてくれないので、バラバラのリストを渡してもエラーにならず、ただ間違った位置を返します。
基本の関数は、bisect_leftとbisect_right¶
bisectの中心になるのは、挿入位置を返す2つの関数です。どちらもリストと探したい値を受け取り、インデックスを整数で返します。
違いが出るのは、同じ値がすでにリストに入っているときです。次のコードで確かめてみましょう。
import bisect
scores = [10, 20, 20, 20, 30]
print(bisect.bisect_left(scores, 20)) # 1
print(bisect.bisect_right(scores, 20)) # 4
print(bisect.bisect(scores, 20)) # 4
bisect_leftは、同じ値の群れのいちばん左の位置を返します。bisect_rightは、同じ値の群れのすぐ右の位置を返します。
ただのbisectは、bisect_rightの別名です。迷ったら、どちらの端が欲しいのかを考えて、leftかrightを明示して書くと読み手に親切です。
3つの関数の違いを、表にまとめておきます。
| 関数 | 同じ値があるときに返す位置 | よく使う場面 |
|---|---|---|
| bisect_left | 同じ値のいちばん左 | 値が含まれているかの判定、以上の範囲を探す |
| bisect_right | 同じ値のいちばん右のすぐ後ろ | 境界値で区分けする、より大きい範囲を探す |
| bisect | bisect_rightと同じ | 短く書きたいとき |
点数から評価を決めてみよう¶
bisectの使い方として、公式ドキュメントでも紹介されている定番があります。点数を、境界値にしたがってAやBといった評価に変換する処理です。
if文を何段も重ねて書く方も多いと思いますが、bisectを使うと次のように短くまとまります。
import bisect
def grade(score, breakpoints=[60, 70, 80, 90], grades="FDCBA"):
i = bisect.bisect(breakpoints, score)
return grades[i]
print([grade(s) for s in [33, 60, 79, 90, 100]])
# ['F', 'D', 'C', 'A', 'A']
breakpointsは、評価が切り替わる点数の一覧です。bisectが返すインデックスが、そのままgradesの何文字目かに対応しています。
60点ちょうどがDになるのは、bisect_rightと同じ動きをするからです。境界値を上の区分に入れたいならbisect、下の区分に入れたいならbisect_leftと覚えておくと迷いません。
この書き方の良いところは、境界値を変えたいときにリストを書き換えるだけで済む点です。送料の区分や、年齢による料金の区分など、実務でも同じ形の処理はよく出てきます。
値が含まれているかを高速に調べる¶
bisectは挿入位置を返す関数なので、値が含まれているかどうかは直接教えてくれません。そこで、返ってきた位置の値を確かめるひと手間を加えます。
import bisect
def contains(sorted_list, x):
i = bisect.bisect_left(sorted_list, x)
return i != len(sorted_list) and sorted_list[i] == x
data = [3, 8, 10, 15]
print(contains(data, 10)) # True
print(contains(data, 11)) # False
i != len(sorted_list) の確認を忘れると、リストのどの値よりも大きい値を探したときにIndexErrorになります。ここは初心者がよくつまずくところです。
では、inと比べてどれくらい速いのでしょうか。私の手元のPython 3.11で、0から999999までの100万件のリストから末尾の値を探す処理を100回ずつ測ってみました。
inは合計でおよそ0.58秒、bisect_leftは0.0001秒にも届きませんでした。環境によって数字は変わりますが、件数が多いほど差が開くことは覚えておいてください。
insortで、順番を保ったまま値を追加する¶
並べ替え済みのリストに値を1つ追加したいとき、appendしてからsortし直すのは遠回りです。bisectには、挿入まで一気に行うinsortという関数も用意されています。
import bisect
data = [3, 8, 15]
bisect.insort(data, 10)
print(data) # [3, 8, 10, 15]
insortにも、insort_leftとinsort_rightの2種類があります。数値だけを扱うならどちらでも結果は同じなので、最初はinsortだけ覚えておけば十分です。
並べ替えそのものの仕組みについては、こちらの記事で詳しく解説しています。【関連記事】Pythonのsortedとsortの違いとは？key引数で自在に並べ替える方法を初心者向けに解説
insortは、探すのは速いが挿入は速くない¶
ここで1つ注意があります。insortのうち、位置を探す部分は二分探索なので速いのですが、リストへの挿入そのものは速くありません。
リストの途中に値を入れると、それより後ろの要素をすべて1つずつずらす必要があるからです。公式ドキュメントでも、insortは挿入の手間が支配的なので、全体としては件数に比例する時間がかかると説明されています。
私は10年ほどエンジニアとして開発に関わってきましたが、以前ログ集計のバッチで、数十万件のリストにinsortで1件ずつ足していく処理を書いたことがあります。探索は速いはずなのにバッチが一向に終わらず、原因を追ってみたら挿入のたびに大量の要素がずれていたのが犯人でした。
大量のデータをまとめて並べたいなら、全部appendしてから最後に1回だけsortするほうが速い場面も多いです。途中で最小値だけを何度も取り出したいなら、heapqのほうが向いています。【関連記事】Pythonのheapqとは？毎回sortせずに最小値をすばやく取り出す仕組みを初心者向けに解説
Python 3.10から使えるkey引数¶
bisectの関数には、Python 3.10からkey引数が加わりました。sortedのkeyと同じように、比較の前に要素へ関数を適用できる仕組みです。
これにより、タプルや辞書が並んだリストでも、特定の項目を基準に探せるようになりました。年齢の順に並んだユーザーの一覧で試してみましょう。
import bisect
users = [("sato", 21), ("suzuki", 34), ("tanaka", 45)]
get_age = lambda u: u[1]
# 34歳の人が入る位置を探す（xには年齢そのものを渡す）
print(bisect.bisect_left(users, 34, key=get_age)) # 1
# 30歳の人を、年齢順を保ったまま追加する（xにはタプルごと渡す）
bisect.insort(users, ("ito", 30), key=get_age)
print(users)
# [('sato', 21), ('ito', 30), ('suzuki', 34), ('tanaka', 45)]
コメントに書いたとおり、ここには少しクセがあります。bisect_leftやbisect_rightでは、keyはリストの要素にだけ適用され、探したい値にはかかりません。
一方でinsortは、追加する値にもkeyを適用します。bisect系には比較用の値を、insort系には要素そのものを渡す、と覚えておくと混乱しません。
標準ライブラリのソースコードを読むと、この違いがはっきりわかります。insort_rightの中で、key(x)を計算してからbisect_rightに渡しているのです。
bisectが活躍する場面と、向いていない場面¶
ここまでの内容を踏まえて、bisectを選ぶべきかどうかの目安を整理しておきます。使いどころを表にまとめました。
| やりたいこと | おすすめ | 理由 |
|---|---|---|
| 並べ替え済みのリストから何度も値を探す | bisect_left | 1回ごとの探索が速い |
| 境界値で区分けする | bisect | if文の段を重ねずに済む |
| ある範囲に入る件数を数える | bisect_leftとbisect_rightの差 | 2回の探索で求まる |
| 値があるかだけを何度も調べる | set | 並び順が不要なら最も手軽 |
| 最小値を何度も取り出す | heapq | 取り出しと追加がどちらも速い |
範囲の件数を数える使い方は、意外と便利です。たとえば点数の一覧から60点以上80点未満の人数を知りたいなら、bisect_left(scores, 80) から bisect_left(scores, 60) を引くだけで求まります。
逆に、並び順に意味がなく、ただ値があるかどうかを調べたいだけならsetを使いましょう。setは並べ替えの手間もなく、平均的には一瞬で判定できます。
setで存在チェックが速くなる理由は、こちらで詳しく解説しています。【関連記事】Pythonの集合（set）とは？重複の削除と高速な存在チェックを初心者向けに解説
つまずきやすいところ¶
最後に、初心者がひっかかりやすい点を3つ振り返っておきます。どれも、エラーが出ずに間違った結果になるので気づきにくいものです。
ひとつめは、並べ替えていないリストにbisectを使うことです。bisectは順番を確認しないので、間違った位置を静かに返します。
ふたつめは、大きい順に並んだリストに使うことです。bisectは小さい順を前提にしているので、降順のリストでは正しく動きません。
みっつめは、Python 3.9以前の環境でkey引数を使うことです。サーバーのPythonが古いとTypeErrorになるので、動かす環境のバージョンを先に確認しておきましょう。
まとめと、次の一歩¶
bisectは、並べ替え済みのリストを半分ずつ絞り込んで、目的の位置をすばやく見つける道具です。データが増えても探す回数はほとんど増えません。
まずはbisect_leftとbisect_rightの違い、そして境界値で区分けする使い方を覚えておけば十分です。insortは便利ですが、大量のデータを1件ずつ足す用途には向かないことを忘れないでください。
次の一歩として、手元のコードでif文が何段も並んだ区分けの処理を探してみてください。境界値のリストとbisectに置き換えると、驚くほどすっきりするはずです。
ここまでお読みいただきありがとうございました。
