Come si ordina un file con un elenco molto lungo di elementi?

Question

Ho un file di testo che ha un elenco molto lungo di elementi. Quindi voglio ordinarli alfabeticamente ma non voglio caricare tutto il file nella memoria (RAM).

Ho provato a caricare tutto il contenuto del file in un array e ordinarli come faccio normalmente. Ma il sistema si lamenta che non ci sono molti ricordi !!

Grazie, Mohammad

Answer 1

Avrete bisogno di leggere su external sorting. L'approccio di base consiste nell'utilizzare una sorta di routine divide et impera come merge sort, in cui si legge e si ordina una parte del file, quindi si legge e si ordina un'altra porzione del file, ecc. E quando si arriva alla fine si uniscono le parti ordinate insieme.

Answer 2

Forse lo STXXL (libreria di modelli standard per set di dati di grandi dimensioni) aiuta.

STXXL offre external sorting tra gli altri.

Answer 3

Non è necessario conservare l'intero file in memoria. Se questo è un compito che non devi fare molto spesso, puoi scrivere un'applicazione che lo ordina molto lentamente. Qualcosa di simile (pseudo):

vector<int> linesProcessed; 
for (int i = 0; i < lineCount; i++) 
{ 
    if (linesProcessed contains i) continue; 
    string alphabeticalFirstLine; 
    int lineIndex; 
    foreach line in oldFile 
    { 
     if (line is before alphabeticalFirstLine) 
     { 
      alphabeticalFirstLine = line; 
      lineIndex = i; 
     } 
    } 
    write alphabeticalFirstLine to newFile; 
    vector.add(lineIndex); 
} 
clear vector; 
delete oldFile; 
rename newFile to oldFile; 

Answer 4

Se si utilizza un sistema operativo unix, è possibile utilizzare il comando di ordinamento. Si prenderà cura del consumo di memoria. Per un esempio qualcosa come "cat large_file | sort" farà il lavoro.

Oppure è possibile scrivere il proprio/utilizzare l'ordinamento esterno dalla libreria. Dicci quale lingua stai usando e forse qualcuno ti dirà la libreria esatta da usare.