Класс Python для объединения отсортированных файлов, как это можно улучшить?

Question

фон:

Я очистки большой (не может удерживаться в памяти) табуляция файлы с разделителями. Когда я очищаю входной файл, я создаю список в памяти; когда он достигает 1 000 000 записей (около 1 ГБ в памяти), я сортирую его (используя ключ по умолчанию ниже) и записываю список в файл. Этот класс предназначен для объединения сортированных файлов. Он работает над файлами, с которыми я столкнулся. До сих пор мой самый большой случай объединяет 66 отсортированных файлов.

Вопросы:

1. Существуют ли дыры в моей логике (где она хрупкая)?
2. Я правильно выполнил алгоритм слияния-сортировки ?
3. Есть ли очевидные улучшения , которые могут быть сделаны?

Пример данных:

Это абстракция линии в одном из этих файлов:

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

вынос в том, что я использую 'SomeStringId'.lower().replace(' ', '') как мой ключ сортировки.

Оригинальный код:

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: Реализация предложений от Brian я придумал следующее решение:

Второе редактирование: Обновленный код на John Machin «s предложение :

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 

Грубый Тест

Используя те же входные файлы (2,2 ГБ данных):

• класс SortedFileMerger занял 51 минут (3068.4 секунд)
• Brian «ы раствора потребовалось 40 минут (2408,5 секунд)
• После добавления предложений John Machin, решение приняло 36 минут (2214,0 секунд)

Answer 1

Обратите внимание, что в python2.6 у heapq есть новая функция merge, которая сделает это за вас.

Для обработки пользовательской функции клавиш, вы можете просто обернуть файл итератор с чем-то, что украшает его так, что он сравнивает на основе ключа, и лишить его потом:

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]) 

[Редактировать] Даже в более ранних версиях python, вероятно, стоит просто взять реализацию слияния из более позднего модуля heapq. Это чистый python и работает без изменений в python2.5, и поскольку он использует кучу, чтобы получить следующий минимум, должен быть очень эффективным при слиянии большого количества файлов.

Вы должны просто скопировать файл heapq.py из установки python2.6, скопировать его в исходный код как «heapq26.py» и использовать «from heapq26 import merge» - в нем нет 2.6 конкретных функций. В качестве альтернативы, вы можете просто скопировать функцию слияния (переписывая вызовы heappop etc для ссылки на модуль heapq python2.5).

Answer 2

< < Этот «ответ» является комментарием к полученному коду исходного спрашивающий в >>

Предложение: использование Eval() является Ummmm и то, что вы делаете, ограничивающее вызывающему использования лямбда - ключ извлечения может потребоваться больше, чем однострочный, и в любом случае вам не нужна такая же функция для предварительного шага сортировки?

Так заменить это:

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

с этим:

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):