【 亿级数据 】求 A中不存在B 的区间 高效算法
本帖最后由 zengzhan 于 2013-09-04 12:54:34 编辑 闭区间 排好序了的 递增
———————A———————————--
[2,10]
[11,30]
[35,48]
[49,50]
[54,70]
[73,100]
几十万个区间 [m,n] n最大值为几十亿的了
———————B———————————--
[1,8]
[10,20]
[21,30]
[32,48]
[49,50]
[51,66]
[69,121]
几十万个区间 [m,n] n最大值为几十亿的了
—————找 A中不存在B 的区间 ——结果如下：—————————————————---
[1,1]
[32,34]
[51,53]
[71,72]
[101,121]
注：如果 几十亿一个个枚举的话 cpu 和内存 不够！
A B 区间 各有 几十万，区间数量不一定相等！
所以只能求高效算法
区间? 覆盖 不相交 大数据
[解决办法]
既然排好序了从小到大比较不就得了，O（N）的复杂度还不够？
[解决办法]
这个跟n的大小没关系啊，复杂度只跟区间个数有关
[解决办法]
如果数据量很大的话，不可能一次读到内存中。
可以一次读取一部分数据，而且区间是排好序，然后一个个计算A和B的区间不就可以了吗。
[解决办法]
读一行，判断一行的，不需要全部读进来。
[解决办法]
数据放在A.txt和B.txt
结果写入C.txt
#include <iostream>
#include <fstream>
using std::pair;
using std::ifstream;
using std::ofstream;
typedef pair<unsigned int, unsigned int> Upair;
inline unsigned Min(unsigned int x, unsigned int y) {return x < y ? x : y;}
inline unsigned Max(unsigned int x, unsigned int y) {return x > y ? x : y;}
ifstream& getpairfromfile(ifstream& ifs, Upair& inoutpair);
Upair left(Upair& uall, const Upair& ua);
int main()
{
ifstream inA("A.txt");
ifstream inB("B.txt");
ofstream outC("C.txt");
Upair upa, upb(0, 0), upc, upall(1, -1);
//设置b(0,0)是为了第一次去读b
//c是当前处理的区间
//all是整个正整数区间
while (inB)
{
if (inA) //A文件没读完，要分区，否则直接把剩余的区间作为当前区间
{
getpairfromfile(inA, upa);
upc = left(upall, upa);
}
else
upc = upall;
while (inB && upc.second >= upb.second && upc.first <= upc.second)
//当前区间还有空间而且右边界比B区间大，否则去读A文件继续划分区间
{
while(inB && upc.first > upb.second) //B区间在当前区间的左边
{
getpairfromfile(inB, upb); //读取B区间
}
if (!inB)
break;
//计算当前区间和B区间重复的部分，并写入c文件
unsigned int low, high;
low = Max(upc.first, upb.first);
high = Min(upc.second, upb.second);
outC << '[' << low << ',' << high << ']' << std::endl;
upc.first = high + 1; //当前区间左边界重新计算
}
}
inA.close();
inB.close();
outC.close();
printf("done.\n");
return 0;
}
ifstream& getpairfromfile(ifstream& ifs, Upair& inoutpair)
{
//读文件一行，取得区间
char buff[128];
ifs.getline(buff, 128);
sscanf(buff, "[%u,%u]", &inoutpair.first, &inoutpair.second);
return ifs;
}
Upair left(Upair& uall, const Upair& ua)
{
//把整个区间根据A的区间分成2部分
Upair ret;
ret.first = uall.first;
ret.second = ua.first - 1;
uall.first = ua.second + 1;
return ret;
}
[2,10]
[11,30]
[35,48]
[49,50]
[54,70]
[73,100]
[1,8]
[10,20]
[21,30]
[32,48]
[49,50]
[51,66]
[69,121]
[1,1]
[32,34]
[51,53]
[71,72]
[101,121]
