この記事では、Pythonでソートされたリストに要素を追加する際、並び順を保ったまま要素を挿入する方法を解説します。
リストに要素を挿入するたびにsort()メソッドで並び替えをすると非常に効率が悪いのでbisectモジュールを使いましょう！
bisectモジュールは二分法アルゴリズムを使っているので要素がたくさんあるリストではより効率よく処理することができます。
それでは、並び順を保ったまま要素を挿入する方法を見ていきましょう！
bisectモジュールのinsert系の関数を使うことでリストに並び順で要素を追加することができます。使用するリストはあらかじめソートしておく必要があります。
bisect.insort_left(a, x, lo=0, hi=len(a))
bisect.insort_right(a, x, lo=0, hi=len(a))
bisect.insort(a, x, lo=0, hi=len(a))リスト内に追加する値と同等の要素が存在する場合、insort_left()は、同じ値の左側に挿入してinsort_right()は、同じ値の右側に挿入します。
insort()は、insort_right()のエイリアスです。
lo引数とhi引数を指定することで要素を挿入する範囲を設定できます。
サンプル
試しに適当なリストに要素を並び順で追加してみましょう。
import bisect
nums = [2, 4, 6, 1, 5]
# あらかじめソートしておく
nums.sort()
print(nums)
# 要素の追加
bisect.insort_left(nums, 3)
bisect.insort_right(nums, 3)
print(nums)実行結果
[1, 2, 4, 5, 6]
[1, 2, 3, 3, 4, 5, 6]範囲を指定した例も見てみましょう！
import bisect
nums = [2, 4, 6, 1, 5]
nums.sort()
print(nums)
bisect.insort(nums, 3, 3, 4)
print(nums)実行結果
[1, 2, 4, 5, 6]
[1, 2, 4, 3, 5, 6]挿入する要素(3)が指定した範囲(nums[3]〜nums[4])の要素(5と6)と比較され、値が挿入されたので5の前に配置されました。
並び順で要素を挿入できる場所を探してインデックスを取得することができます。こちらの関数を使用する際にもリストはあらかじめソートしておく必要があります。
bisect.bisect_left(a, x, lo=0, hi=len(a))
bisect.bisect_right(a, x, lo=0, hi=len(a))
bisect.bisect(a, x, lo=0, hi=len(a))戻り値がインデックスなだけで使い方はinsortと変わりません。
import bisect
nums = [2, 4, 6, 1, 5, 3]
nums.sort()
print(nums)
print(bisect.bisect_left(nums, 3))
print(bisect.bisect_right(nums, 3))実行結果
[1, 2, 3, 4, 5, 6]
2
3毎回リストのソートを使うコードとbisectを使ったコードの速度を比べてみましょう。
import bisect
import random
import time
nums = []
s_t = time.time()
for i in range(10000):
r = random.randrange(10000)
nums.append(r)
nums.sort()
print(f'TIME: {time.time() - s_t} [sec]')
nums = []
s_t = time.time()
for i in range(10000):
r = random.randrange(10000)
bisect.insort(nums, r)
print(f'TIME: {time.time() - s_t} [sec]')実行結果
TIME: 0.4850950241088867 [sec]
TIME: 0.049118995666503906 [sec]約10分の1ぐらいの時間で処理することができました。
この記事では、リストの並び順を保ったまま要素を挿入する方法を解説しました。
リストなどのコレクションは使い方次第で効率がかなり変わるので注意して使いましょう！
頻繁に使用するモジュールではないですが知っておくと便利です。
それでは今回の内容はここまでです。ではまたどこかで〜( ・∀・)ﾉ
Linkbisect --- 配列二分法アルゴリズム — Python ドキュメント