首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

今天遇到的一道很困难的笔试题,海量数据的,该怎么解决

2012-04-25 
今天遇到的一道很困难的笔试题,海量数据的现有两个文件文件一3000w条数据格式是id1 id2文件二是5000w数据

今天遇到的一道很困难的笔试题,海量数据的
现有两个文件
文件一3000w条数据
格式是
id1 id2  
文件二是5000w数据
格式也是 id1 id2 表示id1引用id2 ,文件二的id1 id2如果没有和文件一的id1 id2匹配的话就无效
以上id都是int型
现在要求的是文件一中每一行 一次间接引用的个数,写到每行的末尾 ,举个例子
文件一是
1111 3333
1111 4444

文件二是
1111 2222
2222 3333
1111 5678
5678 3333

那么我逐行把文件一的数据作为输入
首先是 1111 3333
那么看文件二因为 1111->5678->3333 所以文件一中1111 3333这行间接引用是1,补到末尾。注意是一次间接引用,直接引用或者多次间接无效。 而1111->2222->3333不算 因为1111-》2222 , 2222->3333在文件一中均不存在。
之后再运行 1111 4444作为输入

[解决办法]
描述看不明白,没法思考下去。

你是不是说这样的意思:

如果文件1里的id1、id2组合能够在文件二里找到这么两条组合:[文件1].id1=[文件2].id1时,以[文件2]中当前记录的id2作为id1,以文件1中当前的id2作为id2,可在文件2中找到一条匹配记录。此时则称之为发生了一次间接引用?
[解决办法]

探讨

我的想法:

1、将文件二完全读入内存。不算太大,50M*8=400M字节。
2、对其进行排序,将id1与id2结合起来看做是一个long long类型的64位整数键。
3、对文件一的每一条记录做如下查询处理:
3a) 首先用id1在文件二上以二分法查找,找到后取出文件2中的id2。
3b) 用文件2的id2做高位,文件1的id2做低位构成一个64位键。
3c) 在文件二数组中二分……

热点排行