我该如何对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个最旧的条目。

- Frerich Raabe

---

如果都被排序了，这是个问题吗？还是你只是想让事情更快？ - Ishpeck

@Ishpeck：我只是试图保持事情的快速。目前速度已经足够快，但列表可能会比我这里列出的要大得多；如果未来需要，我正在研究优化的潜力。 - Frerich Raabe

Answer 1

您可以使用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)

- moinudin

Answer 2

我不知道有任何现成的东西，但是你可以使用一种变体，从一个端点开始增量地构建已排序列表，但当已排序元素足够时就停止。快速排序是显而易见的选择。选择排序也可以，但它是一个糟糕的排序算法。正如Marco建议的，堆排序也可以，将整个数组的堆化作为沉没成本。归并排序不能用这种方式。

具体来看快排，你只需要跟踪已经排序了多远的位置以及这些元素的总文件大小。在每次子排序结束时，通过添加新排序的元素来更新这些数字。当它超过目标时放弃排序。

您还可以通过更改分区选择步骤来提高性能。如果您只希望对数组的一小部分进行排序，则可能更喜欢倾斜分区的元素。

- Tom Anderson

Answer 3

部分排序（参见维基百科页面）比实际排序更有效率。算法类似于排序算法。我将概述基于堆的部分排序（尽管它不是该页面上最有效的算法）。

您想要最旧的元素。您逐个将元素放入堆中，并在堆变得太大时弹出堆中最新的元素。由于堆保持较小，因此插入和删除元素的成本较低。

在标准情况下，您想要最小/最大的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条目。

- leewz