我正在嘗試按升序列印包含隨機生成的大數字的 1GB 檔案。這是我用來為我的測驗生成亂數的代碼（在此處找到）。
import random
import math
afile = open("./Random.txt", "w" )
digits=1000000000
finalNumber = ""
for i in range(digits // 16):
finalNumber = finalNumber str(math.floor(random.random() * 10000000000000000))
finalNumber = finalNumber str(math.floor(random.random() * (10 ** (digits % 16))))
afile.write(finalNumber)
afile.close()
下面的 python 代碼可以正常作業，只需要不到 4 分鐘。但有人告訴我這可以在大約 15 秒內完成，而且我可能根本不需要對數字進行排序以按順序列印，這有點令人費解。
這不是作業，而是我在求職面試中被問到的一個問題，我沒有設法解決，并且不知道解決方案讓我喪命。我沒有被要求在任何特定語言上執行此操作，但我決定使用 python，因為我熟悉該語言。我對使用 bash 進行了快速測驗，但它已經在使用 10MB 檔案為我的腳本苦苦掙扎。
# Sort integers in ascending order
import sys
import os
import shutil
# Count for the chunks
count = 0
# Generate 100MB chunks
def read_in_chunks(file_object, chunk_size=1024*102400):
while True:
data = file_object.read(chunk_size)
if not data:
break
yield data
#Do a mergesort of the chunks.
def merge_files(outfile):
words = []
for f in os.listdir('./tmp/'):
if os.path.isfile('./tmp/' f):
file_ = open('./tmp/' f)
words.append(file_.readlines())
# Sort in-memory
words.sort()
with open(outfile, 'w') as out:
out.write(str(words))
with open(sys.argv[1]) as line:
#If tmp folder not exist create it
if os.path.exists('./tmp/'):
shutil.rmtree('./tmp/')
os.mkdir('./tmp/')
for chunk in read_in_chunks(line):
# Sort each chunk
ascending = "".join(sorted(str(chunk)))
#write chunk to disk
with open(f"./tmp/out_{count}.txt", mode="w") as fw:
fw.writelines(ascending)
count = 1
#merge all chunks into a single file with mergesort
merge_files('finalout.txt')
shutil.rmtree('./tmp/')
這基本上將檔案分塊在 100MB 的臨時檔案上，對每個塊進行排序，然后進行合并排序以附加它們。只需對檔案進行排序就會導致“MemoryError”
我還嘗試使用 for 讀取檔案一次并執行一系列 if/else 以將每個值附加到 10 個不同的變數，然后按從 0 到 10 的順序列印它們，但這比我的初始方法效率低且慢。
顯然需要有一個“技巧”來解決這個問題。
uj5u.com熱心網友回復：
數字位數的可能值非常有限 - 10 位數字（0 到 9）。出于這個原因，這個問題是使用計數排序的完美候選者。計數排序具有復雜性O(n)，這比任何直接比較排序（如歸并排序）都快。此外，這實際上是您可以實作的最佳復雜性，因為至少您需要讀取數字（這已經是 O(n)，其中n是位數）。
uj5u.com熱心網友回復：
正如大家所指出的，預期的答案是計數排序。
string.sort()但是，要使 python 實作的計數排序優于用 C 撰寫的內置計數排序，需要付出一些額外的努力。避免為資料的每個字符創建一個新的 Python 字串物件尤為重要。
一種解決方案是使用內置的string.sort()，然后呼叫 10string.index()次以獲取每個塊的計數。
我決定使用 10 次呼叫來string.count(). 這是實作：
from collections import defaultdict
counts=defaultdict(int)
with open("./Random.txt") as infile:
while True:
data = infile.read(1000000)
if not data:
break
for digit in "0123456789":
counts[digit] = counts[digit] data.count(digit)
with open("./fastout.txt", mode="w") as outfile:
for digit in "0123456789":
count = counts[digit]
while count > 1000000:
outfile.write(digit*1000000)
count -= 1000000
if count > 0:
outfile.write(digit*count)
您的原始結果：
$ time python3 original.py
real 3m22.689s
user 3m10.143s
sys 0m9.797s
我的結果：
$ time python3 new.py
real 0m14.001s
user 0m13.297s
sys 0m0.471s
我還注意到你的輸出檔案比輸入檔案長一點，所以你在某個地方有一個我沒有費心找到的錯誤。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/491994.html
下一篇：制定高效的組合和填充演算法