如何对Python列表进行部分排序？

Question

我写了一个MSVC的编译缓存（类似于gcc的ccache）。我需要做的一件事就是从我的缓存目录中删除最旧的对象文件，以便把缓存控制在用户设定的大小内。

现在，我基本上有一个元组的列表，每个元组包含最后访问时间和文件大小：

# 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

部分排序（可以参考维基百科页面）比完全排序要高效得多。它的算法和排序算法类似。我将简单介绍基于堆的部分排序方法（虽然这不是页面上最有效的方式）。

假设你想找出最旧的元素。你可以把这些元素一个一个放进一个堆里，当堆里的元素太多时，就把最新的元素弹出去。因为堆的大小保持得比较小，所以在插入和删除元素时花费的时间就会少一些。

在一般情况下，你可能想要最小或最大的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

你可以做一些小优化来提高这段代码的效率。例如，可以先把前几个元素填入列表，然后一次性进行堆化。

这种方法的复杂度可能比完全排序要好。在你的具体问题中，你可能不知道最终会返回多少个元素，或者一次队列中可能有多少个元素。在最坏的情况下，你可能几乎要对整个列表进行排序。你可以通过预处理列表来判断是找新元素更容易，还是找旧元素更容易，从而避免这种情况。

---

如果你想跟踪哪些元素被移除，哪些没有，你可以在原始列表中保持两个“指针”：一个用来跟踪你处理过的元素，另一个用来标记“空闲”空间。在处理一个元素时，从列表中删除它，而当从堆中丢弃一个元素时，再把它放回列表。最终，列表中会留下不在堆中的元素，以及一些末尾的None条目。

Answer 2

我不知道有没有现成的解决方案，但你可以用一种变体的方法，逐步从一端建立一个排序好的列表，直到足够的元素被排序为止。快速排序是个不错的选择。选择排序也可以用，但效果很差。正如Marco所建议的，堆排序也可以做到，前提是把整个数组的堆化视为一个固定成本。归并排序就不适合这样使用了。

具体来说，如果用快速排序，你只需要跟踪一下已经排序到数组的哪个位置，以及这些元素的总大小。在每次子排序结束时，更新这些数字，把新排序的元素加进去。当排序的元素超过目标时，就可以停止排序了。

你可能还会发现，通过改变分区选择的步骤，性能会有所提升。如果你只打算排序数组的一小部分，可能会更倾向于选择不均匀的分区元素。

Answer 3

你可以使用 heapq 这个模块。首先对列表调用 heapify()，然后一直使用 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)