Come ottenere i numeri più grandi da enormi quantità di numeri?

Question

Vorrei estrarre i più grandi 100 elementi da un elenco di almeno 100000000 numeri.

Potrei ordinare l'intero elenco e prendere solo gli ultimi 100 elementi dall'elenco ordinato, ma sarebbe molto costoso in termini sia di memoria che di tempo.

Esiste un modo semplice, pitonico per farlo?

Quello che voglio è seguire la funzione anziché un ordinamento puro. In realtà non voglio perdere tempo a ordinare gli elementi che non mi interessano.

Ad esempio, questa è la funzione che vorrei avere:

getSortedElements(100, lambda x,y:cmp(x,y))

Nota che questo requisito è solo per la prospettiva delle prestazioni.

Answer 1

Il modulo heapq nella libreria standard offre la funzione nlargest () per farlo:

top100 = heapq.nlargest(100, iterable [,key])

Non ordinerà l'intero elenco, quindi non perderai tempo sugli elementi che non ti servono.

Answer 2

Algoritmi di selezione dovrebbero essere utili qui.

Una soluzione molto semplice è trovare il 100 ° elemento più grande, quindi scorrere l'elenco selezionando gli elementi più grandi di questo elemento. Questo ti darà i 100 elementi più grandi. Questo è lineare nella lunghezza dell'elenco; questo è il migliore possibile.

Esistono algoritmi più sofisticati. Un heap , ad esempio, è molto suscettibile di questo problema. L'algoritmo basato su heap è n log k dove n è la lunghezza dell'elenco e k è il numero di elementi più grandi che si desidera selezionare .

C'è una discussione di questo problema sulla pagina di Wikipedia per gli algoritmi di selezione.

/ p>

Modifica: un altro poster ha sottolineato che Python ha una soluzione integrata a questo problema. Ovviamente è molto più semplice che pubblicarne uno tuo, ma terrò questo post nel caso in cui desideri sapere come funzionano tali algoritmi.

Answer 3

È possibile utilizzare una struttura di dati Heap. Un heap non sarà necessariamente ordinato, ma è un modo abbastanza veloce per conservare i dati semi-ordinati e ha il vantaggio che l'elemento più piccolo sia sempre il primo elemento nell'heap.

Un heap ha due operazioni di base che ti aiuteranno: Aggiungi e Sostituisci.

Fondamentalmente quello che fai è aggiungere elementi ad esso fino a quando non arrivi a 100 elementi (il tuo numero N in alto per la tua domanda). Quindi, sostituisci il primo oggetto con ogni nuovo oggetto, purché il nuovo oggetto sia più grande del primo.

Ogni volta che sostituisci il primo oggetto con qualcosa di più grande, il codice interno nell'heap regolerà il contenuto dell'heap in modo che se il nuovo elemento non è il più piccolo, rimbalzerà nell'heap e l'oggetto più piccolo verrà " bolla giù " al primo elemento, pronto per essere sostituito lungo la strada.

Answer 4

Il modo migliore per farlo è quello di mantenere una coda di priorità ordinata da heap da cui si esce una volta che contiene 100 voci.

Anche se non ti importa se i risultati sono ordinati, è intuitivamente ovvio che lo otterrai gratuitamente. Per sapere di avere i primi 100, è necessario ordinare il tuo elenco attuale dei primi numeri in ordine tramite una struttura dati efficiente. Quella struttura conoscerà il minimo, il massimo e la posizione relativa di ciascun elemento in modo naturale da poter affermare la sua posizione vicino ai suoi vicini.

Come è stato menzionato in Python, useresti heapq. In Java PriorityQueue: http://java.sun.com/javase/ 6 / docs / api / java / util / PriorityQueue.html

Answer 5

Ecco una soluzione che ho usato che è indipendente dalle librerie e che funzionerà con qualsiasi linguaggio di programmazione che abbia array:

inizializzazione:

Make an array of 100 elements and initialise all elements
with a low value (less than any value in your input list).

Initialise an integer variable to 0 (or any value in
[0;99]), say index_minvalue, that will point to the
current lowest value in the array.

Initialise a variable, say minvalue, to hold the current 
lowest value in the array.

Per ogni valore, dire current_value, nell'elenco di input:

if current_value > minvalue

  Replace value in array pointed to by index_minvalue
  with current_value

  Find new lowest value in the array and set index_minvalue to
  its array index. (linear search for this will be OK as the array
  is quickly filled up with large values)

  Set minvalue to current_value

else
  <don't do anything!>

minvalue otterrà rapidamente un valore elevato e quindi la maggior parte dei valori nell'elenco di input dovrà essere confrontato solo con il valore minimo (il risultato del confronto sarà per lo più falso).

Answer 6

Per i weenies degli algoritmi nel pubblico: puoi farlo con una semplice variazione dell'algoritmo di Tony Hoare Trova :

find(topn, a, i, j)
   pick a random element x from a[i..j]
   partition the subarray a[i..j] (just as in Quicksort) 
     into subarrays of elements <x, ==x, >x
   let k be the position of element x
   if k == 0 you're finished
   if k > topn, call find(topn, a, i, k)
   if k < topn, call find(topn-k, k, j)

Questo algoritmo inserisce i più grandi elementi topn nei primi elementi topn dell'array a , senza ordinandoli . Naturalmente, se li desideri ordinati, o per pura semplicità, un heap è migliore e chiamare la funzione di libreria è ancora meglio. Ma è un algoritmo interessante.