[Python] How can I partially sort a Python list?

I wrote a compiler cache for MSVC (much like ccache for gcc). One of the things I have to do is to remove the oldest object files in my cache directory to trim the cache to a user-defined size.

Right now, I basically have a list of tuples, each of which is the last access time and the file size:

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


Now I'd like to do a partial sort on this list so that the first N elements are sorted (where N is the number of elements so that the sum of their sizes exceeds 45000). The result should be basically this:

# 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) ]


I don't really care about the order of the unsorted entries, I just need the N oldest items in the list whose cumulative size exceeds a certain value.

Continue reading...