정렬 된 파일을 병합하기 위해 Python 클래스는 어떻게 개선 할 수 있습니까?
https://stackoverflow.com/questions/1001569
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
배경:
나는 크게 청소하고 있습니다 (메모리에서 유지할 수 없음) 탭으로 연결된 파일. 입력 파일을 청소하면 메모리에 목록을 작성합니다. 1,000,000 개의 항목 (메모리에서 약 1GB)에 도달하면 (아래 기본 키를 사용하여) 정렬하고 목록을 파일에 씁니다. 이 클래스는 정렬 된 파일을 다시 정리하기위한 것입니다. 지금까지 발생한 파일에서 작동합니다. 지금까지 가장 큰 경우는 66 개의 정렬 된 파일을 병합하고 있습니다.
질문:
- 내 논리에 구멍이 있습니까 (깨지기 쉬운 곳)?
- Merge-Sort 알고리즘을 올바르게 구현 했습니까?
- 명백한 개선 사항이 있습니까?
예제 :
이것은 이러한 파일 중 하나에서 라인의 추상화입니다.
'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
편집하다: 제안을 구현합니다 브라이언 다음 해결책을 제시했습니다.
두 번째 편집 : 코드 당 업데이트되었습니다 존 기계제안 :
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.2GB 데이터) :
해결책
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에서도 후기 HeaPQ 모듈에서 병합을 구현하는 것이 좋습니다. 순수한 파이썬이며 Python2.5에서 수정되지 않은 실행되며, 힙을 사용하여 다음 최소값을 얻으므로 많은 파일을 병합 할 때 매우 효율적이어야합니다.
Python2.6 설치에서 heapq.py를 간단히 복사하고 소스에 "heapq26.py"로 복사하여 사용하십시오. "from heapq26 import merge" - 2.6 개의 특정 기능이 사용되지 않습니다. 또는 Merge 기능을 복사 할 수 있습니다 (Heappop 등 호출을 다시 작성하여 Python2.5 heapq 모듈을 참조하십시오).
다른 팁
<<이 "답변"은 원래 질문자의 결과 코드에 대한 의견입니다 >>
제안 : Eval ()을 사용하는 것은 ummmm이며, 당신이 수행하는 일은 발신자에게 Lambda 사용으로 제한됩니다. 키 추출은 1 라이너 이상이 필요할 수 있으며, 어쨌든 예비 정렬 단계에 동일한 기능이 필요하지 않습니까?
그래서 이것을 교체하십시오 :
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):
