いろいろ備忘録日記

主に .NET とか Go とか Flutter とか Python絡みのメモを公開しています。

Pythonメモ-37 (bisectモジュール) (配列二分法アルゴリズム, bisect_left, bisect_right, SortedCollection)

python

概要

大量のデータからマッチするものを見つけるという処理はよくあります。

大抵はリストなどを使って処理すると思うのですが

件数が何十万件とかなると、リストの標準メソッドを使うと

先頭からスキャンしていくので、時間がかかる時があります。

そういうときに使えるのが、bisectモジュール さん。

二分探索アルゴリズムを使って、対象のインデックスを見つけてくれます。

使う際の注意点は、「対象となるシーケンスがソートされていること」。

使う前にシーケンスがソートされている必要があります。

サンプル

以下、シーケンス内に対象のデータがある場合に、どれくらい速度差がでるのか

ちょこっと確認してみるサンプルです。シーケンスの要素数は数値のみで1000万個。

その中から値が5555555のインデックス値を取得しています。

最初に list.index, その後に bisect_left, bisect_right の順で取得しています。

# pylint: disable=C0111
# pylint: disable=C0103
# pylint: disable=C0326
import bisect
import contextlib
import time

from typing import Sequence, Any


@contextlib.contextmanager
def stopwatch(prefix: str=''):
    start = time.perf_counter()
    yield
    end = time.perf_counter()
    print(f'{prefix:<12}{" = " if prefix else ""}{end - start:.6f}')


def index(seq: Sequence, val: Any, direction: int=1) -> int:
    def _get_func():
        if direction == 1:
            return (bisect.bisect_left, 0)
        return (bisect.bisect_right, -1)

    f, adjust = _get_func()
    i = f(seq, val)

    if i != len(seq) and seq[i + adjust] == val:
        return i + adjust

    raise ValueError(f'{val} is not in sequence')


values = list(range(10000000))
target = 5555555

with stopwatch('list.index'):
    values.index(target)

with stopwatch('bisect_left'):
    index(values, target)

with stopwatch('bisect_right'):
    index(values, target, direction=2)

結果は、私の環境では以下のようになりました。

list.index   = 0.095323
bisect_left  = 0.000018
bisect_right = 0.000009

たんなる数値のリストなので、list.index自体も対して時間かかっていませんが

それでも、bisectの方が圧倒的に速いです。

要素が複合型の場合どうすんの？

たまに聞かれるのが、「要素が数値みたいにスカラ値の場合分かるんですが、タプルみたいに

複合値持つデータの場合はどうすんの？」って内容です。

bisectモジュール自身は、ソートされた後のシーケンスを対象としているので

sorted関数みたいに、key引数を持っているわけではありません。

なので、複合型をbisectしたい場合は

  • まず、元のシーケンス(ソート済み)からキー値のシーケンスをつくる

  • キー値のシーケンスに対して bisect する。

  • 取得できたインデックスに対して元のリストをいじる

という流れになりますね。あくまで、ソート済みの整理された情報の

中から、特定の値を素早く見つけることに特化しているモジュールと

なります。

ちなみに小ネタですが、pythonのtupleをソートに使う場合は

特殊ルールがあって、まず第一要素でソートされます。

第一要素が同値の場合、次に第二要素、その次に第三要素って

かたちで処理されます。なので、何気にソート処理する際に

それを見越して調整したtupleつくるとグルーピングソートなどが

楽です。

bisect.insortってやつもあるけど？

ごめんなさい。私、bisect_lectやbisect_rightはたまーに使うのですが

insortはほぼつかったことがありません。大抵、対象としているシーケンスの

要素が単純型ではないのが理由です。

備考

とまあ、いろいろ記述したのですが、Pythonのオフィスドキュメントに記載が

あるように、キー関数なども使って、bisectモジュールをモニョモニョする場合は

以下のリンクにある SortedCollection を使う方がとっても楽です。これほんと便利。

SortedCollection « Python recipes « ActiveState Code

参考情報

8.6. bisect — 配列二分法アルゴリズム — Python 3.6.3 ドキュメント

stackoverflow.com

SortedCollection « Python recipes « ActiveState Code

過去の記事については、以下のページからご参照下さい。

サンプルコードは、以下の場所で公開しています。