我需要對由換行符分隔的大型文本檔案進行排序。
我需要假設輸入資料太大而無法放入主記憶體，這意味著我只能在記憶體中讀取和存盤檔案的一行。因此，我無法制作用于經典排序演算法（如合并排序、快速排序等）的串列或陣列，因此我被卡住了。
一個人怎么能解決這樣的問題？
uj5u.com熱心網友回復：
在實踐中，一般情況下，只需要使用 Unix 的sort命令即可。
LC_ALL=C sort file_in.txt > file_out.txt
對于一個非常大的檔案，我會去分布式使用排序構建到 mapreduce 中。請參閱MapReduce 排序演算法如何作業？關于那個是如何作業的。一個提示，如果你去分布式，保持分布式。也就是說，輸入檔案、輸出檔案和操作都應該在分布式檔案系統上，這樣你就不會在任何一臺機器上遇到瓶頸。
恰好有一次，我遇到了這兩個不起作用的情況。情況是我需要對來自資料庫的資料集進行排序和組織，但資料太大而無法在資料庫中排序，并且我所在的機器沒有空間容納原始資料集。
我用合并排序解決了這個問題，其中所有超過一定大小的塊都保存在壓縮檔案中。關鍵邏輯是這樣的：
for row in big query:
last_chunk = new chunk from row
chunk = None
while 0 < len(chunks):
chunk = chunks.pop()
if chunk.size < 1.2 * last_chunk.size:
last_chunk = merge(chunk, last_chunk)
else:
break
if chunk is not None:
chunks.append(chunk)
chunks.append(last_chunk)
while 1 < len(chunks):
chunks.append(merge(chunks.pop(), chunks.pop()))
然后在合并邏輯中，我推理了一個塊是否應該在記憶體中或壓縮檔案中結束，如何獲取行以及如何撰寫它們。
（我的問題并沒有這么簡單，因為我正在分組、求和、合并等。基本上復制了一個我無法在資料庫中運行的報告，因為它沒有足夠的作業記憶體來運行它。）
這三個涵蓋了我個人遇到的大檔案的所有情況。
這是基于外部檔案的合并排序的一個不是很好但有效的實作。
首先，您需要demo.txt我們要排序：
hello
world
greetings
earthlings
現在 Python 代碼按排序順序列印它：
from tempfile import TemporaryFile
class FileBuffer():
def __init__ (self):
self.current_line = None
self.fh = TemporaryFile()
self.state = 'writing'
self.size = 0
def add (self, line):
if self.state != 'writing':
raise Exception(f"Cannot write to FileBuffer in state {self.state}")
self.size = len(line)
self.fh.write(bytes(line, encoding='utf-8'))
def finish_writing (self):
self.fh.seek(0, 0)
self.state = 'reading'
self.fetch()
return self.current_line
def fetch (self):
if self.state != 'reading':
raise Exception(f"Cannot read from FileBuffer in state {self.state}")
self.current_line = bytes.decode(self.fh.readline())
if self.current_line == '':
self.current_line = None
self.state = 'done'
return self.current_line
def __iter__(self):
return self
def __next__(self):
line = self.current_line
if line is None:
raise StopIteration
else:
self.fetch()
return line
class BufferedSort():
def __init__ (self):
self.buffers = []
def merge (self):
buffer1 = self.buffers.pop()
buffer2 = self.buffers.pop()
new_buffer = FileBuffer()
while buffer1.current_line is not None and buffer2.current_line is not None:
if buffer1.current_line < buffer2.current_line:
new_buffer.add(buffer1.current_line)
buffer1.fetch()
else:
new_buffer.add(buffer2.current_line)
buffer2.fetch()
while buffer1.current_line is not None:
new_buffer.add(buffer1.current_line)
buffer1.fetch()
while buffer2.current_line is not None:
new_buffer.add(buffer2.current_line)
buffer2.fetch()
new_buffer.finish_writing()
self.buffers.append(new_buffer)
def add (self, line):
buffer = FileBuffer()
buffer.add(line)
buffer.finish_writing()
self.buffers.append(buffer)
while 1 < len(self.buffers) and self.buffers[-2].size < 1.2 * self.buffers[-1].size:
self.merge()
def finish_writing(self):
while 2 < len(self.buffers):
self.merge()
def sorted_buffer(self):
self.finish_writing()
if len(self.buffers):
return self.buffers[0]
else:
buffer = FileBuffer()
buffer.state = 'done'
return buffer
def __iter__(self):
return self.sorted_buffer()
sorter = BufferedSort()
with open("demo.txt") as fh:
for line in fh:
sorter.add(line)
for line in sorter:
print(line, end="")
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/514779.html
上一篇：如何按此順序對物件陣列進行排序？