Класс Python для объединения отсортированных файлов, как это можно улучшить?
-
05-07-2019 - |
Вопрос
Предыстория:
Я очищаю большие (не могут храниться в памяти) файлы, разделенные табуляцией.Когда я очищаю входной файл, я создаю список в памяти;когда он достигает 1 000 000 записей (около 1 ГБ в памяти) Я сортирую его (используя приведенный ниже ключ по умолчанию) и записываю список в файл.Этот класс предназначен для объединения отсортированных файлов обратно вместе.Это работает с файлами, с которыми я сталкивался до сих пор.Мой самый большой случай, на данный момент, - это объединение 66 отсортированных файлов.
Вопросы:
- Есть ли дыры в моей логике (где она хрупкая)?
- Правильно ли я реализовал алгоритм сортировки слиянием ?
- Есть ли какие-либо очевидные улучшения которые можно было бы внести?
Примерные данные:
Это абстракция строки в одном из этих файлов:
'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
Редактировать: Реализация предложений от Брайан Я пришел к следующему решению:
Вторая Правка: Обновил код на Джон Мачинпредложение от '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 секунды)
- Брайанрешение заняло 40 минут (2408,5 секунды).
- После добавления Джон Мачинпредложения, код решения занял 36 минут (2214,0 секунды)
Решение
Обратите внимание, что в python2.6 heapq имеет новый слияние функция, которая сделает это за вас.
Чтобы обработать пользовательскую функцию ключа, вы можете просто обернуть итератор файла чем-то, что украшает его так, чтобы он сравнивался на основе ключа, и впоследствии удалить его:
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, вероятно, стоит просто взять реализацию merge из более позднего модуля heapq.Это чистый python и выполняется без изменений в python2.5, и поскольку он использует кучу для получения следующего минимума, он должен быть очень эффективным при объединении большого количества файлов.
Вы должны быть в состоянии просто скопировать heapq.py из установки python2.6, скопируйте его в свой исходный код как "heapq26.py" и используйте "from heapq26 import merge
" - в нем не используются какие-либо специфические функции 2.6.В качестве альтернативы, вы могли бы просто скопировать функцию слияния (переписав вызовы heappop и т.д. Для ссылки на модуль python2.5 heapq).
Другие советы
<< Этот "ответ" является комментарием к исходному результирующему коду спрашивающего >>
Предложение:использование eval() - это ummmm, и то, что вы делаете, ограничивает вызывающего абонента использованием lambda - извлечение ключа может потребовать больше, чем однострочное, и в любом случае, разве вам не нужна та же функция для предварительного этапа сортировки?
Так что замените это:
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):