使用Python在2M内存中排序一百万个32位整数

核心提示：有人开玩笑地问我 如何使用python在2M内存中排序一百万个32位整数.为了应付这个挑战,我学习了一下缓冲I/O.很 明显,这是一个开玩笑的问题.假设是二进制编码,单单是数据就已经占了4M!唯一的解释就是: 给定一个包含一百万个32位整数的文件,你如何使用最少内存去排序好它们?这可能需要使用某种合并排序的方式,把数据

有人开玩笑地问我 如何使用python在2M内存中排序一百万个32位整数.为了应付这个挑战,我学习了一下缓冲I/O.

很 明显,这是一个开玩笑的问题.假设是二进制编码,单单是数据就已经占了4M!唯一的解释就是: 给定一个包含一百万个32位整数的文件,你如何使用最少内存去排序好它们?这可能需要使用某种合并排序的方式,把数据分块在内存排序,并保存到临时文件中 去,最后把临时文件合并获得最终结果.

下面是我的解决方案,稍候会解释.

注意:所有的例子都是使用python3.0. 这个例子的不同之处就是使用file.buffer访问二进制流的方式去访问字符流文件.

#!/usr/bin/env python3.0
import sys, array, tempfile, heapq
assert array.array('i').itemsize == 4
def intsfromfile(f):
　while True:
　　a = array.array('i')
　　a.fromstring(f.read(4000))
　　if not a:
　　　　break
　　for x in a:
　　　　yield x
iters = []
while True:
　a = array.array('i')
　a.fromstring(sys.stdin.buffer.read(40000))
　if not a:
　　　break
　f = tempfile.TemporaryFile()
　array.array('i', sorted(a)).tofile(f)
　f.seek(0)
　iters.append(intsfromfile(f))
a = array.array('i')
for x in heapq.merge(*iters):
　a.append(x)
　if len(a) >= 1000:
　　　a.tofile(sys.stdout.buffer)
　　　del a[:]
if a:
　a.tofile(sys.stdout.buffer)

在 我的Goole桌面(一个使用了3年,跑着Googlified Linux的个人电脑,用Python3.0的pystones测试得分是34000),在输入文件包含一百万个32位随机整数的情况下,这个程序大概花 了5.4秒.还不太差,如果直接在内存中排序大概需要2秒: