Python でソートされたリストを操作する: `bisect` モジュールの魔法

並べ替えられたリストの操作は、少し難しい場合があります。挿入するたびにリストの順序を維持し、リスト内の要素を効率的に検索する必要があります。二分探索は、ソートされたリスト内を検索するための強力なアルゴリズムです。最初から実装するのはそれほど難しくありませんが、時間がかかる場合があります。幸いなことに、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: Within a loop, the function calculates the midpoint (mid) between lo and hi. It then compares the value at mid with the target value you’re looking to insert.

3. Comparison:

* 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. Termination: This process continues, halving the search range each time, until lo equals hi. At this point, lo (or hi) represents the correct index where the target should be inserted to maintain the list's sorted order.

2. Insertion: For the insort function, once the correct index is found using bisect_left, the target is inserted into the list at that position.

This approach ensures that the insertion process is efficient, with a time complexity of O(log n) for the search and O(n) for the insertion due to the list shifting operation. This is significantly more efficient than sorting the list after each insertion, especially for large datasets.

bisect_left code example:

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

insort_left code example:

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)

Conclusion

The bisect module makes working with sorted lists straightforward and efficient. The next time you need to perform binary search or insert elements into a sorted list, remember the bisect module and save yourself time and effort.

以上がPython でソートされたリストを操作する: `bisect` モジュールの魔法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。