我有大量的产品,数量超庞大,我现在要从文本数据中统计出每两个产品之间的关联,如 Pi和Pj的关联(Pi是可乐,Pj是蛋糕),关联<Pi,Pj>=V. V的值从1到1万不等..那么用什么数据结构存储这个数据好呢?

刘学炜 发布于 2012/04/04 23:54
阅读 300
收藏 0

请教一下,我有大量的产品,数量超庞大,我现在要从文本数据中统计出每两个产品之间的关联,如 Pi和Pj的关联(Pi是可乐,Pj是蛋糕),关联<Pi,Pj>=V. V的值从1到1万不等..那么用什么数据结构存储这个数据好呢? 稀疏矩阵? 如果是稀疏矩阵的话,用什么办法优化查找一个 <Pi,Pj>已经存在于矩阵中呢??

1. 用哈希表来存储, <Pi,Pj>可以用一个哈希函数f(Pi,Pj)来算出一个整数值k,通过k来存取
可以很快地查出是否有关联存在. 此算法查找时间在O(1),但需要预先分配一个足够大的连续空间.

2. <Pi,Pj>应该可以合并成一个32位或64位的整数N, 高16或32位是Pi, 低16或32位是Pj.
然后根据N值来将所有关联插入排序, 推荐用二叉树来进行排序, 这样方便动态存取.
查找的时间为logN, 32至64之间. 虽然时间上比方法1差一点,但由于可以不用预先分配连续空间,
方便动态插入新值.


在数据长度不明的情况下不能轻易的合成吧??

5000万总数据, 还是 Pi 5000万, PJ5000万
如果是后者就不要做了 哈哈 太恐怖, 不知道要做多久, 需要多大存储空间
8650万个32位INT类型需要1G的内存空间(测试环境, 1.5G内存,XP_PESONNAL2,.NET2.0)

数据量这么大, 肯定要分步的, 先做一部分, 保存到文件, 再做一部分保存到文件
如果是.NET一次做500万个关系式 (32位 数组长度限制,申请空间限制,存储空间限制,) 三元组比较合适模式

加载中
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部