Necesito obtener los n menores n de una lista en Python. Necesito que esto sea realmente rápido porque está en una parte crítica para el rendimiento y debe repetirse muchas veces.Obtener los n elementos menores de una lista en Python
n generalmente no es mayor que 10 y la lista generalmente tiene alrededor de 20000 elementos. La lista siempre es diferente cada vez que llamo a la función. La clasificación no se puede hacer en su lugar.
Inicialmente, he escrito esta función:
def mins(items, n):
mins = [float('inf')]*n
for item in items:
for i, min in enumerate(mins):
if item < min:
mins.insert(i, item)
mins.pop()
break
return mins
Sin embargo, esta función no puede vencer a un clasificadas simples (elementos) [n] qué tipo de toda la lista. Aquí está mi prueba:
from random import randint, random
import time
test_data = [randint(10, 50) + random() for i in range(20000)]
init = time.time()
mins = mins(test_data, 8)
print 'mins(items, n):', time.time() - init
init = time.time()
mins = sorted(test_data)[:8]
print 'sorted(items)[:n]:', time.time() - init
Resultados:
mins(items, n): 0.0632939338684
sorted(items)[:n]: 0.0231449604034
ordenados() [n] es tres veces más rápido. Creo que esto es porque:
- operación de inserción() es costoso porque las listas de Python no son listas vinculadas.
- ordenado() es una función c optimizada y la mía es pura python.
¿Hay alguna manera de vencer sorted() [: n]? ¿Debo usar una extensión C, o Pyrex o Psyco o algo así?
Gracias de antemano por sus respuestas.
¡Esto es muy rápido! –
Un montón sería mejor; no es necesario ordenar por completo toda la lista para cada inserción, solo un repaso más barato. – erickson
@erickson: Acaba de editarse para agregar que bisect.insort puede tener el mismo efecto. –