ソートされたリストの操作は、少し難しい場合があります。挿入するたびにリストの順序を維持し、リスト内の要素を効率的に検索する必要があります。二分探索は、ソートされたリスト内を検索するための強力なアルゴリズムです。最初から実装するのはそれほど難しくありませんが、時間がかかる場合があります。幸いなことに、Python は bisect モジュールを提供しており、これによりソートされたリストの処理がはるかに簡単になります。

二分探索とは何ですか?

二分探索は、ソートされた配列内でターゲット値の位置を見つけるアルゴリズムです。電話帳で名前を検索していると想像してください。最初のページから開始するのではなく、本の途中から開始して、名前のアルファベット順が中央のページよりも大きいか小さいかに基づいて、前半と後半のどちらで検索を続けるかを決定する可能性があります。二分探索も同様の方法で動作します。二分探索は 2 つのポインタから開始され、1 つはリストの先頭に、もう 1 つはリストの末尾に配置されます。次に、中央の要素が計算され、ターゲットと比較されます。

bisect モジュール: ソートされたリスト操作の簡素化

二分探索は効果的ですが、毎回実装を書き出すのは面倒な場合があります。しかし、たった 1 行のコードで同じ操作を実行できるとしたらどうなるでしょうか?そこで Python の bisect モジュールが登場します。Python の標準ライブラリの一部である bisect は、挿入のたびに並べ替える必要がなく、並べ替えられたリストを維持するのに役立ちます。これは、単純な二分アルゴリズムを使用して行われます。

bisect モジュールは、bisect と insort という 2 つの主要な機能を提供します。 bisect 関数は、リストのソートを維持するために要素を挿入するインデックスを見つけます。一方、insort は、ソートされた順序を維持しながら要素をリストに挿入します。

bisect モジュールの使用: 実践的な例

モジュールをインポートすることから始めましょう:

import bisect

例 1: 並べ替えられたリストへの数値の挿入

ソートされた数値リストがあるとします:

data = [1, 3, 5, 6, 8]

リストを並べ替えたまま新しい番号を挿入するには、単に次のように使用します:

bisect.insort(data, 7)

このコードを実行すると、データは次のようになります:

[1, 3, 5, 6, 7, 8]

例 2: 挿入ポイントの検索

実際に数値を挿入せずに、数値が挿入される場所を知りたいだけの場合はどうすればよいでしょうか? bisect_left 関数または bisect_right 関数を使用できます:

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

これは、リストをソートしておくためにインデックス 2 に数値 4 を挿入する必要があることを示しています。

例 3: 動的リストでのソート順序の維持

動的に増加するリストを管理していて、並べ替えられた状態を維持しながら要素を挿入する必要があるとします。

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

これにより、要素が挿入されるときに各ステップでリストが出力されます:

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

例 4: カスタム オブジェクトでの bisect の使用

タプルなどのカスタム オブジェクトのリストがあり、特定の基準に基づいてそれらを挿入するとします。

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

または、各タプルの 2 番目の要素に基づいて挿入することもできます:

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

二分するアクション: 言葉の検索

二分モジュールは数値に限定されません。文字列、タプル、文字などのリストを検索する場合にも役立ちます。
たとえば、ソートされたリストから単語を検索するには:

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

または、特定の接頭辞を持つ単語グループ内の最初の単語を検索するには:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix   'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

ただし、 bisect_left はターゲットがリストに存在するかどうかではなく、ターゲットが挿入されるインデックスを返すことに注意してください。

bisect と insort の変形

このモジュールには、右側のバリアント (bisect_right と insort_right) も含まれています。これらの関数は、要素がすでにリストに存在する場合、その要素を挿入する右端のインデックスを返します。たとえば、bisect_right は、ターゲットがリスト内にある場合、ターゲットより大きい最初の要素のインデックスを返しますが、insort_right はその位置に要素を挿入します。

ボンネットの下で二分する

bisect モジュールの威力は、二分探索アルゴリズムの効率的な実装にあります。たとえば、 bisect.bisect_left を呼び出すと、関数は基本的にリストに対して二分検索を実行して、新しい要素の正しい挿入ポイントを決定します。

内部での仕組みは次のとおりです:

1. 初期化: 関数は、リスト内の検索範囲の下限と上限を表す 2 つのポインター lo と hi で始まります。最初に、lo はリストの先頭 (インデックス 0) に設定され、hi はリストの末尾 (リストの長さに等しいインデックス) に設定されます。ただし、カスタムの lo 値と hi 値を指定して、リストの特定の範囲内を検索することもできます。

2. Bisection: ループ内で、関数は lo と hi の中点 (mid) を計算します。次に、mid の値と挿入しようとしているターゲット値を比較します。

3. 比較：

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid   1`.

1. 終了: このプロセスは、lo が hi に等しくなるまで、毎回検索範囲を半分にして継続します。この時点で、lo (または hi) は、リストのソート順を維持するためにターゲットを挿入する必要がある正しいインデックスを表します。

2. 挿入: insort 関数の場合、bisect_left を使用して正しいインデックスが見つかると、ターゲットがリストのその位置に挿入されます。

このアプローチにより、リストのシフト操作による検索の時間計算量が O(log n)、挿入の時間計算量が O(n) になるため、挿入プロセスが効率的になります。これは、特に大規模なデータセットの場合、挿入のたびにリストを並べ替えるよりも大幅に効率的です。

bisect_left コード例:

    if lo 



insort_left コード例:


def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)





  
  
  結論


bisect モジュールを使用すると、ソートされたリストを簡単かつ効率的に操作できます。次回バイナリ検索を実行したり、ソートされたリストに要素を挿入したりする必要があるときは、bisect モジュールを覚えておくと、時間と労力を節約できます。