Python
python3
PythonDay 4

Python標準ライブラリ:順序維持のbisect

はじめに

ソートされたリストに対してソート順序を保ったまま値を挿入したいと思う場面は少なくないはずです。そういった場面に 出くわしたときにappendしてsortしているとパフォーマンスはよくないです。Pythonのlistのソートの平均時間計算量は$O(n \log{n})$です。要素数が増えてきたり、毎度ソートしていたりすると実行速度にも影響がでてくると思います。

A = [1, 12, 23, 38, 54, 66, 76, 98]
# Aの順序を保ったまま'46'を挿入したい
A.append(46)
A.sort()
print(A)
# [1, 12, 23, 38, 46, 54, 66, 76, 98]

今回は、上記の方法よりも効率よく、ソートされたリストに対してソート順序を保ったまま値を挿入するためのPython標準ライブラリ「bisect」について説明します。

bisectとは

「bisect」は「二分探索」を利用することで効率よく、リストをソートされた状態に保つことをサポートするためのPython標準ライブラリです。二分探索(binary search)はソート済みの配列に対する探索アルゴリズムです。知っている人は多いと思うのでアルゴリズム自体の詳細は割愛しますが、このアルゴリズムでの時間計算量は$O(\log{n})$です。上記のソートと比べるてパフォーマンスが向上する理由は、リストの順序を保つための計算量が少なくて済むからです。

bisectはPython標準ライブラリなのでなにもインストールせずにimportするだけで使えます。

import bisect

使い方

実際にbisectの使い方について説明します。bisectには挿入箇所を探索する関数(bisect)と探索と挿入を同時に行う(insort)の主に2つの関数が存在しています。

bisect系は以下の3つの関数が存在しています。

  • bisect_left
  • bisect_right
  • bisect

insort系は以下の3つの関数が存在しています。

  • insort_left
  • insort_right
  • insort

それぞれの関数について説明します。

bisect_left

bisect.bisect_left(a, x, lo=0, h=len(a))

引数は以下になります(他の関数においても同様)
a: ソート済みリスト
x: 挿入したい値
lo: 探索範囲の下限
hi: 探索範囲の上限
(lo, hiはスライスと同様の指定方法)

bisect_leftはソートされたリストaに対して順序を保ったままxを挿入できる箇所を探索します。leftが示す通り、aにすでにxが存在している場合は、挿入箇所は既存のxよりも左側になります。また、lo, hiを指定することで探索範囲を絞り込むことも可能です。デフォルトはaの全体が探索対象です。

A = [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]
print(A)
index = bisect.bisect_left(A, 3) # 2 最も左(前)の挿入箇所が返ってきている
A.insert(index, 3)
print(A) # [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]

# 探索範囲を絞り込む
A = [1, 2, 3, 3, 3, 0, 0, 0, 0, 0, 0]
index = bisect.bisect_left(A, 3, 0, 5)
print(index)# 2

bisect_right

名前からも見当がつくように、bisect_leftのxの挿入箇所が既存のxより右になったものです。

A = [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]
print(A)
index = bisect.bisect_right(A, 3) # 5

bisect

こいつはbisect_rightのaliasなので、明示的に書くという意味では使用場面はないかもしれません。

insort_left

insort_left(a, x)はa.insert(bisect.bisect_left(a, x))と同じです。つまり、探索を行い、挿入までを行います。

A = [1, 2, 3, 3, 3, 4, 4, 6, 6, 6, 6]
bisect.insort(A, 3) # [1, 2, 3, 3, 3, 3, 4, 4, 6, 6, 6, 6]

insort_right

insort_right(a, x)はa.insert(bisect.bisect_right(a, x))と同じです。

insort

こいつもinsort_rightのaliasです...

使用例

最長増加部分列問題では動的計画法と二分探索を用いることにより効率的に($O(n\log{n})$)最長増加部分列を求めることができます。

def lis(n, A):
    L = [0 for i in range(n + 1)]
    L[0] = A[0]
    length = 1
    for i in range(1, n):
        if L[length - 1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            index = bisect.bisect_left(L, A[i], 0, length)
            L[index] = A[i]
    return length

また、公式ドキュメントでは以下のように成績評価についての実装例が挙げられています。

 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 — Array bisection algorithm