Come posso ordinare 1 milione di numeri e stampare solo i primi 10 in Python?

Question

Ho un file che ha 1 milione di numeri. Ho bisogno di sapere come posso risolvere la cosa in modo efficiente, in modo che esso non stalla il computer, e stampare solo la parte superiore 10.

#!/usr/bin/python3 

#Find the 10 largest integers 
#Don't store the whole list 

import sys 

def fOpen(fname): 
     try: 
       fd = open(fname,"r") 
     except: 
       print("Couldn't open file.") 
       sys.exit(0) 
     all = fd.read().splitlines() 
     fd.close() 
     return all 

words = fOpen(sys.argv[1]) 

big = 0 
g = len(words) 
count = 10 

for i in range(0,g-1): 
     pos = i 
     for j in range(i+1,g): 
       if words[j] > words[pos]: 
         pos = j 
       if pos != i: 
         words[i],words[pos] = words[pos],words[i] 
       count -= 1 
       if count == 0: 
         print(words[0:10]) 

So che questa è la selezione tipo, io non sono sicuro di quello che sarebbe il miglior modo di fare.

Answer 1

Se sono necessari solo i primi 10 valori, allora si sprecherà molto tempo per ordinare ogni singolo numero.

Basta scorrere l'elenco dei numeri e tenere traccia dei 10 valori principali più visti finora. Aggiorna i primi dieci mentre leggi l'elenco e stampali quando raggiungi la fine.

Ciò significa che solo bisogno di fare un unico passaggio attraverso il file (cioè complessità temporale di theta (n))

Un problema più semplice

Potete guardare il problema come una generalizzazione di trovare il valore massimo in una lista di numeri. Se ti viene dato {2,32,33,55,13, ...} e ti viene chiesto di trovare il valore più grande, cosa faresti? La soluzione tipica è quella di scorrere l'elenco, ricordando il numero più grande incontrato finora e confrontandolo con il numero successivo.

Per semplicità, supponiamo di avere a che fare con numeri positivi.

Initialize max to 0 
0 < 2, so max = 2 
2 < 32, so max = 32 
32 < 33, so max = 33 
33 < 55, so max = 55 
55 > 13, so max = 55 
... 
return max 

Quindi, vedete, siamo in grado di trovare il massimo in un unico attraversamento della lista, a differenza di qualsiasi tipo di ordinamento per confronti.

Generalizzando

Trovare i primi 10 valori in una lista è molto simile. L'unica differenza è che dobbiamo tenere traccia dei primi 10 invece del massimo (primo 1).

La linea di fondo è che è necessario un contenitore contenente 10 valori. Mentre stai scorrendo la tua gigantesca lista di numeri, l'unico valore che ti interessa nella tua dimensione-10-contenitore è il minimo. Questo perché è il numero che verrebbe sostituito se hai scoperto un nuovo numero che merita di essere nella top-10-così-lontano.

In ogni caso risulta che la struttura dati più adatta per trovare rapidamente i min è un heap minimo. Ma non sono sicuro che tu abbia già imparato a conoscere gli heap e il sovraccarico dell'utilizzo di un heap per 10 elementi potrebbe superare i suoi benefici.

Qualsiasi contenitore che contiene 10 elementi e può ottenere il minimo in un ragionevole lasso di tempo sarebbe un buon inizio.

Answer 2

L'ordinamento migliore è un ordinamento parziale, disponibile nella libreria Python come heapq.nlargest.

Answer 3

import heapq 

with open('nums.txt') as f: 
    numbers=map(int,f.readlines()) 
    print heapq.nlargest(10,numbers) 
    print heapq.nsmallest(10,numbers) 
""" 
[1132513251, 13252365, 23512, 2000, 1251, 1235, 324, 100, 82, 82] 
[1, 1, 7, 13, 15, 21, 22, 22, 33, 82] 
""" 

Answer 4

quello che vuoi è un buon selection algorithm

Il seguente codice Python si basa intorno alla funzione di partizione partition() divide la lista in due. I valori inferiori a "pivotValue" vengono spostati all'inizio dell'elenco. I valori maggiori di pivotValue vengono spostati alla fine dell'elenco. Questo avviene nelle operazioni O (N) passando dall'elenco dall'inizio alla fine, ogni volta che guarda un valore lo sposta vicino all'inizio della lista, solo se è più piccolo del valore pivot.

(nel tuo caso, in realtà, spostiamo i valori più grandi all'inizio della lista poiché vuoi che i valori più grandi non siano i più piccoli).

Una volta partizionato l'elenco in tempo O (N), restiamo con m numeri grandi all'inizio della lista. se m = 10 allora ottimo, ecco i tuoi dieci più grandi numeri. se m è più grande di 10, allora dobbiamo dividere nuovamente i numeri più grandi per ottenere i 10 numeri più grandi dai più grandi numeri. se m è minore di 10 allora abbiamo bisogno di 10 m più numeri, quindi partizioniamo la parte più rara per trovare i numeri da 10 m e li aggiungiamo ai nostri numeri m per ottenere i 10 numeri necessari.

Così continuiamo a partizionare finché non abbiamo 10 numeri più grandi. Questo è fatto dal metodo select(). L'intero metodo è di solito molto veloce perché ogni volta che facciamo una partizione ci rimane circa la metà dei numeri da gestire. (se dividi costantemente il numero di numeri che devi considerare per due, va bene). Ogni volta che facciamo una partizione che produce più di 10 numeri più grandi, possiamo ignorare un intero mucchio di numeri troppo piccoli.

Ecco il codice:

def partition(_list,left,right,pivotIndex): 
    pivotValue=_list[pivotIndex] 
    _list[right],_list[pivotIndex]=pivotValue,_list[right] 
    storeIndex=left 
    for i in range(left,right): 
     if _list[i] > pivotValue: 
      _list[storeIndex],_list[i]=_list[i],_list[storeIndex] 
      storeIndex+=1 
    _list[right],_list[storeIndex]=_list[storeIndex],_list[right] 
    return storeIndex 

from random import randint 
def select(_list,left,right,k): 
    if left==right: 
     return _list[:left+1] 
    pivotIndex=randint(left,right) 
    pivotNewIndex=partition(_list,left,right,pivotIndex) 
    pivotDist=pivotNewIndex-left+1 
    if pivotDist==k: 
     return _list[:pivotNewIndex+1] 
    elif k<pivotDist: 
     return select(_list,left,pivotNewIndex-1,k) 
    else: 
     return select(_list,pivotNewIndex+1,right,k-pivotDist) 

_list=[1,2,109,2234,23,6,1,234,11,4,12451,1] 

left=0 
right=len(_list)-1 
pivotIndex=4 

print _list 
"[1, 2, 109, 2234, 23, 6, 1, 234, 11, 4, 12451, 1]" 
print partition(_list,left,right,pivotIndex) #partition is order(N). 
"7" #index 7, so the lowest number are in the first 7 numbers of the list [1, 2, 1, 6, 1, 11, 4, 23] 
print _list 
"[1, 2, 1, 6, 1, 11, 4, 23, 2234, 109, 12451, 234]" 
print select(_list,left,right,10) 
"[1, 2, 1, 1, 4, 11, 6, 23, 109, 234]" 

with open('nums.txt') as f: 
    numbers=map(int,f.readlines()) 
    print select(numbers,0,len(numbers)-1,10) 
    "[1132513251, 2000, 23512, 13252365, 1235, 1251, 324, 100, 82, 82]"