Ordina file 1TB su macchina con 1 GB di RAM

Question

Questa domanda sembra facile, ma non sono in grado di comprendere il vero lavoro che sta dietro. So che la gente dirà, scomporre in pezzi da 512 Meg e ordinarli come usando Unisci Ordina usando Riduci mappa.

Quindi, ecco la domanda reale che ho:

Supponiamo che io rompere il file in 512 mega pezzo e poi inviare a diverse macchine host per ordinare loro. si supponga che queste macchine abbiano utilizzato l'Unisci ordinamento. Ora diciamo che avevo 2000 macchine ciascuna ordinate 2000, 512 mega di chunk. Ora quando li unisco di nuovo, come funziona? Le dimensioni non aumenteranno di nuovo? Ad esempio, l'unione di due 512 mega farà 1024 meg che è la dimensione della mia RAM, quindi come funzionerebbe? Qualsiasi macchina non può unire un chunk di più di 512 mega di chunk con un altro chunk perché poi la dimensione> 1 GB.

Come alla fine della fusione potrò mai unire due blocchi da 0,5 TB con un altro chunk da 0,5 TB. Il concetto di memoria virtuale entra in gioco qui?

Sono qui per chiarire le mie basi e spero di porre questa domanda molto importante (correttamente) correttamente. Inoltre, chi dovrebbe fare questo unire (dopo l'ordinamento)? La mia macchina o alcune di quelle macchine del 2000?

Answer 1

Ecco un modo teorico che dovrebbe funzionare. Supponiamo che tu abbia i tuoi 2000 file 512mb, pronti a creare un file da 1TB.

Se semplicemente scorrere ogni file, trovare uno che ha il valore più basso, quindi spostare che nel vostro file di destinazione, e ripetere poi vi ritroverete con tutto in ordine. L'utilizzo della RAM dovrebbe essere ridotto in quanto non avrai mai bisogno di aprire più di una linea alla volta.

Ovviamente dovresti essere in grado di ottimizzare questo - mantieni la prima riga di ogni file nella RAM mentre vai e dovrebbe essere un po 'più veloce.

Answer 2

La versione breve di come si uniscono è come questo:

1) Si crea una tabella con uno slot per ogni macchina si uniscono da.

2) Si chiede ad ogni macchina l'entrata minima che non hanno ancora fornito.

3) Si rimuove la voce con valore più basso dalla tabella, la si stampa e si chiede alla macchina di riempire il lento con la voce più bassa che non ha ancora dato, lasciando lo slot vuoto se la macchina è fuori dalle voci .

4) Ripetere il passaggio 3 finché il tavolo non è vuoto.

Ciò consente di unire da N macchine che memorizzano solo N voci alla volta. Ovviamente, puoi banalmente ottimizzarlo per contenere le voci M di ogni macchina. In tal caso, è necessario memorizzare le voci N * M e quando uno slot è vuoto, chiedere a quella macchina le voci M per riempirlo.

Answer 3

Il bello di un ordinamento di unione è che non è necessario l'accesso casuale; l'accesso sequenziale funzionerà. Questo è ciò che lo rende una soluzione perfetta quando il set di dati non si adatta alla memoria.

Un singolo passaggio di unione richiede 2 (o più) ingressi e produce un'uscita. Continui a combinare gli input in output finché non rimane un solo file.

Answer 4

Ora dire, ho avuto 2000 macchine ogni filtrate 2000, 512 mega di pezzo.Ora quando li unisco di nuovo, come funziona? La dimensione non continuerà a crescere su ? Ad esempio, l'unione di due 512 mega renderà 1024Meg che è la dimensione della mia RAM, quindi come funzionerebbe? Qualsiasi macchina non può unire una porzione di più di 512 mega pezzo con un altro pezzo perché quindi la dimensione> 1 GB.

Non è così che funziona un'implementazione pratica del mergesort. La cosa interessante di mergesort (e algoritmi di ordinamento correlati) è che non è necessario avere l'intero set di dati in memoria per farlo funzionare. Quando si uniscono, è sufficiente leggere in memoria una piccola porzione del file alla volta, che verrà poi scritta poco dopo.

In altre parole, non è necessario un accesso casuale per un mergesort. Se non fosse per questa bella proprietà sarebbe impossibile per sort the data on tape drives con la tecnologia disponibile al momento. Le unità nastro non sono ovviamente supporti ad accesso casuale e la RAM è stata misurata in kilobyte.

Answer 5

Questo problema può essere ridotto a un problema più semplice. Questo problema è stato progettato per costringerti a un approccio. Eccolo:

• Pick up chunks = ~ 1GB, tipo & memorizzarli come file ordinati separati.
• Si finisce con 1000 file 1 GB ordinati sul file system.

• Ora, è semplicemente un problema di unire gli array k-ordinati in un nuovo array.

  L'unione di array k-ordinati richiede di mantenere un min-heap (coda prioritaria) con k elementi alla volta.

cioè k = 1000 (file) nel nostro caso. (1 GB ram può memorizzare 1000 numeri)

Pertanto, mantenere gli elementi di popolamento dalla coda di priorità e salvarli sul disco.

Si avrà un nuovo file, ordinato di dimensioni 1 TB.

consultare: http://www.geeksforgeeks.org/merge-k-sorted-arrays/

Aggiornamento

PS: può essere fatto su una sola macchina con 1 GB di RAM, con una struttura di dati migliore

Merge può essere fatto in meno di O (N), spazio con priorità Coda, ovvero O (K), spazio, ovvero il cuore del problema.