首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 服务器 > 云计算 >

求教一个在两个资料中寻找配对元素的方法

2012-12-30 
求教一个在两个文件中寻找配对元素的方法?有两个文件A和B ,A中任意一行a最多与B中的一行有对应关系,反之亦

求教一个在两个文件中寻找配对元素的方法?
有两个文件A和B ,A中任意一行a最多与B中的一行有对应关系,反之亦然。A和B的行数比较多,大概在100m到300m之间,文件大小大约在2G~4G,文件比较大,所以不能一次将文件载入到内存中。

求教一个时间复杂度比较小的办法,将A和B中有对应关系的各行找出来。

[解决办法]
每行可以理解成一个整数向量,向量的夹角cos=a.b/
[解决办法]
a
[解决办法]
*
[解决办法]
b
[解决办法]

cos越接近于1,代表两个向量越相似。

第一步你可以依次计算文件A每行和这个N维第一维坐标轴(1,0,0,0。。。。)的向量夹角。
保存为数组Arr,这一步需要O(A行数)时间,是线性的扫描。


第二步 对B重复上述操作,保存为哈希Hash,同样是O(B行数)时间数),是线性的扫描。

Arr和Hash长度和大小,可以进入内存是绝对没问题的。

第二步,遍历数组Arr,去查找Hash中有无相同元素,O(A行数)依旧是线性的。
这样你就找到了可疑的行号,再去比对行是否维数相同,是否完全相同。

总体还是O(N)问题。秒杀
[解决办法]
至于存储小数的哈希怎么实现,我不知道你用什么具体语言实现,如果用.Net根本不需要考虑,直接往Dictionnary<T,T>里灌就可以了。

如果不安装.Net开发环境,用记事本写VBS脚本,调用脚本组件Dictionnary,就可以轻松实现哈希,此外VBS还可以实现包括逐行读文件行在内的全部操作,保存为hta文件运行,就具有全部硬盘读写权限。因为是O(N)复杂度,所以你不太需要担心超时的问题。
哥以前当VBS斑竹来着,VBS还是很方便实用的脚本工具,学会了可以利用记事本在Windows机器下干好/坏事,很酷。

热点排行