Come ottimizzare l'ordinamento di unione?

Question

Ho due file da 1 GB ciascuno contenenti solo numeri in ordine.Ora so come leggere il contenuto dei file e ordinarli utilizzando l'algoritmo Merge Sort e inviarlo in un altro file, ma ciò che mi interessa è come farlo utilizzando solo una dimensione del buffer di 100 MB (non mi preoccupo dello scratch spazio).Ad esempio, un modo è leggere blocchi da 50 MB da entrambi i file e ordinarli e una volta ordinati potrei leggere un nuovo elemento e continuare il processo fino a raggiungere la fine di entrambi i file (qualcuno può darmi qualche idea su come implementare Questo).

Answer 1

Sembra che tu solo bisogno di unione i numeri nei file, non le specie, dato che sono già ordinati in ogni file. La parte merge di merge sort è questa:

function merge(left,right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) ≤ first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append left to result
            break             
        else if length(right) > 0
            append right to result
            break
    end while
    return result

Ora si può solo leggere il primo 50 MB di numeri da entrambi i file in due buffer, applicare l'algoritmo merge, poi, quando uno dei buffer è stato esaurito (tutti i suoi numeri analizzati), leggere un altro 50 MB dal file necessario . Non c'è bisogno di sorta nulla.

Hai solo bisogno di una condizione che verifica quando uno dei tuoi buffer è vuoto. Quando è, per saperne di più dal fascicolo che buffer è associato.

Answer 2

Perché non utilizzare la libreria standard?

#include <fstream>
#include <iterator>
#include <algorithm>

int main()
{
   std::ifstream in1("in1.txt");
   std::ifstream in2("in2.txt");
   std::ofstream ut("ut.txt");
   std::istream_iterator<int> in1_it(in1);
   std::istream_iterator<int> in2_it(in2);
   std::istream_iterator<int> in_end;
   std::ostream_iterator<int> ut_it(ut, "\n");

   std::merge(in1_it, in_end, in2_it, in_end, ut_it);
}

Answer 3

Probabilmente si desidera leggere / scrivere in blocchi ragionevoli per evitare un sovraccarico di I / O. Quindi probabilmente utilizzare tre buffer di ~ 30M, input1, input2 e l'uscita.

Continuare fino a quando uno dei buffer di ingresso è vuoto o il buffer di uscita è pieno, allora lettura / scrittura di ricarica / svuotare il buffer vuoto / pieno.

In questo modo si sta scrivendo / lettura di grandi quantità di dati dal disco.

Al di là che è necessario I / O asincrono per leggere / scrivere dati mentre si sta facendo l'ordinamento. Ma questo è probabilmente eccessivo.

Answer 4

Dato che stai solo eseguendo un'unione, non un ordinamento completo, è solo il ciclo di unione di base.I/O puramente sequenziale.Non c'è bisogno di preoccuparsi dei buffer.Immagina una cerniera su una giacca.È così semplice.(Nota:potrebbe essere molto più veloce se i numeri fossero in formato binario nei file.Non solo i file saranno più piccoli, ma il programma sarà limitato in termini di I/O e i numeri saranno perfettamente accurati.)

double GetNumberFromFile(FILE file){
  if (feof(file)){
    return BIGBIGNUMBER;
  }
  else {
    return ReadADouble(file);
  }
}

double A = GetNumberFromFile(AFILE);
double B = GetNumberFromFile(BFILE);
while (A < BIGBIGNUMBER && B < BIGBIGNUMBER){
  if (A < B){
    write A;
    A = GetNumberFromFile(AFILE);
  }
  else if (B < A){
    write B;
    B = GetNumberFromFile(BFILE);
  }
  else {
    write A;
    write B; // or not, if you want to eliminate duplicates
    A = GetNumberFromFile(AFILE);
    B = GetNumberFromFile(BFILE);
  }
}
while (A < BIGBIGNUMBER){
    write A;
    A = GetNumberFromFile(AFILE);
}
while (B < BIGBIGNUMBER){
    write B;
    B = GetNumberFromFile(BFILE);
}

---

Rispondendo alla tua domanda, considera un problema più semplice, copiare un file in un altro.Stai solo effettuando I/O sequenziale, cosa in cui il file system è davvero bravo.Scrivi un semplice ciclo per leggere piccole unità come un byte o un int dal file e scriverlo nell'altro.Non appena provi a leggere un byte, il sistema alloca un buffer abbastanza grande, inserisce una grossa porzione del file nel buffer e quindi estrae il byte dal buffer.Continua a farlo finché non hai bisogno di un altro buffer, quando invisibilmente ne crea un altro per te.Lo stesso genere di cose accade con il file che stai scrivendo.Ora la CPU è piuttosto veloce, quindi può scorrere i byte di input, copiandoli sull'output, in una frazione del tempo necessario per leggere o scrivere un buffer, perché la lettura o la scrittura non può andare più veloce del hardware esterno.L'unica ragione per cui un buffer più grande sarebbe d'aiuto è che parte del tempo di lettura/scrittura è quella che viene chiamata "latenza", sostanzialmente il tempo necessario per spostare la testa sulla traccia desiderata e attendere che arrivi il settore desiderato.La maggior parte dei file system suddivide i file in blocchi sparsi sul disco, quindi la testa salta comunque.Puoi sentirlo.

L'unica differenza tra la copia e un algoritmo di unione come il tuo è che legge due file, non uno.In ogni caso, la sequenza temporale di base è una serie di letture e scritture del buffer intervallate da una piccola quantità di azione della CPU.(È possibile farlo sovrapposto I/O, in modo che venga eseguita l'azione della CPU Mentre l'I/O avviene, quindi fondamentalmente c'è NO ritardo tra le letture e le scritture del buffer, ma era un problema maggiore quando le CPU erano 1000 volte più lente.)

Naturalmente, se è possibile organizzarlo in modo che i file letti e scritti siano tutti su unità disco fisiche separate e le unità non siano molto frammentate, la quantità di movimento della testina potrebbe essere ridotta al minimo e buffer più grandi potrebbero essere d'aiuto.Ma fondamentalmente, con un programma semplice, puoi aspettarti che il codice semplice vada alla stessa velocità con cui il disco può spostare i dati, e buffer giganti potrebbero aiutare, ma non molto.

Answer 5

Benchmark. Leggere il valore per valore e il blocco di lettura. Senti la differenza! =)