Python-Klasse sortierte Dateien zusammenführen, wie können diese verbessert werden?

Question

Hintergrund:

Ich bin die Reinigung groß tabstoppgetrennten Dateien (nicht im Speicher gehalten werden). Als ich die Eingabedatei reinigen, baue ich eine Liste im Speicher nach oben; wenn es um eine Million Einträge (über 1 GB Speicher) bekommt ich es sortieren (den Standardschlüssel unter Verwendung) und die Liste in eine Datei schreiben. Diese Klasse ist die sortierten Dateien für die Zusammenstellung zurück. Es funktioniert auf die Dateien, die ich bisher erlebt habe. Mein größter Fall so weit, verschmilzt 66 sortierten Dateien.

Fragen:

1. Gibt es Löcher in meiner Logik (wo ist es instabil)?
2. Habe ich implementiert, um den merge-sort Algorithmus korrekt?
3. Gibt es offensichtliche Verbesserungen das könnte gemacht werden?

Beispieldaten:

Dies ist eine Abstraktion einer Linie in einer dieser Dateien:

'hash_of_SomeStringId\tSome String Id\t\t\twww.somelink.com\t\tOtherData\t\n'

Das Essen zum Mitnehmen ist, dass ich 'SomeStringId'.lower().replace(' ', '') als meine Sortierschlüssel verwenden.

Original-Code:

class SortedFileMerger():
    """ A one-time use object that merges any number of smaller sorted 
        files into one large sorted file.

        ARGS:
            paths - list of paths to sorted files
            output_path - string path to desired output file
            dedup - (boolean) remove lines with duplicate keys, default = True
            key - use to override sort key, default = "line.split('\t')[1].lower().replace(' ', '')"
                  will be prepended by "lambda line: ".  This should be the same 
                  key that was used to sort the files being merged!
    """
    def __init__(self, paths, output_path, dedup=True, key="line.split('\t')[1].lower().replace(' ', '')"):
        self.key = eval("lambda line: %s" % key)
        self.dedup = dedup
        self.handles = [open(path, 'r') for path in paths]
        # holds one line from each file
        self.lines = [file_handle.readline() for file_handle in self.handles]
        self.output_file = open(output_path, 'w')
        self.lines_written = 0
        self._mergeSortedFiles() #call the main method

    def __del__(self):
        """ Clean-up file handles.
        """
        for handle in self.handles:
            if not handle.closed:
                handle.close()
        if self.output_file and (not self.output_file.closed):
            self.output_file.close()

    def _mergeSortedFiles(self):
        """ Merge the small sorted files to 'self.output_file'. This can 
            and should only be called once.
            Called from __init__().
        """
        previous_comparable = ''
        min_line = self._getNextMin()
        while min_line:
            index = self.lines.index(min_line)
            comparable = self.key(min_line)
            if not self.dedup:                      
                #not removing duplicates
                self._writeLine(index)
            elif comparable != previous_comparable: 
                #removing duplicates and this isn't one
                self._writeLine(index)
            else:                                   
                #removing duplicates and this is one
                self._readNextLine(index)
            previous_comparable = comparable
            min_line = self._getNextMin()
        #finished merging
        self.output_file.close()

    def _getNextMin(self):
        """ Returns the next "smallest" line in sorted order.
            Returns None when there are no more values to get.
        """
        while '' in self.lines:
            index = self.lines.index('')
            if self._isLastLine(index):
                # file.readline() is returning '' because 
                # it has reached the end of a file.
                self._closeFile(index)
            else:
                # an empty line got mixed in
                self._readNextLine(index)
        if len(self.lines) == 0:
            return None
        return min(self.lines, key=self.key)

    def _writeLine(self, index):
        """ Write line to output file and update self.lines
        """
        self.output_file.write(self.lines[index])
        self.lines_written += 1
        self._readNextLine(index)

    def _readNextLine(self, index):
        """ Read the next line from handles[index] into lines[index]
        """
        self.lines[index] = self.handles[index].readline()

    def _closeFile(self, index):
        """ If there are no more lines to get in a file, it 
            needs to be closed and removed from 'self.handles'.
            It's entry in 'self.lines' also need to be removed.
        """
        handle = self.handles.pop(index)
        if not handle.closed:
            handle.close()
        # remove entry from self.lines to preserve order
        _ = self.lines.pop(index)

    def _isLastLine(self, index):
        """ Check that handles[index] is at the eof.
        """
        handle = self.handles[index]            
        if handle.tell() == os.path.getsize(handle.name):
            return True
        return False

Edit: Die Umsetzung der Vorschläge von Brian ich mit folgenden Lösung kam:

Zweite Änderung: Aktualisiert den Code per John Machin 's Vorschlag:

def decorated_file(f, key):
    """ Yields an easily sortable tuple. 
    """
    for line in f:
        yield (key(line), line)

def standard_keyfunc(line):
    """ The standard key function in my application.
    """
    return line.split('\t', 2)[1].replace(' ', '').lower()

def mergeSortedFiles(paths, output_path, dedup=True, keyfunc=standard_keyfunc):
    """ Does the same thing SortedFileMerger class does. 
    """
    files = map(open, paths) #open defaults to mode='r'
    output_file = open(output_path, 'w')
    lines_written = 0
    previous_comparable = ''
    for line in heapq26.merge(*[decorated_file(f, keyfunc) for f in files]):
        comparable = line[0]
        if previous_comparable != comparable:
            output_file.write(line[1])
            lines_written += 1
        previous_comparable = comparable
    return lines_written

Rau Test

Mit den gleichen Eingabedateien (2,2 GB Daten):

• SortedFileMerger Klasse nahm 51 Minuten (3068,4 Sekunden)
• Brian 's Lösung dauerte 40 Minuten (2408,5 Sekunden)
• Nach der Zugabe von John Machin 's Vorschläge, die Lösung Code dauerte 36 Minuten (2214,0 Sekunden)

Answer 1

Beachten Sie, dass in python2.6, heapq einen neuen zu fusionieren Funktion, die dies für Sie tun wird.

die benutzerdefinierte Tastenfunktion umgehen, können Sie einfach die Datei Iterator wickeln mit etwas, das sie schmückt, so dass es auf dem Schlüssel basiert vergleicht, und es Streifen aus danach:

def decorated_file(f, key):
    for line in f: 
        yield (key(line), line)

filenames = ['file1.txt','file2.txt','file3.txt']
files = map(open, filenames)
outfile = open('merged.txt')

for line in heapq.merge(*[decorated_file(f, keyfunc) for f in files]):
    outfile.write(line[1])

[Bearbeiten] Auch in früheren Versionen von Python, es ist einfach wahrscheinlich lohnt sich, die Umsetzung der Zusammenführung aus dem später heapq Modul zu nehmen. Es ist reiner Python und läuft unmodifizierte in python2.5, und da es einen Haufen verwendet das nächste Minimum bekommen sollte sehr effizient sein, wenn ein große Anzahl von Dateien zusammenführen.

Es soll möglich sein, einfach die heapq.py von einer python2.6 Installation zu kopieren, kopieren Sie sie in Ihre Quelle als „heapq26.py“ und verwenden „from heapq26 import merge“ - es gibt keine 2.6 Besonderheiten darin verwendet. Alternativ können Sie auch nur die Merge-Funktion kopieren (Umschreiben der heappop etc ruft die python2.5 heapq Modul zu verweisen).

Answer 2

<< Diese „Antwort“ ist ein Kommentar auf den resultierenden Code ursprünglichen Fragesteller >>

Vorschlag: Verwendung von eval () ist ummmm und etwas Sie tun, schränkt den Anrufer Lambda mit - Taste Extraktion mehr als ein Einzeiler erfordern, und in jedem Fall brauchen Sie nicht die gleiche Funktion für die vorläufigen Schritt sortieren?

diesen So ersetzen:

def mergeSortedFiles(paths, output_path, dedup=True, key="line.split('\t')[1].lower().replace(' ', '')"):
    keyfunc = eval("lambda line: %s" % key)

mit dieser:

def my_keyfunc(line):
    return line.split('\t', 2)[1].replace(' ', '').lower()
    # minor tweaks may speed it up a little

def mergeSortedFiles(paths, output_path, keyfunc, dedup=True):