[算法] 位图排序
初始化于: 2013-09-10
更新: 2013-09-18
《编程珠玑(第2版)》第1章 开篇
问题描述:
输入: 一个最多包含n个正整数的文件, 每个数都小于n, 且n=10^7. 如果在输入文件中有任何整数重复出现就是致使错误. 没有其他数据与该整数相关联.
输出: 按升序排列的输入整数的列表.
约束: 最多有(大约)1MB的内存空间可用, 有充足的磁盘存储空间可用. 运行时间最多几分钟, 运行时间为10秒就不需要进一步优化了.
位图数据结构: 该数据结构描述了一个有限定义域内(有范围)的稠密集合, 其中的每一个元素最多出现一次(不重复)并且没有其他任何数据与该元素相关联. 即使这些条件没有完全满足(例如, 存在重复元素或额外的数据), 也可以用有限定义域内的键作为一个表项更复杂的表格的索引.
三个阶段:
- 将所有的位都置为0, 从而将集合初始化为空.
- 通过读入文件中的每个整数来建立集合, 将每个对应的位置都置为1.
- 检验每一位, 如果该位为1, 就输出对应的整数, 由此产生有序的输出文件.
问题: 找出1到10^7中没有出现的两个数字
这个没啥好想的了...这里主要是了解bitarray模块的使用, 顺便与bitstring模块进行比较. bitstring模块速度比bitarray模块慢很多, 内存占用也比较多.
#--coding: utf8 --
from bitarray import bitarray
def use_bitarray(seq):
ba = bitarray(10000000)
ba.setall(0)
for i in seq:
ba[i] = 1
for i in range(1, len(ba.to01())):
if ba[i] == 0:
print(i)
from bitstring import BitArray
def use_bitstring(seq):
BA = BitArray(length=10000000)
for i in seq:
BA.set(1, i)
for i in range(1, len(BA)):
if BA[i] == 0:
print(i)
# 初始化10w个数, 打乱, 移除两个数
import random
seq = [i for i in range(10000000)]
random.shuffle(seq)
seq.pop()
seq.pop()
import cProfile
cProfile.run('use_bitarray(seq)') # 8.063 seconds
cProfile.run('use_bitstring(seq)') # 169.849 seconds
相关文章:
程序员编程艺术：第十章、如何给10^7个数据量的磁盘文件排序