tutorial - Obtener los n elementos menores de una lista en Python

pandas read text

Question

Necesito obtener n menos números 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.

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, escribí 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

Pero esta función no puede vencer a un simple ordenado (elementos) [: n] que ordena la lista completa. 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

sorted () [: n] es tres veces más rápido. Yo creo que esto es porque:

1. La operación de inserción () es costosa porque las listas de Python no son listas vinculadas.
2. sorted () es una función c optimizada y la mía es python pura.

¿Hay alguna forma de vencer sorted () [: n]? ¿Debería usar una extensión C, o Pyrex o Psyco o algo así?

Gracias de antemano por sus respuestas.

Answer 1

Me gusta la idea de pila de Erickson. Tampoco conozco Python, pero parece que hay una solución enlatada aquí: heapq - Algoritmo de cola de montón

Answer 2

Si la velocidad es de gran preocupación, el método más rápido será con c. Psyco tiene un costo inicial, pero puede llegar a ser bastante rápido. Recomendaría Cython para python -> c compilación (un más actualizado para pf Pyrex).

Codificarlo a mano en c sería lo mejor y te permitirá usar estructuras de datos específicas para tu dominio problemático.

Pero nota:

"Compilar el algoritmo incorrecto en C puede no ser más rápido que el algoritmo correcto en Python" @ S.Lott

Quería agregar el comentario de S.Lott para que se note. Python es un excelente lenguaje de prototipos, donde puedes resolver un algoritmo que luego intentas traducir a un lenguaje de nivel inferior.

Answer 3

Una posibilidad es usar el módulo bisect :

import bisect
def mins(items, n):
mins = [float(''inf'')]*n
for item in items:
bisect.insort(mins, item)
mins.pop()
return mins

Sin embargo, es solo un poco más rápido para mí:

mins(items, n): 0.0892250537872
sorted(items)[:n]: 0.0990262031555

Usar psyco lo acelera un poco más:

import bisect
import psyco
psyco.full()
def mins(items, n):
mins = [float(''inf'')]*n
for item in items:
bisect.insort(mins, item)
mins.pop()
return mins

Resultado:

mins(items, n): 0.0431621074677
sorted(items)[:n]: 0.0859830379486

Answer 4

En realidad quieres una secuencia ordenada de minutos.

mins = items[:n]
mins.sort()
for i in items[n:]:
if i < mins[-1]:
mins.append(i)
mins.sort()
mins= mins[:n]

Esto se ejecuta mucho más rápido porque ni siquiera estás mirando minutos a menos que se obtenga un valor mayor que el elemento dado. Aproximadamente 1/10 parte del tiempo del algoritmo original.

Esto funcionó en tiempo cero en mi Dell. Tuve que ejecutarlo 10 veces para obtener un tiempo de ejecución medible.

mins(items, n): 0.297000169754
sorted(items)[:n]: 0.109999895096
mins2(items)[:n]: 0.0309998989105

Usar bisect.insort lugar de append y sort puede acelerar esto un poco más.

Answer 5

¿por qué no simplemente llamar al elemento select_n_thth en O (N) vez y luego dividir la matriz en dos partes por el elemento n_th, este debería ser el más rápido.

ps: Este algoritmo O (N) funciona si no especifica el orden de los n elementos más pequeños. El siguiente enlace parece hacer el algoritmo de selección. http://code.activestate.com/recipes/269554-select-the-nth-smallest-element/

Suponiendo que la matriz no tiene elementos duplicados, el código funciona para mí. La eficiencia aún depende de la escala del problema, si n <10, probablemente sea suficiente un algoritmo O (logn * N).

import random
import numpy as np
def select(data, n):
"Find the nth rank ordered element (the least value has rank 0)."
data = list(data)
if not 0 <= n < len(data):
raise ValueError(''not enough elements for the given rank'')
while True:
pivot = random.choice(data)
pcount = 0
under, over = [], []
uappend, oappend = under.append, over.append
for elem in data:
if elem < pivot:
uappend(elem)
elif elem > pivot:
oappend(elem)
else:
pcount += 1
if n < len(under):
data = under
elif n < len(under) + pcount:
return pivot
else:
data = over
n -= len(under) + pcount
def n_lesser(data,n):
data_nth = select(data,n)
ind = np.where(data<data_nth)
return data[ind]

Answer 6

import heapq
nlesser_items = heapq.nsmallest(n, items)

Aquí hay una versión correcta del algoritmo de S.Lott :

from bisect import insort
from itertools import islice
def nsmallest_slott_bisect(n, iterable, insort=insort):
it = iter(iterable)
mins = sorted(islice(it, n))
for el in it:
if el <= mins[-1]: #NOTE: equal sign is to preserve duplicates
insort(mins, el)
mins.pop()
return mins

Actuación:

$ python -mtimeit -s "import marshal; from nsmallest import nsmallest$label as nsmallest; items = marshal.load(open(''items.marshal'',''rb'')); n = 10"/
"nsmallest(n, items)"

nsmallest_heapq 100 loops, best of 3: 12.9 msec per loop nsmallest_slott_list 100 loops, best of 3: 4.37 msec per loop nsmallest_slott_bisect 100 loops, best of 3: 3.95 msec per loop

nsmallest_slott_bisect es 3 veces más rápido que heapq ''s nsmallest (para n = 10, len (items) = 20000). nsmallest_slott_list es solo marginalmente más lento. No está claro por qué Heapq''s nsmallest es tan lento; su algoritmo es casi idéntico al presentado anteriormente (para n pequeño).