Pythonのリストを部分的にソートするにはどうしたらいいですか？

Question

compiler cache for MSVC（ccacheはgccとよく似ています）を書きました。私がしなければならないことの1つは、キャッシュディレクトリ内の最も古いオブジェクトファイルを削除して、キャッシュをユーザー定義のサイズに調整することです。

# First tuple element is the access time, second tuple element is file size 
items = [ (1, 42341), 
      (3, 22), 
      (0, 3234), 
      (2, 42342), 
      (4, 123) ] 

は今、私はこのリストに部分の並べ替えを行うにはしたいと思います：

は今のところ、私は基本的にそのそれぞれが最終アクセス時間とファイルサイズで、タプルのリストを持っています最初のN個の要素がソートされます（Nは要素の数であり、そのサイズの合計は45000を超えます）。結果は、基本的にはこのようになります。

# Partially sorted list; only first two elements are sorted because the sum of 
# their second field is larger than 45000. 
items = [ (0, 3234), 
      (1, 42341), 
      (3, 22), 
      (2, 42342), 
      (4, 123) ] 

私は本当にソートされていないエントリの順番を気にしない、私はちょうど累積サイズ一定の値を超え、リスト内のN最古のアイテムが必要。

Answer 1

heapqモジュールを使用できます。あなたの条件が満たされるまで、をリストに、その後にheappop()と呼んでください。 heapify()は線形で、対数はheappop()なので、できるだけ早く得ることができます。

heapq.heapify(items) 
size = 0 
while items and size < 45000: 
    item = heapq.heappop(items) 
    size += item[1] 
    print item 

出力：

(0, 3234) 
(1, 42341) 

Answer 2

私は缶詰何も知りませんが、あなたは漸進一端から他端にソートされたリストを構築するあらゆる種類の変種でこれを行うことができますが、これは、十分な要素がソートされたときに停止します。クイックソートは明白な選択でしょう。選択ソートはやりますが、それはひどい種類です。 Heapsortは、Marcoが示唆しているように、配列全体のヒープを沈んだコストとして取ることもあります。 Mergesortはこの方法では使用できませんでした。

クイックソートを具体的に見るには、これまでに配列のどの位までの高さと、それらの要素の合計ファイルサイズを追跡するだけです。各サブソートの終わりに、新しくソートされた要素を追加してそれらの番号を更新します。ソートを放棄してターゲットを通過するとき。

また、パーティションの選択手順を変更することで、パフォーマンスが向上することがあります。配列の小さな部分だけをソートすることを期待しているならば、片側のパーティション要素を好むかもしれません。

Answer 3

部分ソート（the Wikipedia page参照）は、実際のソートよりも効率的です。アルゴリズムはソートアルゴリズムに類似しています。ヒープベースの部分ソートの概要を説明します（ただし、そのページでは最も効率的ではありません）。

最も古いものが必要です。要素がヒープに1つずつ貼り付けられ、ヒープ内の最新の要素があまりにも大きくなると、要素がポップされます。ヒープは小さく保たれているので、要素を挿入したり削除したりすることはほとんどありません。

標準的なケースでは、最小/最大のk要素が必要です。合計条件を満たす最も古い要素が必要なので、total_sizeの変数を維持して合計条件を追跡します。

コード：

import heapq 

def partial_bounded_sort(lst, n): 
    """ 
    Returns minimal collection of oldest elements 
    s.t. total size >= n. 
    """ 
    # `pqueue` holds (-atime, fsize) pairs. 
    # We negate atime, because heapq implements a min-heap, 
    # and we want to throw out newer things. 
    pqueue = [] 
    total_size = 0 

    for atime, fsize in lst: 
     # Add it to the queue. 
     heapq.heappush(pqueue, (-atime, fsize)) 
     total_size += fsize 

     # Pop off newest items which aren't needed for maintaining size. 
     topsize = pqueue[0][1] 
     while total_size - topsize >= n: 
      heapq.heappop(pqueue) 
      total_size -= topsize 
      topsize = pqueue[0][1] 

    # Un-negate atime and do a final sort. 
    oldest = sorted((-priority, fsize) for priority, fsize in pqueue) 

    return oldest 

あなたはこのコードをmicrooptimizeするために行うことができますがいくつかあります。たとえば、最初のいくつかの項目をリストに入力してまとめてまとめてもかまいません。

複雑さはソートよりも優れています。あなたの特定の問題では、返す要素の数、またはキュー内の要素の数を一度に知ることはできません。最悪の場合、リストのほぼすべてをソートします。リストを前処理することで、新しいものや古いものを見つけるのが簡単かどうかを調べることで、これを防ぐことができます。

---

あなたは、削除されていない項目を追跡したい場合は、元のリストの中に二つの「ポインタ」を維持することができます：あなたが処理したものを追跡するための1、およびマーキング1 "フリースペース。アイテムを処理するときは、リストからそのアイテムを削除し、ヒープからアイテムを捨てるときは、リストに戻します。リストには、ヒープにないアイテムと最後にNoneのエントリが追加されます。