¿Cómo puedo ordenar parcialmente una lista de Python?

Question

Escribí un compiler cache for MSVC (muy parecido a ccache para gcc). Una de las cosas que tengo que hacer es eliminar los archivos de objeto más antiguos en mi directorio de caché para recortar el caché a un tamaño definido por el usuario.

En este momento, básicamente, tienen una lista de tuplas, cada una de las cuales es la última vez que el acceso y el tamaño de archivo:

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

Ahora me gustaría hacer un parcial de tipo en esta lista de modo que los primeros N elementos están ordenados (donde N es la cantidad de elementos para que la suma de sus tamaños supere los 45000). El resultado debe ser básicamente el siguiente:

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

Realmente no importa el orden de las entradas no ordenados, sólo necesito los artículos N más antiguos de la lista cuyo tamaño acumulado excede un cierto valor.

Answer 1

Puede usar el módulo heapq. Llame al heapify() en la lista, seguido por heappop() hasta que se cumpla con su condición. heapify() es lineal y heappop() logarítmico, por lo que es probable que sea lo más rápido posible.

heapq.heapify(items) 
size = 0 
while items and size < 45000: 
    item = heapq.heappop(items) 
    size += item[1] 
    print item 

Salida:

(0, 3234) 
(1, 42341) 

Answer 2

No sé nada de lata, pero se puede hacer esto con una variante de cualquier tipo, que construye incrementalmente la lista ordenada de un extremo al otro, pero que simplemente se detiene cuando se han ordenado suficientes elementos. Quicksort sería la opción obvia. El tipo de selección sería bueno, pero es un tipo terrible. Heapsort, como sugiere Marco, también lo haría, tomando el heapify de todo el conjunto como un costo hundido. Mergesort no se pudo usar de esta manera.

Para ver específicamente el quicksort, simplemente necesitaría rastrear una marca de agua máxima de hasta qué punto en la matriz se ha ordenado hasta el momento, y el tamaño total del archivo de esos elementos. Al final de cada clasificación secundaria, actualiza esos números al agregar los elementos recién ordenados. Abandona el género cuando pasa el objetivo.

También puede encontrar que el rendimiento se mejoró al cambiar el paso de selección de partición. Es posible que prefiera elementos de partición asimétricos si solo espera clasificar una pequeña fracción de la matriz.

Answer 3

La clasificación parcial (consulte the Wikipedia page) es más eficiente que la clasificación real. Los algoritmos son análogos a los algoritmos de clasificación. Describiré el tipo parcial basado en el montón (aunque no es el más eficiente en esa página).

Quieres las más antiguas. Pega los elementos en un montón, uno por uno, y saca el elemento más nuevo en el montón cuando se vuelve demasiado grande. Como el montón se mantiene pequeño, no se paga tanto para insertar y eliminar elementos.

En el caso estándar, desea los elementos más pequeños/más grandes k. Desea los elementos más antiguos que satisfagan una condición total, así que realice un seguimiento de la condición total manteniendo una variable total_size.

Código:

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 

Hay algunas cosas que puede hacer para microoptimize este código.Por ejemplo, puede completar la lista con los primeros elementos y heapify todo a la vez.

La complejidad podría ser mejor que la de la clasificación. En su problema particular, no sabe la cantidad de elementos que devolverá, o incluso cuántos elementos podrían estar en la cola a la vez. En el peor de los casos, ordena casi toda la lista. Es posible que pueda evitar esto al preprocesar la lista para ver si es más fácil encontrar el conjunto de cosas nuevas o el conjunto de cosas viejas.

---

Si desea realizar un seguimiento de los elementos que están y no se quitan, se puede mantener dos "punteros" en la lista original: uno para realizar un seguimiento de lo que haya procesado, y uno que marca el "espacio libre. Al procesar un elemento, bórrelo de la lista y, cuando tire un artículo del montón, vuelva a colocarlo en la lista. La lista terminará con los elementos que no están en el montón, más algunas entradas None al final.