2009-06-23 2 views

risposta

15

Ordinamento richiederebbe O (nlogn) runtime al minimo - ci sono molto efficienti selection algorithms che può risolvere il problema in tempo lineare.

Partition-based selection (a volte Quick select), che si basa sull'idea di quicksort (partizionamento ricorsivo), è una buona soluzione (vedi link per pseudocode + Another example).

+0

Collegamento piacevole. Credo che questo sia il migliore. –

+9

Sfortunatamente, il link "Un altro esempio" ora porta a una pagina Web protetta al MIT, che devi avere il permesso di accesso. – Beel

+0

[NumPy ha questo built-in] (http://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.partition.html), anche se è una specie di strana dipendenza da inserire se si ' non sta ancora facendo uso della sua funzionalità ndarray. – user2357112

1

Usa heapsort. Ordina solo parzialmente l'elenco finché non ne estrai gli elementi.

+1

Prova a trovare l'elemento n/2-esimo - Richiede O (nlogn)! – Dario

3

È possibile eseguire l'iterazione dell'intera sequenza mantenendo un elenco dei 5 valori più grandi che si trovano (questo sarà O (n)). Detto questo, penso che sarebbe più semplice ordinare la lista.

+0

Ma quando non è il quinto, ma l'ennesimo elemento, avrai O (n²) che è anche peggio dell'ordinamento. – Dario

+0

Suppongo che intendiate mantenere un elenco dei N valori più grandi. Ma N non può essere troppo grande in quel caso. –

1

In sostanza, si desidera produrre un elenco "top-N" e selezionare quello alla fine di tale elenco.

Quindi è possibile scansionare l'array una volta e inserirlo in un elenco vuoto quando l'elemento largeArray è maggiore dell'ultimo elemento dell'elenco Top-N, quindi rilasciare l'ultimo elemento.

Al termine della scansione, selezionare l'ultimo elemento nell'elenco N superiore.

Un esempio per interi e N = 5:

int[] top5 = new int[5](); 
top5[0] = top5[1] = top5[2] = top5[3] = top5[4] = 0x80000000; // or your min value 

for(int i = 0; i < largeArray.length; i++) { 
    if(largeArray[i] > top5[4]) { 
     // insert into top5: 
     top5[4] = largeArray[i]; 

     // resort: 
     quickSort(top5); 
    } 
} 
1

Come si è detto, è possibile visualizzare l'elenco una volta tenendo traccia dei valori K più grandi. Se K è grande questo algoritmo sarà vicino a O (n).

Tuttavia, è possibile memorizzare i valori Kth più grandi come un albero binario e l'operazione diventa O (n log k).

Secondo Wikipedia, questo è il miglior algoritmo di selezione:

function findFirstK(list, left, right, k) 
    if right > left 
     select pivotIndex between left and right 
     pivotNewIndex := partition(list, left, right, pivotIndex) 
     if pivotNewIndex > k // new condition 
      findFirstK(list, left, pivotNewIndex-1, k) 
     if pivotNewIndex < k 
      findFirstK(list, pivotNewIndex+1, right, k) 

La sua complessità è O (n)

+0

Credo che l'Algoritmo del Torneo, vedi i collegamenti di Dario, sia quello per cui stai girando. Ha un'operazione di O (n + k * log (n)). – tgray

+1

Un mio errore, anche se sarei interessato a vedere una piena implementazione di questo in Python. – tgray

3

Un semplice quicksort modificato funziona molto bene nella pratica. Ha un tempo di esecuzione medio proporzionale a N (anche se il peggior caso di sfortuna è O (N^2)).

Procedere come un quicksort. Scegli un valore di pivot in modo casuale, quindi esegui lo streaming dei tuoi valori e verifica se sono superiori o inferiori a tale valore di pivot e li metti in due bin in base a tale confronto. In quicksort, si ordina in modo ricorsivo ciascuno di questi due raccoglitori. Ma per l'N-esimo calcolo del valore più alto, devi solo ordinare UNO dei bin ... la popolazione di ciascun bin ti dice quale bin contiene il tuo n-esimo valore più alto. Quindi, ad esempio, se desideri il 125 ° valore più alto e dividi in due contenitori che hanno 75 nel cestino "alto" e 150 nel cestino "basso", puoi ignorare il contenitore alto e procedi nel trovare il 125-75 = 50 ° valore più alto nel solo contenitore basso.

19

Un heap è la migliore struttura dati per questa operazione e Python ha un'eccellente libreria integrata per fare proprio questo, chiamato heapq.

import heapq 

def nth_largest(n, iter): 
    return heapq.nlargest(n, iter)[-1] 

Esempio di utilizzo:

>>> import random 
>>> iter = [random.randint(0,1000) for i in range(100)] 
>>> n = 10 
>>> nth_largest(n, iter) 
920 

risultato Conferma di classificare:

>>> list(sorted(iter))[-10] 
920 
+2

Funziona bene (tempo lineare) se si desidera l'ennesimo articolo più grande o più piccolo, dove n è una costante. Se n è metà della lunghezza della lista (cioè vuoi la mediana), questa è ancora O (nlogn) tempo. – mgold

+0

Questa non è una soluzione sul posto, Quickselect non aggiungerà O (n) memoria extra come questa soluzione farebbe. Quindi, per gli array molto grandi come chiede la domanda, questo probabilmente non sarebbe il più efficiente. – db1234

2

Si potrebbe provare la mediana del metodo di mediane - la sua velocità è O (N).

0

Una cosa che dovresti fare se questo è nel codice di produzione è testare con campioni dei tuoi dati. Ad esempio, è possibile considerare array "grandi" di 1000 o 10000 elementi e codificare un metodo quickselect da una ricetta.

La natura compilata di ordinamento, e le sue ottimizzazioni un po 'nascoste e in continua evoluzione, rendono più veloce di un metodo quickselect scritto in python su dataset di piccole e medie dimensioni (< 1.000.000 di elementi). Inoltre, è possibile che quando si aumenta la dimensione dell'array oltre questa quantità, la memoria venga gestita in modo più efficiente nel codice nativo e il vantaggio continui.

Quindi, anche se quickselect è O (n) vs O (nlogn) ordinato, ciò non tiene conto di quante istruzioni del codice macchina effettive eseguiranno ogni n elementi, dell'impatto sul pipelining, degli usi delle cache del processore e altre cose che i creatori e i manutentori di ordinamento inseriranno nel codice python.