Python のデータ構造とアルゴリズム - 順序付きリストの維持と二分

[[402075]]

序文

Bisect は、リストをソートしたままリストに要素を挿入するアルゴリズムを実装します。

この記事では、bisectライブラリを使用してリストを効率的に操作する方法を詳しく紹介します。

注文された挿入物

まず、bisect ライブラリがリスト挿入をどのように実装するかを見てみましょう。具体的なコードは次のとおりです。

インポート二分
 
 a = [7, 5, 4, 1, 9, 8, 2, 3, 6, 0, 5]
印刷(a)
新しい_a = []
 aのiの場合:
    位置 = bisect.bisect(new_a, i)
    bisect.insort(new_a, i)
    print(位置、new_a)

実行後の効果は次のようになります。

ご覧のとおり、bisect は挿入用に自動的にソートされ、position は挿入のインデックス位置になります。もちろん、このような挿入の場合は、リストを直接構築してから並べ替える方が速い場合があります。ただし、これは短いリストの場合にのみ非常に高速です。非常に長いリストの場合、上記の挿入ソートを使用すると、特に 2 つのリスト メンバーを比較すると計算オーバーヘッドが大きくなる場合に、時間とメモリを大幅に節約できます。

重複値の処理

実際のリスト処理では、重複した値を処理する場合があります。上記のように、デフォルトでは重複値の右側に余分な 5 が挿入されます。これは、insort_right() 関数を使用するのと同じです。同様に、左側では insort_left() 関数を使用できます。

インポート二分
 
 a = [7, 5, 4, 1, 9, 8, 2, 3, 6, 0, 5]
印刷(a)
新しい_a = []
 aのiの場合:
    位置 = bisect.bisect_left(new_a, i)
    bisect.insort_left(new_a, i)
    print(位置、new_a)

実行後の効果は次のようになります。

読者は上の 2 つの画像を比較すると、最後の行のインデックスが変わることがわかります。ご覧のとおり、1 つは 6 で、もう 1 つは 5 です。積極的に変更したため、重複した値はデフォルトで左側に挿入されます。