Как я могу частично отсортировать список 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)

Answer 2

Я не знаю ничего консервированного, но вы могли бы сделать это с вариантом любого вида, который постепенно создает отсортированный список от одного конца до другого, но который просто останавливается, когда отсортировано достаточно элементов.Быстрая сортировка будет очевидным выбором.Сортировка выбора подойдет, но это ужасный вид.Heapsort, как предполагает Марко, также сделает это, принимая кучу всего массива за непогашенную стоимость.Mergesort не может быть использован таким образом.

Чтобы взглянуть конкретно на быструю сортировку, вам просто нужно отследить высокую отметку того, как далеко в массив был отсортирован до сих пор, и общий размер файла техэлементы.В конце каждой подсортировки вы обновляете эти числа, добавляя вновь отсортированные элементы.Откажитесь от сортировки, когда она пройдет цель.

Вы также можете обнаружить, что производительность была улучшена путем изменения шага выбора раздела.Вы можете предпочесть односторонние элементы разбиения, если вы планируете сортировать только небольшую часть массива.

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 записей в конце.