python - Python: heapq ヒープをトリミングして X アイテムの長さだけにする

Question

ヒープのトップ X アイテムをヒープとして取得する最速の方法は何でしょうか?

ヒープをX回ポップしてヒープを再構築するよりも良い方法があると思います。

Answer 1

@Ben はすべての点で正しいですが、Python のheapqヒープは最大ヒープではなく最小ヒープです。

newheap = [heappop(oldheap) for _ in range(X)]  # removes from oldheap

通常、それが得られるのと同じくらい良いです。ただし、特に X が とほぼ同じ大きさの場合は、代わりに次のようにすると高速になります。len(oldheap)

newheap = sorted(oldheap)[:X]  # doesn't change oldheap

少なくとも CPython では、 sort メソッドは既に にある半順序を利用して、最小の要素を抽出するoldheapよりも速くリスト全体のソートを完了することができます (ソートに必要な比較は全体的に少なくなり、比較は最もコストのかかる部分です)。この流れの極端な例は、たまたまソート順になっている場合です。次に、並べ替えには比較の総計が必要ですが、繰り返しポップには比較の順序が必要です。heappop()XX == len(oldheap)oldheapX-1X*log(X)