bisect – ソート済みのリストを保持する¶
| 目的: | リストへ要素が追加されたときにソートせずにリスト内の順序を保持する |
|---|---|
| 利用できるバージョン: | 1.4 |
bisect モジュールは、ソート済みのリストへ挿入する要素のアルゴリズムを実装します。これはリストを繰り返しソートする、もしくは作成後に巨大なリストを明示的にソートするよりもかなり効率が良いです。
サンプル¶
ソート済みのリストへ要素を挿入する bisect.insort() を使用する簡単なサンプルを見てみましょう。
import bisect
import random
# ループの実行時に同じ疑似乱数になるように定数を使用する
random.seed(1)
# 20個の乱数を生成してソート順序を保持してリストへ挿入する
l = []
for i in range(1, 20):
r = random.randint(1, 100)
position = bisect.bisect(l, r)
bisect.insort(l, r)
print '%2d %2d' % (r, position), l
このスクリプトの実行結果は次のようになります。
$ python bisect_example.py
14 0 [14]
85 1 [14, 85]
77 1 [14, 77, 85]
26 1 [14, 26, 77, 85]
50 2 [14, 26, 50, 77, 85]
45 2 [14, 26, 45, 50, 77, 85]
66 4 [14, 26, 45, 50, 66, 77, 85]
79 6 [14, 26, 45, 50, 66, 77, 79, 85]
10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
44 4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
77 9 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
1 0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
45 7 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85]
73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
23 4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95]
91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95]
1番目の列は生成された乱数を、2番目の列はリストへ挿入された位置を表示します。行毎にカレントのソート済みリストも表示します。
これは簡単なサンプルで、いま扱っているデータ量では、単純にリストを作成してソートする方が速いかもしれません。しかし、巨大なリストでは、このような挿入ソートアルゴリズムを使用すると処理時間とメモリが節約できます。
上述した結果セットは重複する値(45 と 77)を含んでいることに気付きます。 bisect モジュールは重複値を扱うのに2つの方法を提供します。新たな値が既存の値の左側か右側に挿入されます。 insert() 関数は、実際に既存の値の後に挿入する insort_right() のエイリアスです。対応する insort_left() は既存の値の前に挿入します。
insort_right() と insort_left() で同じデータを扱う場合、結局は同じソート済みのリストになりますが、重複した値の挿入位置が違っていることに気付きます。
import bisect
import random
# シードをリセットする
random.seed(1)
# bisect_left と insort_left を使用する
l = []
for i in range(1, 20):
r = random.randint(1, 100)
position = bisect.bisect_left(l, r)
bisect.insort_left(l, r)
print '%2d %2d' % (r, position), l
$ python bisect_example2.py
14 0 [14]
85 1 [14, 85]
77 1 [14, 77, 85]
26 1 [14, 26, 77, 85]
50 2 [14, 26, 50, 77, 85]
45 2 [14, 26, 45, 50, 77, 85]
66 4 [14, 26, 45, 50, 66, 77, 85]
79 6 [14, 26, 45, 50, 66, 77, 79, 85]
10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
44 4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
77 8 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
1 0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
45 6 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85]
73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
23 4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95]
91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95]
Python 実装に加えて、より高速な C 言語実装も利用できます。C 言語実装が存在するなら bisect をインポートするときにピュア Python 実装がオーバーライドされます。
