C# N l'unione per l'ordinamento esterno

Question

Qual è il modo migliore per implementare un'unione in modo N per i file ordinati N?

Diciamo che ho 9 file ordinati con 10 record ciascuno? Come faccio a unire questi file per creare un grande file con 90 record ordinati?

Answer 1

La strategia potrebbe dipendere dalla quantità di dati.

1. Se i dati si inserisce in memoria è possibile leggere tutti i dati in un elenco, ordinare, e scriverlo fuori
2. Se si desidera rimuovere i duplicati utilizzare un HashSet invece di una lista
3. Se lo farà non si adatta alla memoria, apre tutti i file per la lettura, confronta il primo record di ogni file e scrive il più basso. Quindi fai avanzare il file che hai letto. Loop su tutti i file fino a quando non sono tutti esauriti e scritti nel nuovo file.
4. Se si desidera rimuovere i duplicati, fare come sopra, ma saltare un record uguale all'ultimo scritto.

Ecco un esempio di codice che legge in N file di testo ordinati e li unisce. Non ho incluso il controllo duplicato, ma dovrebbe essere facile da implementare.

Prima una classe di supporto.

class MergeFile : IEnumerator<string> 
{ 
    private readonly StreamReader _reader; 

    public MergeFile(string file) 
    { 
     _reader = File.OpenText(file); 
     Current = _reader.ReadLine(); 
    } 

    public string Current { get; set; } 

    public void Dispose() 
    { 
     _reader.Close(); 
    } 

    public bool MoveNext() 
    { 
     Current = _reader.ReadLine(); 
     return Current != null; 
    } 

    public void Reset() 
    { 
     throw new NotImplementedException(); 
    } 

    object IEnumerator.Current 
    { 
     get { return Current; } 
    } 
} 

E poi codice per leggere e fondere (dovrebbe essere riscritta per chiarezza in produzione):

// Get the file names and instantiate our helper class 
List<IEnumerator<string>> files = Directory.GetFiles(@"C:\temp\files", "*.txt").Select(file => new MergeFile(file)).Cast<IEnumerator<string>>().ToList(); 
List<string> result = new List<string>(); 
IEnumerator<string> next = null; 
while (true) 
{ 
    bool done = true; 
    // loop over the helpers 
    foreach (var mergeFile in files) 
    { 
     done = false; 
     if (next == null || string.Compare(mergeFile.Current, next.Current) < 1) 
     { 
      next = mergeFile; 
     } 
    } 
    if (done) break; 
    result.Add(next.Current); 
    if (!next.MoveNext()) 
    { 
     // file is exhausted, dispose and remove from list 
     next.Dispose(); 
     files.Remove(next); 
     next = null; 
    } 
} 

Answer 2

sto supponendo che ci potrebbe essere molto di più di dati, allora hai dato nel tuo esempio . Se è possibile aprire tutti i file contemporaneamente, è possibile utilizzare questo algoritmo:

• Leggere la prima riga da ciascun file, in modo da avere 10 righe in memoria, una per ciascun file.
• Inserire le righe in una coda di priorità in base all'ordinamento.
• Estrarre l'elemento meno (ordinato per primo) dalla coda di priorità e scrivere sul file di output.
• Leggi un'altra riga dal file corrispondente dalla quale proviene la linea e la inserisce nella coda di priorità.
• Ripetere fino a quando tutti i file vengono letti fino alla fine.

Si noti che non c'è bisogno di leggere tutti i file in memoria in una sola volta, quindi questo funzionerà bene se si dispone di un numero ragionevole di file di grandi dimensioni, ma non se si dispone di un sacco di file di piccole dimensioni.

Se si dispone di molti piccoli file, è necessario unirli in gruppi per creare un singolo file di output per ciascun gruppo, quindi ripetere il processo per unire questi nuovi gruppi.

In C# è possibile utilizzare ad esempio uno SortedDictionary per implementare la coda di priorità.

Answer 3

Affrontare i commenti nel altra risposta:

Se si dispone di un numero variabile di file, ecco cosa farei. Questo è solo uno schizzo per far passare l'idea; questo codice non viene compilato, ho sbagliato i nomi dei metodi e così via.

// initialize the data structures 
var priorityQueue = new SortedDictionary<Record, Stream>(); 
var streams = new List<Stream>(); 
var outStream = null; 
try 
{ 
    // open the streams. 
    outStream = OpenOutputStream(); 
    foreach(var filename in filenames) 
    streams.Add(GetFileStream(filename)); 
    // initialize the priority queue 
    foreach(var stream in streams) 
    { 
    var record = ReadRecord(stream); 
    if (record != null) 
     priorityQueue.Add(record, stream); 
    // the main loop 
    while(!priorityQueue.IsEmpty) 
    { 
    var record = priorityQueue.Smallest; 
    var smallestStream = priorityQueue[record]; 
    WriteRecord(record, outStream); 
    priorityQueue.Remove(record); 
    var newRecord = ReadRecord(smallestStream); 
    if (newRecord != null) 
     priorityQueue.Add(newRecord, smallestStream); 
    } 
} 
finally { clean up the streams } 

Ha senso? Continui a prendere la cosa più piccola dalla coda di priorità e la sostituisci con il record successivo in quel flusso, se ce n'è uno. Alla fine la coda sarà vuota e sarai fatto.

Answer 4

Direi di non utilizzare la coda di priorità, non utilizzare IEnumerable. Entrambi sono molto lenti.

Ecco un modo veloce per ordinare o unire file ordinati in memoria esterna:

http://www.codeproject.com/KB/recipes/fast_external_sort.aspx