使用Python在2M内存中排序一百万个32位整数
2010-09-22 11:14:41 来源:WEB开发网有人开玩笑地问我 如何使用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秒:
- ››使用脚本恢复WinXP系统的用户登录密码
- ››使用phpMyadmin创建数据库及独立数据库帐号
- ››使用Zend Framework框架中的Zend_Mail模块发送邮件...
- ››使用cout标准输出如何控制小数点后位数
- ››使用nofollow标签做SEO的技巧
- ››使用 WebSphere Message Broker 的 WebSphere Tra...
- ››使用SQL Server事件探查器做应用程序的性能分析
- ››使用SQL Server事件探查器分析死锁原因
- ››使用纯文本文件打造WCF服务
- ››使用 Dojo 开发定制 Business Space 小部件,第 4...
- ››使用 ADDRESS 与 INDIRECT函数查询信息
- ››使用 COLUMN函数编制单元信息
更多精彩
赞助商链接