Algoritmi di ordinamento che funzionano su grandi quantità di dati

Il riferimento canonico all'ordinamento e alla ricerca è Knuth, vol. 3 . Inizia lì.

Il libro è stato originariamente riscritto quando i computer erano molto più piccoli e più lenti di adesso, il che ha reso le tecniche di ordinamento out-of-memory più importanti di quanto non siano oggi.

Unione esterna R-Way unione come in UNIX Il comando sort è una buona alternativa. Dalla tua formulazione, non sono sicuro se questo è l'algoritmo che intendevi con "unisci sort", e se non lo sai, dai un'occhiata.

Senza altre specifiche "Unisci Ordina" è probabilmente la migliore risposta che otterrai, tuttavia puoi implementare qualcosa di molto più intelligente in base alle tue esigenze.

Ad esempio, puoi semplicemente creare un indice in memoria del file e copiare tutti i valori contemporaneamente, memorizzando nella cache la posizione di vari valori chiave? 1/2 si adatta subito alla memoria o 1/1000000? Se è il secondo, potresti non essere in grado di adattare un indice in memoria, se il primo è possibile ordinare entrambi i mezzi in modo più efficiente, quindi unirli in un solo ultimo passaggio.

Diavolo, dato che non lo hai specificato è possibile che i tuoi dati siano tutti in un database, in tal caso puoi semplicemente creare una tabella di indice e chiamarla buona (credo che questo non sia il caso, ma solo sottolineando che la tua situazione è fondamentale per risolvere un problema complicato come questo).

Se vuoi farlo solo una volta e stai cercando un attacco molto rapido sembra che l'unione esterna sort sarebbe un buon inizio se stai usando unix (dato che apparentemente è integrato)

Se devi mantenerlo in ordine e aggiungi sempre un singolo record, sarà necessario un ordinamento per l'inserimento (l'aggiunta di un singolo record ai dati ordinati è sempre un ordinamento per inserimento).

Puoi controllare il codice che "Legge" i dati? In questo caso, molte forme di indicizzazione (anziché l'ordinamento spostando i dati sul disco) aiuteranno A LOT (sarà effettivamente un requisito assoluto).

• In posizione o più file?
• Una volta, periodico o tenerlo sempre ordinato?
• Quanto più grande della memoria (Quanti carichi di memoria riescono a superare l'intero set di dati)?
• È in un database? Può essere?
• Sei tu a controllare il codice che legge i dati, o altri stanno scaricando un file direttamente?
• Formato del file? (Testo? Record fisso?)
• Altre circostanze particolari di cui non ho chiesto informazioni?

Se vuoi davvero una soluzione scalabile dovresti dare un'occhiata a TeraSort, l'implementazione di ordinamento standard con map-reduce; ulteriori dettagli su StackOverflow .

Potresti essere interessato a un tipo di benna . La prestazione del caso medio è un tempo lineare.

= O (n + d) n: numero di elementi e d = lunghezza del numero più grande se hai un'intuizione sui tuoi dati, es. Se sai quante "cifre" è il tuo numero più grande. Quindi se hai 2 milioni di numeri a 6 cifre = > 0 (n) quindi lineare.

Utilizza un algoritmo di ordinamento merge esterno (se i tuoi dati sono continui) o un tipo di benna con < a href="http://en.algoritmy.net/article/40549/Counting-sort"> contando l'ordinamento come un'implementazione dell'ordinamento per bucket (se i tuoi dati sono discreti e distribuiti uniformemente).

Probabilmente l'approccio migliore è creare il tuo indice / file di mappatura se l'incremento è piccolo.

1. In qualche modo ordina il tuo "database"
2. Assegna un numero intero a ogni voce (1, 2, 3, 4, ..., n) (meglio: usa alcuni indici sparsi)
3. Quando aggiungi un incremento trovi solo un intervallo in cui il numero a sinistra è minore o uguale e il numero corretto è maggiore o uguale (non dovrebbe essere difficile con qualche versione modificata di una ricerca binaria)
4. Inserisci, mentre gli spazi vuoti sono sufficientemente grandi, in caso contrario: solo reindice (non riordinare mai più): -)

Ho appena creato alcune strutture astratte chiamate big queue e big array per semplificare l'attività di ricerca e ordinamento di grandi quantità su una singola macchina con memoria limitata. Fondamentalmente, l'algoritmo utilizzato è simile a quello che hai citato sopra - external merge sort.

Posso ordinare i dati da 128 GB (ogni elemento 100 byte) in 9 ore su una singola macchina, quindi eseguire la ricerca binaria nei dati ordinati quasi senza tempo.

Qui è un post su come cercare grandi dati usando la mia grande coda open source e le grandi strutture di array.