Trovare l'ennesimo elemento dell'elenco non ordinato senza ordinare l'elenco

Question

Ehi. Ho una matrice molto grande e voglio trovare il nono valore più grande. Trivially Posso ordinare l'array e prendere l'elemento Nth ma sono interessato solo a un elemento, quindi probabilmente c'è un modo migliore rispetto all'ordinamento dell'intero array ...

Answer 1

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

Answer 2

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

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

Answer 4

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); 
    } 
} 

Answer 5

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)

Answer 6

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.

Answer 7

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 

Answer 8

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

Answer 9

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.