开发学院软件开发Python 使用Python在2M内存中排序一百万个32位整数 阅读

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

 2010-09-22 11:14:41 来源:WEB开发网   
核心提示:有人开玩笑地问我 如何使用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秒:

1 2  下一页

Tags:使用 Python 内存

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
更多精彩
    赞助商链接

    热点阅读
      焦点图片
        最新推荐
          精彩阅读