Obtener los n elementos menores de una lista en Python

Question

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.

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:

1. operación de inserción() es costoso porque las listas de Python no son listas vinculadas.
2. 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.

Answer 1

Usted realmente quiere 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 va mucho más rápido porque no está aún buscando en minutos a menos que sea demostrable tiene un valor mayor que el punto dado. Aproximadamente 1/10 parte del tiempo del algoritmo original.

Esto se ejecutó 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 

Usando bisect.insort en lugar de agregación y de especie puede acelerar este proceso un adicional de cabello.

Answer 2

Una posibilidad es utilizar 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 sólo un poco más rápido para mí:

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

Usando psyco no acelerarlo 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 3

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

La codificación a mano en c sería la mejor, y le permitirá usar estructuras de datos específicas para su dominio problemático.

Pero nota:

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

que quería añadir S. El comentario de 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 4

Me gusta la idea de montón de erickson. No sé Python tampoco, pero no parece haber una solución enlatada aquí: heapq — Heap queue algorithm

Answer 5

import heapq 

nlesser_items = heapq.nsmallest(n, items) 

Aquí hay una versión correcta de S.Lott's algorithm:

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 

Rendimiento:

$ 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 (artículos) = 20000). nsmallest_slott_list es solo un poco 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).

Answer 6

¿por qué no simplemente llamar al elemento select_n_th 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]