C# N Weg Merge für externe Sortierung

Question

Was ist der beste Weg, um eine N-Weg-Merge für N sortierte Dateien zu implementieren?

Sagen wir, ich habe 9 sortierte Dateien mit je 10 Datensätzen? Wie füge ich diese Dateien zusammen, um eine große Datei mit 90 sortierten Datensätzen zu erstellen?

Answer 1

Die Strategie hängt möglicherweise von der Datenmenge ab.

1. Wenn Daten im Speicher passen können Sie alle Daten in eine Liste lesen, sortieren sie, und sie schreiben
2. Wenn Sie Duplikate verwenden entfernen möchten wird eine HashSet statt einer Liste
3. Wenn es nicht in den Speicher passen, alle Dateien zum Lesen öffnen, den ersten Datensatz jeder Datei vergleichen und den niedrigsten ausgeben. Dann führe die Datei weiter, die du gelesen hast. Wiederholen Sie alle Dateien, bis sie alle erschöpft sind und in die neue Datei geschrieben wurden.
4. Wenn Du Duplikate entfernen möchtest, gehe wie oben vor, überspringe aber jeden Datensatz, der dem zuletzt geschriebenen Datensatz entspricht.

Hier ist ein Codebeispiel, das N sortierte Textdateien einliest und zusammenführt. Ich habe keine doppelte Überprüfung eingeschlossen, aber es sollte einfach zu implementieren sein.

Zuerst eine Hilfsklasse.

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; } 
    } 
} 

Und dann Code zu lesen und fusionieren (es sollte aus Gründen der Klarheit in der Produktion Refactoring):

// 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

Ich gehe davon aus, dass es viel mehr Daten könnten dann gab Sie in Ihrem Beispiel . Wenn Sie alle Dateien gleichzeitig öffnen können, können Sie diesen Algorithmus verwenden:

Lesen Sie die erste Zeile aus jeder Datei, so haben Sie 10 Zeilen im Speicher, eine aus jeder Datei.

Versetzen Sie die Zeilen in eine Prioritätswarteschlange nach der Sortierreihenfolge.

Das kleinste Element (sortiert zuerst) aus der Prioritätswarteschlange nehmen und in die Ausgabedatei schreiben.

Lesen Sie eine weitere Zeile aus der entsprechenden Datei, aus der die Zeile kam, und fügen Sie diese in die Prioritätswarteschlange ein.

Wiederholen Sie den Vorgang, bis alle Dateien bis zum Ende gelesen wurden.

Beachten Sie, dass Sie nicht alle Dateien gleichzeitig im Speicher ablegen müssen. Dies funktioniert also gut, wenn Sie eine angemessene Anzahl großer Dateien haben, aber nicht, wenn Sie viele kleine Dateien haben.

Wenn Sie viele kleine Dateien haben, sollten Sie sie in Gruppen zusammenführen, um eine einzelne Ausgabedatei für jede Gruppe zu erstellen, und dann den Vorgang wiederholen, um diese neuen Gruppen zusammenzuführen.

In C# können Sie zum Beispiel eine SortedDictionary verwenden, um die Prioritätswarteschlange zu implementieren.

Answer 3

die Kommentare in der anderen Antwort Adressierung:

Wenn Sie eine variable Anzahl von Dateien haben, hier ist was ich tun würde. Dies ist nur eine Skizze, um die Idee zu vermitteln; Dieser Code kompiliert nicht, ich habe die Methodennamen falsch angegeben und so weiter.

// 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 } 

Macht das Sinn? Sie greifen einfach das kleinste Ding aus der Prioritätswarteschlange und ersetzen es durch den nächsten Datensatz in diesem Stream, falls es einen gibt. Schließlich wird die Warteschlange leer sein und Sie werden fertig sein.

Answer 4

Ich würde sagen, keine Prioritätswarteschlange verwenden, IEnumerable nicht verwenden. Beide sind sehr langsam.

Hier ist eine schnelle Art und Weise sortierte Dateien im externen Speicher zu sortieren oder zu fusionieren:

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