python - 要素を読みながらリストをソートしておく方法

Question

要素をリストに読み込み、既存のソートされたリストで新しい要素の場所を検索してそこに挿入することとは別に、リストをソートしたままにする効率的な方法は何ですか?

Answer 1

特殊なデータ構造を使用します。Python では、bisectモジュールを自由に使用できます。

このモジュールは、挿入のたびにリストをソートすることなく、ソートされた順序でリストを維持するためのサポートを提供します。コストのかかる比較操作を伴う項目の長いリストの場合、これはより一般的なアプローチよりも改善される可能性があります。モジュールが呼び出されるのbisectは、基本的な二分アルゴリズムを使用して作業を行うためです。

Answer 2

の関数を探していますheapq。

このモジュールは、優先キュー アルゴリズムとも呼ばれるヒープ キュー アルゴリズムの実装を提供します。

Answer 3

@Aswinのコメントは興味深いです。項目を挿入するたびにソートする場合、への呼び出しsort()は通常の O(n*log(n)) ではなく O(n) になります。これは、sort(timsort) の実装方法によるものです。

ただし、これに加えて、リストに沿って一連の要素を移動してスペースを作る必要があります。これも O(n) であるため、全体として -.sort()毎回の呼び出しは O(n) です。

このシフトは常に必要であるため、ソートされたリストを O(n) よりも適切に保持する方法はありません。

実際のリストが必要ない場合は、(@Ignacio の回答で述べたように) heapq が必要なプロパティを効率的にカバーすることがよくあります。

それ以外の場合は、おそらく、多くのツリー データ構造の 1 つが、リストよりも目的に適していることがわかります。