¿El método más rápido para obtener k números más pequeños en una lista no clasificada de tamaño N en python?

¿Cuál es el método más rápido para obtener los k números más pequeños en una lista no clasificada de tamaño N usando python?
¿Es más rápido ordenar la lista grande de números y luego obtener los k números más pequeños,
¿O para obtener los k números más pequeños buscando el mínimo en la lista k veces, asegurándose de que eliminas el mínimo encontrado de la búsqueda antes de la próxima búsqueda?

Podrías usar una cola de stack; puede darle los K números más grandes o más pequeños de una lista de tamaño N en tiempo O (NlogK).

La biblioteca estándar de Python incluye el módulo heapq , completo con una función heapq.nsmallest() implementada:

 import heapq k_smallest = heapq.nsmallest(k, input_list) 

Internamente, esto crea un montón de tamaño K con los primeros K elementos de la lista de entrada, luego iterando sobre los elementos NK restantes, empujando cada uno hacia el montón, y luego sacando el más grande. Tal empuje y pop toma tiempo de registro K, haciendo que la operación general O (NlogK).

La función también optimiza los siguientes casos de borde:

  • Si K es 1, en su lugar se usa la función min() , que le da un resultado O (N).
  • Si K> = N, la función utiliza la clasificación en su lugar, ya que O (NlogN) vencería a O (NlogK) en ese caso.

Una mejor opción es usar el algoritmo de selección introselect , que ofrece una opción O (n). La única implementación que conozco es la función numpy.partition() :

 import numpy # assuming you have a python list, you need to convert to a numpy array first array = numpy.array(input_list) # partition, slice back to the k smallest elements, convert back to a Python list k_smallest = numpy.partition(array, k)[:k].tolist() 

Además de requerir la instalación de numpy , esto también toma N memoria (versus K para heapq ), ya que se crea una copia de la lista para la partición.

Si solo quería índices, puede usar, para cualquiera de las dos variantes:

 heapq.nsmallest(k, range(len(input_list)), key=input_list.__getitem__) # O(NlogK) numpy.argpartition(numpy.array(input_list), k)[:k].tolist() # O(N) 

EDITAR: esto supone que la lista es inmutable. Si la lista es una matriz y se puede modificar, hay métodos lineales disponibles.

Puede reducir la complejidad a O(n * log k) utilizando un montón de tamaño k + 1 .

  1. Inicialmente obtener los primeros k elementos en un mínimo de stack.
  2. Para cada elemento posterior, agregue el elemento como una hoja y heapify.
  3. Reemplace el último elemento con el siguiente elemento.

Heapify se puede hacer en tiempo logarítmico y, por lo tanto, la complejidad del tiempo es la anterior.

Es posible que desee echar un vistazo a heapq :

 In [109]: L = [random.randint(1,1000) for _ in range(100)] In [110]: heapq.nsmallest(10, L) Out[110]: [1, 17, 17, 19, 24, 37, 37, 45, 63, 73] 

Si no es necesario ordenar la lista de los kth números más pequeños, esto se puede hacer en tiempo O (n) con un algoritmo de selección como introselect . La biblioteca estándar no viene con una, pero NumPy tiene numpy.partition para el trabajo:

 partitioned = numpy.partition(l, k) # The subarray partitioned[:k] now contains the k smallest elements. 

Puedes hacerlo en O(kn) con un algoritmo de selección . Una vez que kn >= n log n , cambie a ordenación. Dicho esto, la constante en el algoritmo de selección tiende a ser mucho más alta que la de quicksort, por lo que realmente necesita comparar i (kn) y j (n log n) . En la práctica, generalmente es más conveniente simplemente ordenar, a menos que esté tratando con n grande o muy pequeña.

Edición: ver comentarios. En realidad es mucho mejor.

Usar nsmallest números en heapq es menos código, pero si está buscando implementarlo usted mismo, esta es una forma simple de hacerlo. Esta solución requiere recorrer los datos una sola vez, pero dado que heappush y heappop se ejecutan en O (log n), este algoritmo funcionaría mejor en números más pequeños de k.

 import heapq def getsmallest(arr, k): m = [-x for x in l[:k]] heapq.heapify(m) for num in arr[5:]: print num, m heapq.heappush(m, max(-num, heapq.heappop(m))) return m if __name__ == '__main__': l = [1,2,3,52,2,3,1] print getsmallest(l, 5)