實現外部合併排序

我在學習Python，並且正在使用帶ints的輸入文件進行外部合併排序。我使用heapq.merge，並且我的代碼幾乎可以工作，但它似乎將我的行排序爲字符串而不是整數。如果我嘗試轉換爲整數，writelines將不接受數據。任何人都可以幫我找到替代方案嗎？另外，我是正確的思維，這將讓我排序文件比內存大實現外部合併排序

import itertools 
from itertools import islice 
import tempfile 
import heapq 

#converts heapq.merge to ints 
#def merge(*temp_files): 
# return heapq.merge(*[itertools.imap(int, s) for s in temp_files]) 

with open("path\to\input", "r") as f: 
    temp_file = tempfile.TemporaryFile() 
    temp_files = [] 
    elements = [] 
    while True: 
     elements = list(islice(f, 1000)) 
     if not elements: 
      break 
     elements.sort(key=int) 
     temp_files.append(elements) 
     temp_file.writelines(elements) 
     temp_file.flush() 
     temp_file.seek(0) 
     with open("path\to\output", "w") as output_file: 
      output_file.writelines(heapq.merge(*temp_files))

來源

2015-05-27 user2361820

您的代碼沒有多大意義，我（temp_files.append(elements)內環路合併？），但這裏的合併文件數字排序的方式：

首先map(int, ...)打開每個文件的行成整型。然後那些與heapq.merge合併。然後map('{}\n'.format將每個整數都換成一個字符串，換行。然後writelines寫入這些行。換句話說，你已經很近了，只需要在寫入之前將ints轉換回字符串。

一種不同的方式來寫它（可能是一些更清晰）：

import heapq 
files = open('a.txt'), open('b.txt') 
with open('merged.txt', 'w') as out: 
    int_streams = (map(int, f) for f in files) 
    int_stream = heapq.merge(*int_streams) 
    line_stream = map('{}\n'.format, int_stream) 
    out.writelines(line_stream)

在任何情況下，你如果你正在使用Python 2否則它會讀取整個文件到使用itertools.imap記憶一次。在Python 3中，您可以使用正常的map。

是的，如果你做得對，這將允許你用很少的內存來排序巨大的文件。

來源

2015-05-27 23:30:24

謝謝 out.writelines（地圖（「{} \ n'.format， heapq.merge（*（圖（INT，F）在文檔F））））是缺少的部分我試圖找到。 – user2361820

你的元素被默認爲字符串讀取（給予足夠的磁盤空間），你必須做一些事情，如：

elements = list(islice(f, 1000)) 
elements = [int(elem) for elem in elements]

因此它們會被解釋爲整數。

這也將意味着你需要將它們轉換回到串寫，例如：

temp_file.writelines([str(elem) for elem in elements])

從

除了時，您將需要再次轉換的元素爲int的最終合併。在你的情況下，你可能想取消你的merge方法的註釋（然後再把結果轉換回字符串，就像上面一樣）。

來源

2015-05-27 21:59:29 Ashalynd

他需要str（）類型轉換之前做writelines？ – sudhishkr

啊，是的，也是。 – Ashalynd

我試過了，但是書寫筆不會接受整數。有另一種方法嗎？ – user2361820

實現外部合併排序

回答

相關問題