python - Python のリストの n 個の最高値

Question

特定のリストの n 個の最高値を取得する最良の方法は何ですか? の長さに比べて n がかなり小さい場合、alist以下よりも効率的なものはありますか?

alist.sort()
return alist[0:n]

Answer 1

heapqモジュールを使用します：

import heapq

return heapq.nlargest(n, l)        

比較的少数のn要素を探している場合は、ヒープ キューを使用する方がフル ソートよりも効率的です。がn大きいsorted(l)[-n:]ほど効率的です。実装はこれらの条件をテストし、が と等しいかそれより大きいと判断できる場合はheapq.nlargest()using に切り替えます。sorted()nlen(l)

heapqモジュールはリストをインプレースで変更することに注意してください(heapq.heapify()がリストで呼び出されます)。

Answer 2

あなたの方法は非常に簡潔ですが、最も効率的ではないかもしれません。1つの可能性は、決定論的選択アルゴリズムを実装することです（ここではテキストで説明されており、ここではビデオで説明されています）、必要な値に対してそれを呼び出します。これにより、全体的に O(n) 操作が可能になります。リストを調べることについて話しているので、大幅に改善できるとは思いません。