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

Question

我写了一个编译器缓存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)