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).