Ordinamento di dati più grandi della dimensione della RAM

Question

Questa è una domanda di intervista di Google: Dato 2 computer, ciascuno con 64 GB di RAM, contenenti tutti gli interi (8 byte), ordinare gli interi dati da 128 GB. Puoi assumere una piccola quantità di RAM aggiuntiva. Estendere questo per ordinare i dati memorizzati in 1000 macchine.

Mi è venuta l'ordinamento esterno. In questo dividiamo l'intero dato in blocchi e usiamo l'unire l'ordinamento su di essi. Questo è il primo tipo i blocchi e li rimettono indietro e li rimettono pezzo saggio e li uniscono. C'è un modo migliore? Quale sarebbe la complessità?

Answer 1

Ciascuno dei 64 GB può essere ordinato utilizzando un quicksort separatamente e quindi utilizzando la memoria esterna mantenere i puntatori in testa a entrambi gli array da 64 GB, si consideri che vogliamo RAM1 e RAM2 in tale ordine per avere l'intero dato, continuare ad incrementare puntatore su RAM1 se è minore del valore del puntatore su RAM2 altrimenti scambia il valore con RAM2 finché il puntatore non raggiunge la fine di RAM1.

prendere lo stesso concetto per ordinare tutte le N RAM. Prendine un paio e ordinale usando il metodo sopra. Si rimane con N/2 RAM ordinate. Usa lo stesso concetto sopra in modo ricorsivo.

Answer 2

ChingPing propone un ordinamento O (n log n) per ogni sottoinsieme, seguito da un'unione lineare (scambiando gli elementi). Il problema con Quicksort (e la maggior parte degli ordinamenti n log n è che richiedono n memoria. Suggerirei invece di usare uno SmoothSort che utilizza la memoria costante, continua ancora in O (n log n)

Il peggiore scenario è dove si hanno qualcosa di simile a:.

setA = [maxInt .. 1] 
setB = [0..minInt] 

in cui entrambi i gruppi sono ordinate in senso inverso, ma poi la fusione è in ordine inverso

The (IMO - più chiaro) spiegazione della soluzione ChingPing è :

Have a pointers 'pointerA', 'pointerB' initialized at the beginning of each array 
While setA's pointer is not at the end 
    if (setA[pointerA] < setB[pointerB]) 
    then { pointerA++; } 
    else { swap(setA[pointerA], setB[pointerB]); pointerB++; } 

Ora i set devono essere ordinati.

Answer 3

Ci sono già risposte per il caso di 2 macchine.

Suppongo che il 128 GB di dati da ordinare sia archiviato come singolo file su un singolo disco rigido (o qualsiasi dispositivo esterno). Indipendentemente dal numero di macchine o dischi rigidi utilizzati, il tempo necessario per leggere il file 128 GB originale e scrivere il file 128 GB ordinato rimane lo stesso. L'unico risparmio si verifica durante gli ordinamenti interni basati su ram per creare blocchi di dati ordinati. Il tempo necessario per unire con n + 1 dischi rigidi per unire n-way in un unico file ordinato da 128 GB sul disco rigido rimanente rimane lo stesso, limitato dal tempo necessario per scrivere il file ordinato da 128 GB su quello rimanente disco rigido.

Per n macchine, i dati verrebbero suddivisi in blocchi da 128 GB/n. Ciascuna delle macchine potrebbe alternare la lettura di sotto-blocchi, forse 64 MB alla volta, per ridurre l'overhead di accesso casuale, in modo che la macchina "last" non sia in attesa di tutte le macchine precedenti per leggere tutti i loro blocchi prima ancora che inizi .

Per n macchine (64 GB ciascuna) e n + 1 dischi fissi con n> = 4, un ordinamento digitale con O (n) complessità temporale può essere utilizzato da ciascuna macchina per creare 32 GB o più blocchi sul lavoro n dischi rigidi allo stesso tempo, seguiti da un'unione n-way sul disco fisso di destinazione.

C'è un punto di rendimenti decrescenti che limita il beneficio di più grande n. Da qualche parte oltre n> 16, il throughput di fusione interno potrebbe diventare maggiore della larghezza di banda I/O del disco.Se il processo di unione è legato alla cpu piuttosto che al limite I/O, c'è un compromesso nel sovraccarico della CPU per il tempo necessario a creare blocchi in parallelo rispetto al sovraccarico di unione maggiore del tempo di I/O.