请教在大数据量的情况下构建字典的问题

[wanzathe]

有一个二进制格式存储的数据文件test.dat（intA+intB+intC+intD），想根据这个二进制文件创建字典
{(intA,intB):(intC,intD)}：

myDict = {}
input_file = file('./test.dat','rb')
content = input.read()
record_number = len(content) / 16
for i in range(0,record_number):
a = struct.unpack("IIII",content[i*16:i*16+16])
myDict[(a[0],a[1])] = (a[2],a[3])

问题：
因test.dat文件数据量巨大（150M,大概1000w条记录），这么做基本上是不可行的，速度慢，内存占用太厉害:(
目前眼前一片迷茫，还请各位大侠指点一二，万分感激！

[Qiangning Hong]

如果你真的是要一个dict对象的话，下面这段代码应该会内存占用小一些：

f = open('./test.dat','rb')
def g():
while True:
x = f.read(16)
if not x: break
a = struct.unpack('llll', x)
yield (a[0], a[1]), (a[2], a[3])
mydict = dict(g())

如果你仅仅是希望能够用类似dict的方式来访问数据的话，建议你看看shelve模块

--
Qiangning Hong
http://www.douban.com/people/hongqn/

[Albert Lee]

不如直接上数据库吧

[Zoom.Quiet]

On Jan 2, 2008 1:37 PM, Albert Lee <hanzh...@gmail.com> wrote:
> 不如直接上数据库吧
>
收了!
http://wiki.woodpecker.org.cn/moin/MicroProj/2008-01-02

咔咔咔,的确!这么大,真不如使用DB了,
入SQLite 就好,也是种字典哪

--
'''Time is unimportant, only life important!
过程改进乃是开始催生可促生靠谱的人的组织!
'''http://zoomquiet.org
博 @ http://blog.zoomquiet.org/pyblosxom/
维 @ http://wiki.woodpecker.org.cn/moin/ZoomQuiet
豆 @ http://www.douban.com/people/zoomq/
看 @ http://zoomq.haokanbu.com/
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Pls. usage OOo to replace M$ Office. http://zh.openoffice.org
Pls. usage 7-zip to replace WinRAR/WinZip. http://7-zip.org
You can get the truely Freedom 4 software.

[Albert Lee]

你怎么什么都收啊。。

如果在Linux下，也建议尝试下 BDB

[Qiangning Hong]

On Jan 2, 2008 1:43 PM, Albert Lee <hanzh...@gmail.com> wrote:
> 你怎么什么都收啊。。

我也想问这句来着，;)

[yantao]

对于大数据量，基本的处理策略：分块处理/流式处理。不可能把所有数据一次装入内存，但总是可以装入一部分。每次只处理能够处理的数据量。处理后的结果
重新写回磁盘。经过多次扫描，总能完成需要的任务。请参考数据结构与算法中分段归并排序策略，由于不知道你把数据读入内存的后续处理，所以只给一些提
示。

[wanzathe]

衷心感谢Qiangning Hong/Albert Lee/Zoom. Quiet/yantao等各位大侠的指点:)

如此大量的数据直接放入dict结构中确实不合适，看了一下shelve，基本可行，改造代码如下：

import shelve

my_file = file('test.dat','rb')
content = my_file.read()

record_number = len(content) / 16

db = shelve.open('test.dat.db')

for i in range(0,record_number):
a = struct.unpack("IIII",content[i*16:i*16+16])

db[str(a[0])+'_'+str(a[1])] = (a[2],a[3])
db.sync()

内存的问题不存在了，字典的查询速度相当满意:)
数据960W条，创建整个shelve的时间在320秒左右，不知道这个是否还有优化的空间？

Thanks

[yuting cui]

bdb在windows下也能用的说....

在 08-1-2，wanzathe<wanz...@gmail.com> 写道：

[Leo Jay]

要不再试试sqlite?

--
Best Regards,
Leo Jay

[wanzathe]

今天试了一下bsddb，960W条数据，使用hash类型创建数据库需要260秒左右，使用bt类型则需要210秒；两种类型的数据库查询起来都感觉
不到延迟，没有专门测试。以上数据供大家参考。

期待进一步的优化~

[骨头]

BDB当然可以进行优化，py自带的bsddb的使用方法，文档中提到的是比较初级的，可以参考一下bsddb3的使用方法……

 

提高建索引速度，可以通过增加cachesize的方法，减少IO占用。

尤其是象你上面提到的需求，可以考虑采用Queue类型的索引……速度比BT，HASH之类的索引快N倍……

 

另：BSDDB支持事务，日志……有兴趣的可以深入研究……

 

[wanzathe]

拜谢骨头:)

bsddb BT类型, 增加了cachesize, 建立索引消耗时间由原来的210秒减少到140秒。

同时尝试了一下Queue/Recno类型的索引，不过有些问题：
Queue/Recno类型的索引key值必须是数字，不过当这个数字太大的时候程序就不能正常运行了，代码如下，程序运行起来很长时间都不会终止，只
能kill掉:(

import bsddb

db = bsddb.rnopen('test.db','n',cachesize=100000000)
db[1000000000] = 'abc'
db.close()
print ‘done’

Queue/Recno类型的索引在key值范围上是否有限制？还请大家指教~

[骨头]

你的例子中的代码并没有问题，关键是RECNO类型在第一次建立索引的过程中，会从1开始计数进行索引，例如你的Key为1000，在建立的过程中RECNO建立了1至1000的所有索引。如果是一千万，那么这个索引建立的过程当然会慢……

 

Key为32位的整数，对recno类型来说，确实有范围限制，即你的Key值不能大于2147483647。

这个限制在MYSQL之类的数据库中也普遍存在，通常二十一亿条数据的容量已经足够了。

 

但Queue类型不存在这个限制，因为Queue类型允许分文件存储，这样就能将不同的Key值范围放到不同的文件中来实现对Key值的扩充。当然前提是你必须自己写一个key值的转换过程。

 

另外强调一下，Queue类型的速度非常快，尤其是它的允许拆分存储的功能，很适合大量固定长度的数据的存储。