Uzyskiwanie mniejszych n elementów listy w Pythonie

Question

Potrzebuję uzyskać mniejsze liczby n listy w Pythonie. Potrzebuję tego, aby był naprawdę szybki, ponieważ ma kluczowe znaczenie dla wydajności i musi być powtarzany wiele razy.

n zwykle nie jest większe niż 10, a lista zwykle zawiera około 20000 elementów. Lista jest zawsze inna za każdym razem, gdy wzywam funkcję. Sortowania nie można wprowadzić w życie.

Początkowo Pisałem tę funkcję:

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 

Ale ta funkcja nie może pokonać proste posortowane (przedmioty) [n], która uszeregować całą listę. Oto my Test:

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 

Wyniki:

mins(items, n): 0.0632939338684 
sorted(items)[:n]: 0.0231449604034 

klasyfikowane() [n] jest trzy razy większa. Wierzę, że dzieje się tak dlatego:

1. Operacja insert() jest kosztowna, ponieważ listy w Pythonie nie są listami połączonymi.
2. posortowane() to zoptymalizowana funkcja c, a moja to czysty pyton.

Czy istnieje sposób na pokonanie posortowane() [: n]? Czy powinienem używać rozszerzenia C, Pyrex lub Psyco, czy coś w tym stylu?

Z góry dziękuję za odpowiedzi.

Answer 1

Rzeczywiście chcesz posortowaną sekwencję min.

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

ten biegnie dużo szybciej, ponieważ nie patrząc nawet na min chyba to provably ma wartość większą niż danej pozycji. Około 1/10 czasu oryginalnego algorytmu.

To trwało zero czasu na moim Dell. Musiałem uruchomić go 10 razy, aby uzyskać mierzalny czas pracy.

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

Korzystanie bisect.insort zamiast append i sortowania może przyspieszyć proces włosy dalej.

Answer 2

Możliwość jest użycie modułu bisect:

import bisect 

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

Jednak, to tylko nieco szybciej dla mnie:

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

Korzystanie psyco ma przyspieszyć go trochę więcej:

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 

Wynik:

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

Answer 3

Jeśli prędkość jest sprawą najwyższej wagi, najszybszą metodą będzie c. Psyco ma koszt początkowy, ale może okazać się dość szybki. Polecam Cython dla Pythona -> kompilacja c (bardziej aktualna dla Pyrex).

Ręczne kodowanie go w c byłoby najlepsze i pozwala używać struktur danych specyficznych dla domeny problemu.

Ale uwaga:

"Kompilacja zły algorytm w C nie może być szybciej niż algorytm w Pythonie prawo " @ S.Lott

chciałem dodać S. Komentarz Lott, więc zostaje zauważony. Python to doskonały język prototypowy, w którym możesz wyprowadzić algorytm, który później zamierzasz przetłumaczyć na język niższego poziomu.

Answer 4

Podoba mi się pomysł sterty ericksona. Nie wiem, Python albo, ale nie wydaje się być w puszkach rozwiązanie tutaj: heapq — Heap queue algorithm

Answer 5

import heapq 

nlesser_items = heapq.nsmallest(n, items) 

Oto poprawna wersja 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 

Wydajność:

$ 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 

jest 3 razy szybsza niż heapq 's nsmallest (dla n = 10, len (przedmioty) = 20000). nsmallest_slott_list jest tylko nieznacznie wolniejszy. Nie jest jasne, dlaczego nsmallest heapq jest tak wolny; jego algorytm jest prawie identyczny z przedstawionym powyżej (dla małych n).

Answer 6

dlaczego nie po prostu wywołać select_n_th element w czasie O (N), a następnie podzielić tablicę na dwie części przez n_th element, powinien to być najszybszy.

ps: Ten algorytm O (N) działa, jeśli nie określono kolejności najmniejszych elementów. Poniższy link wydaje się być algorytmem wyboru. http://code.activestate.com/recipes/269554-select-the-nth-smallest-element/

Zakładając, że tablica nie ma zduplikowanych elementów, kod działa dla mnie. Wydajność nadal zależy od skali problemu, jeśli n < 10, prawdopodobnie wystarczy algorytm 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]