海量数据的“交并集”操作
应用场景大致是这样：
有上亿条数据，每条数据属于若干个类别（大约属于3到10个类别），
总共约有近千个不同的类别，每个类别含有的数据量从几千到上亿不等。
现在需要迅速的查询出某几个类别，经过交、并操作后的数据量。
现在的处理方式是：
对原始的上亿条数据，随机抽样出千分之一的数据量；
对这抽样的数据，分别赋上从1开始的序号；
然后，对这抽样的数据中的每个类别分别建立一个bitmap，
bitmap的每个下标，对应着某一条抽样数据，
若置一，则表示该类别含有该下标所对应的数据。
当有交并集查询到来时，取出相应类别的bitmap，进行交并操作，
并得到结果bitmap的置一数量，然后再除以抽样率，得到近似的原始数据的交并集的数据量。
现在，希望能够尽可能精确的得到原始数据的交并集数据量，
请问大家有没有什么更好的方案啊？
比如说，是否可以建立多级的bitmap，或者分段的bitmap等（自己瞎捉摸着）。
望大家不吝赐教，
来者有分啊！
[解决办法]
观望！！！！！！ 这么大的数据量暂时没处理过。。。。。
[解决办法]
这个数据量是什么？只是count么？
[解决办法]
求交集用小集合做HASH，求并集用bitmap，复杂度不可能低于O(n)吧
[解决办法]
不知redis数据库是否可以用上，天然的对集合操作的支持，而且性能很好。
[解决办法]
每条数据属于若干个类别, 用一个int字段("Type")来表示这个
如果只属于第一个类别用 1,
第2个类别 2
同时属于两个类别 3
最后数据按这个 Type做索引, 以后的检索就很快了
[解决办法]
[解决办法]
文章 和 标签？
关系数据库 采用 分区表，应该能解决
[解决办法]
有统计数据吗？(2-10)个类别的数据比重大概是多少？其实我想知道是不是绝大部分的数据只有2~3个类别？
[解决办法]
估计没什么好办法，你看google的查询结果数量都不给准确值，结果数量过多的时候连综合权值的计算的抛弃了，归并的开销太大。
[解决办法]
有一个不怎么好的想法(仅仅是个常数级的处理)，将分类数据按照数量排序形成C个等级，然后将每个分类数据按照最小关联等级分成C分，归并的时候就只需要处理有关联的等级数据。
[解决办法]
看贴总是不回 ，一直没提升等级和增加经验，现在我明白了，反正回贴可以升级 ，也可以赚经验，而升级又需要经验 ，我就把这句话复制下来，遇贴就灌水，捞经验就闪
[解决办法]
- C/C++ code
//输出PROG中有但LIST中没有的文本行，即集合PROG-LIST#include <stdio.h>#include <string.h>#include <stdlib.h>#include <search.h>#define MAXLINES 1000000#define MAXCHARS 256char buf[MAXLINES][MAXCHARS];char P[256]="PROG";//程序Program需要的文件列表char L[256]="LIST";//dir /b /s生成的实际文件列表ListFILE *fp,*fl;int c,n,L1,hh;int ignore_case=0;char ln[MAXCHARS];int icompare(const void *arg1,const void *arg2) { return stricmp((char *)arg1,(char *)arg2);}int compare(const void *arg1,const void *arg2) { return strcmp((char *)arg1,(char *)arg2);}int main(int argc,char **argv) { if (argc>1) strcpy(P,argv[1]);//命令行参数1覆盖PROG if (argc>2) strcpy(L,argv[2]);//命令行参数2覆盖LIST if (argc>3) ignore_case=1;//若存在命令行参数3，忽略大小写 if ((fl=fopen(L,"rt"))==NULL) { fprintf(stderr,"Can not open %s\n",L); fprintf(stderr,"Usage: %s [PROG] [LIST] [-i]\n",argv[0]); return 1; } if ((fp=fopen(P,"rt"))==NULL) { fclose(fl); fprintf(stderr,"Can not open %s\n",P); return 2; } n=0; hh=0; while (1) { if (fgets(ln,MAXCHARS,fl)==NULL) break;// hh++; L1=strlen(ln)-1; if ('\n'!=ln[L1]) {//超长行忽略后面内容 fprintf(stderr,"%s Line %d too long(>%d),spilth ignored.\n",L,hh,MAXCHARS); while (1) { c=fgetc(fl); if ('\n'==c || EOF==c) break;// } } while (1) {//去掉行尾的'\n'和空格 if ('\n'==ln[L1] || ' '==ln[L1]) { ln[L1]=0; L1--; if (L1<0) break;// } else break;// } if (L1>=0) { strcpy(buf[n],ln); n++; if (n>=MAXLINES) { fclose(fl); fclose(fp); fprintf(stderr,"%s up to %d lines",L,MAXLINES); return 3; } } } fclose(fl); if (ignore_case) qsort(buf,n,MAXCHARS,icompare); else qsort(buf,n,MAXCHARS,compare); hh=0; while (1) { if (fgets(ln,MAXCHARS,fp)==NULL) break;// hh++; L1=strlen(ln)-1; if ('\n'!=ln[L1]) {//超长行忽略后面内容 fprintf(stderr,"%s Line %d too long(>%d),spilth ignored.\n",P,hh,MAXCHARS); while (1) { c=fgetc(fp); if ('\n'==c || EOF==c) break;// } } while (1) {//去掉行尾的'\n'和空格 if ('\n'==ln[L1] || ' '==ln[L1]) { ln[L1]=0; L1--; if (L1<0) break;// } else break;// } if (L1>=0) { if (ignore_case) { if (NULL==bsearch(ln,buf,n,MAXCHARS,icompare)) printf("%s\n",ln); } else { if (NULL==bsearch(ln,buf,n,MAXCHARS,compare)) printf("%s\n",ln); } } } fclose(fp); return 0;}
[解决办法]
- C/C++ code
#include <stdio.h>#include <stdlib.h>#include <time.h>int d[6];int i,n,a,b,t;int c,j;void main() { srand(time(NULL)); printf("shuffle 0..n-1 demo\n"); for (n=1;n<=5;n++) {/* 测试1～5个元素 */ printf("_____n=%d_____\n",n); j=1; for (c=1;c<=n;c++) j=j*c;/* j为n! */ j*=n*2; for (c=1;c<=j;c++) {/* 测试n*2*n!次 */ for (i=0;i<n;i++) d[i]=i;/* 填写0～n-1 */ for (i=n;i>0;i--) {/* 打乱0～n-1 */ a=i-1;b=rand()%i; if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;} } printf("%04d:",c); for (i=0;i<n;i++) printf("%d",d[i]); printf("\n"); } } printf("shuffle 1..n demo\n"); for (n=1;n<=5;n++) {/* 测试1～5个元素 */ printf("_____n=%d_____\n",n); j=1; for (c=1;c<=n;c++) j=j*c;/* j为n! */ j*=n*2; for (c=1;c<=j;c++) {/* 测试n*2*n!次 */ for (i=1;i<=n;i++) d[i]=i;/* 填写1～n */ for (i=n;i>1;i--) {/* 打乱1～n */ a=i;b=rand()%i+1; if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;} } printf("%04d:",c); for (i=1;i<=n;i++) printf("%d",d[i]); printf("\n"); } }}
[解决办法]
哇哦 这么专业 可惜研究方向不同 帮不上什么吖
[解决办法]
没处理过这么大的数据
[解决办法]
[解决办法]
[解决办法]
楼主，不知道你是在什么平台上开发，对于性能要求到底有多高？究竟是内存不够，还是硬盘不够，抑或运算时间不够？
照理来说10亿也不是一个很大的数值呀，10亿位的bitmap内存占用不到60M。
预处理的时候创建1000个种类的bitmap，硬盘占用也就60G。
[解决办法]
文章 和 标签？
[解决办法]
js代码js代码
[解决办法]
看贴总是不回 ，一直没提升等级和增加经验，现在我明白了，反正回贴可以升级 ，也可以赚经验，而升级又需要经验 ，我就把这句话复制下来，遇贴就灌水，捞经验就闪
[解决办法]
只是数量，不需要交并之后的具体元素。
花时间穷举，把所有的可能的交并结果都记下来吧。
假设有10个类，有2^10个可能的交并结果，很小的。
如果需要，可以增量式的更新这个结果，在每次增删改数据的时候。
[解决办法]
不敢说。。什么是海量？定义范围？
[解决办法]
战神的代码是在刷分，以前用过的。。。
[解决办法]
支持39楼。
[解决办法]
1,分段
2,哈希
复杂度做到加法O(A+B)
[解决办法]
同意楼上
[解决办法]
知道啦 谢谢
[解决办法]
做足排序、筛选后再说别的先
[解决办法]
建议楼主不妨参考一下点积拓扑的处理方式~