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

Question

我写了一个compiler cache for MSVC (很像 ccache 对于 gcc )。我必须做的一件事是删除缓存目录中最旧的对象文件，以将缓存修剪为用户定义的大小。

现在，我基本上有一个元组列表，每个元组都是上次访问时间和文件大小:

# 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模块。在列表中调用 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)