8
Tło:Klasa Pythona do scalania posortowanych plików, jak można to poprawić?
jestem czyszczenia duży (nie mogą być przechowywane w pamięci) pliki tabulatorami. Podczas czyszczenia pliku wejściowego tworzę listę w pamięci; kiedy osiąga 1 000 000 wpisów (około 1 GB w pamięci), sortuję go (używając domyślnego klucza poniżej) i zapisuję listę do pliku. Ta klasa służy do ponownego posortowania posortowanych plików. Działa na plikach, które spotkałem do tej pory. Moim największym przypadkiem, jak dotąd, jest scalenie 66 posortowanych plików.
Pytania:
- Are tam dziury w moim logiki (gdzie jest on kruchy)?
- Czy poprawnie zaimplementowałem algorytm scalania ?
- Czy są jakieś oczywiste ulepszenia, które można by ulepszyć ?
Przykład Dane:
To jest abstrakcją linii w jednym z tych plików:
'hash_of_SomeStringId\tSome String Id\t\t\twww.somelink.com\t\tOtherData\t\n'
wynos jest to, że używam 'SomeStringId'.lower().replace(' ', '') jak mój klucz sortowania.
Original Kod:
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: Wdrażanie sugestii Brian wymyśliłem następujące rozwiązanie:
Druga Edycja: uaktualniony kod za John Machin „s sugestię :
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
surowca testu
za pomocą tego samego pliku wejściowego (2.2 GB danych)
- klasy SortedFileMerger trwało 51 minut (3068.4 sekund)
- Brian jest rozpuszczenia 40 minut (2408.5 sekund)
- Po dodaniu sugestii John Machin, , kod rozwiązania zajęł 36 minut (2214.0 sekund)
decorated_file jest równoważna ((klucz (linia), linia) dla linii f) –
@gnibbler, Will, że przyspieszenie proces lub po prostu pozbyć się funkcji? – tgray