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

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

二分探索とは何ですか?

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

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

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

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

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

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

リーリー

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

並べ替えられた数値のリストがあるとします:

リーリー

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

リーリー

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

リーリー

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

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

リーリー

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

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

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

リーリー

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

リーリー

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

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

リーリー

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

リーリー

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

二等分モジュールは数値に限定されません。文字列、タプル、文字などのリストの検索にも役立ちます

たとえば、ソートされたリストから単語を検索するには:

リーリー

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

リーリー

ただし、 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:

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:

insort_left code example:

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 サイトの他の関連記事を参照してください。