Algorithmus für die Zusammenführung von großen Dateien

Question

Ich habe mehrere Protokolldateien von Veranstaltungen (ein Ereignis pro Zeile). Die Protokolle können möglicherweise überlappen. Die Protokolle werden erzeugt auf separaten Client-Rechner von möglicherweise mehreren Zeitzonen (aber ich nehme ich die Zeitzone kennen). Jedes Ereignis hat einen Zeitstempel, die in eine gemeinsame Zeit normalisiert wurde (durch instantianting jeder Protokoll-Parser Kalender-Instanz mit der Zeitzone entsprechend die Protokolldatei und dann getTimeInMillis mit der UTC-Zeit zu bekommen). Die Protokolle werden bereits nach dem Zeitstempel sortiert. Mehrere Ereignisse zur gleichen Zeit auftreten können, aber sie sind nicht gleich Ereignisse bedeutet.

Diese Dateien können relativ groß sein, wie in, 500000 Ereignisse oder mehr in einem einzigen Log, so den gesamten Inhalt der Protokolle in ein einfaches Ereignis Lesung [] ist nicht möglich.

Was ich tue, ich versuche, ist die Ereignisse von jedem der Protokolle in einer einzigen Protokoll fusionieren. Es ist ein bisschen wie eine mergesort Aufgabe, aber jedes Protokoll bereits sortiert ist, ich brauche nur um sie zusammen zu bringen. Die zweite Komponente ist, dass das gleiche Ereignis kann in jeder der getrennten Protokolldateien bezeugt werden, und ich möchte zu „entfernen Sie doppelte Ereignisse“ in der Datei Ausgabeprotokoll.

Kann diese „in place“, wie es in der Reihe nach durchgeführt werden Arbeiten über einige kleine Puffer jeder Protokolldatei? Ich kann nicht einfach in allen Dateien in ein Ereignis lesen [], um die Liste zu sortieren, und dann Duplikate entfernen, aber so weit meine begrenzten Programmierfähigkeiten mich nur ermöglichen dies als die Lösung zu sehen. Gibt es einen anspruchsvollere Ansatz, dass ich verwenden kann, um dies zu tun, wie ich Ereignisse von jedem der Protokolle gleichzeitig lesen?

Answer 1

1. Lesen Sie die erste Zeile von jedem der Protokolldateien

2. LOOP

   a. Finden Sie die "früheste" -Zeile.

   b. Legen Sie die „früheste“ Zeile in die Master-Protokolldatei

   c. Lesen Sie die nächste Zeile aus der Datei, die die früheste Zeile enthalten

Sie können nach Duplikaten zwischen b und c überprüfen, um den Zeiger für jede dieser Dateien voran.

Answer 2

Sicher - jede Protokolldatei öffnen. in der ersten Zeile für jedes in ein Array von ‚aktuellen‘ Zeilen lesen. Dann holen wiederholt die Zeile mit dem niedrigsten Zeitstempel aus dem aktuellen Array. Schreiben Sie es auf den Ausgang, und lesen Sie eine neue Zeile aus der entsprechenden Quelldatei zu ersetzen.

Hier ist ein Beispiel in Python, aber es macht guten Pseudo-Code, auch:

def merge_files(files, key_func):
    # Populate the current array with the first line from each file
    current = [file.readline() for file in files]
    while len(current) > 0:
        # Find and return the row with the lowest key according to key_func
        min_idx = min(range(len(files)), key=lambda x: return key_func(current[x]))
        yield current[min_idx]
        new_line = files[min_idx].readline()
        if not new_line:
            # EOF, remove this file from consideration
            del current[min_idx]
            del files[min_idx]
        else:
            current[min_idx] = new_line

Answer 3

Zur Kasse diesen Link: http : //www.codeodor.com/index.cfm/2007/5/10/Sorting-really-BIG-files/1194

• Verwenden einen Heap (basierend auf einem Array). Die Anzahl der Elemente in diesem Haufen / Array wird auf die Anzahl der Log-Dateien, die Sie haben.

gleich

• Lesen Sie die ersten Datensätze aus allen Dateien und fügen Sie sie in Ihrem Heap.

• Schleife bis (nicht mehr Datensätze in eine der Dateien)

      > remove the max element from the heap
      > write it to the output
      > read the next record from the file to which the (previous) max element belonged
          if there are no more records in that file
              remove it from file list
              continue
      > if it's not the same as the (previous) max element, add it to the heap

Jetzt haben Sie alle Ihre Ereignisse in einer Protokolldatei, werden sie sortiert, und es gibt keine Duplikate. Die Zeitkomplexität des Algorithmus (n k log), wobei n die Gesamtzahl der Datensätze ist und k die Anzahl der Protokolldateien.

Sie sollten gepufferte Reader verwenden und gepuffert Writer-Objekte, wenn vom und zum Lesen von Dateien die Anzahl zu minimieren Platten lesen und schreiben, um Zeit zu optimieren.

Answer 4

Wir waren nötig chronologisch mehr Log-Dateien mit mehreren Zeilen pro Protokolleintrag (Java-Anwendungen tun dies oft - ihr Stack-Traces sind gleich) zu verschmelzen. Ich beschloss, den einfachen Shell + Perl-Skript zu implementieren. Es umfasst unsere Aufgaben. Wenn Sie daran interessiert sind - folgen durch den Link http://code.google.com/p/logmerge /

Answer 5

Lesen Sie nur eine Zeile zu einem Zeitpunkt von beiden Quelldateien. Vergleichen Sie die Zeilen und schreiben Sie die älteren in die Ausgabedatei (und in der nächsten Zeile). Tun Sie dies, bis Sie das Ende der beiden Dateien erreicht, und Sie haben die Dateien zusammengeführt werden.

Und stellen Sie sicher, um Duplikate zu entfernen:)

Ich denke, diesen Code in C #, um den Ansatz erläutern kann:

        StringReader fileStream1;
        StringReader fileStream2;
        Event eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
        Event eventCursorFile2 = Event.Parse(fileStream2.ReadLine());

        while !(fileStream1.EOF && fileStream2.EOF)
        {
            if (eventCursorFile1.TimeStamp < eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
            }
            else if (eventCursorFile1.TimeStamp == eventCursorFile2.TimeStamp)
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile1 = Event.Parse(fileStream1.ReadLine());
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }
            else
            {
                WriteToMasterFile(eventCursorFile1);
                eventCursorFile2 = Event.Parse(fileStream2.ReadLine());
            }  
        }

Die Abbruchbedingung ist nicht ganz richtig, da dies nur Quick'n'Dirty ist, aber es sollte ähnlich aussehen ..

Answer 6

oder Sie konnten ein Protokoll Merge Dienstprogramm von Awstats borgen, die ein Open-Source-Website-Statistik-Tool ist.

logresolvemerge.pl ist ein perl-Skript, das mehrere Protokolldateien zusammenführen können: Sie können sogar mehrere Threads verwenden, um die Log-Dateien zusammenführen (müssen perl 5.8 für Multi-Thread-Anwendung haben). Warum versuchen Sie nicht ein leicht verfügbares Werkzeug anstelle eines zu bauen?