讨论/技术交流/求助丨海量数据处理/
求助丨海量数据处理

1.几亿个ip,求出现次数最多的k个ip,内存限制1G
2.同样是几亿个ip,每个ip都有一个地址对应(城市),给出一个ip如何快速查找这个ip所在的城市
3.几亿个qq号查一个qq号是否存在
解答:
1.hash取模,哈希表统计,堆排序统计topk
2.建立树,左子树0,右子树1,层数32,查找效率常数级,叶子节点储存value
3.位图,内存空间如果有要求,把数字分区然后建立位图

2
共 8 个回复

假如二分后
s1:1,1,1,2,2
s2:2,2,3,3,3

s1筛选出来的数字是1,频率是3;s2筛选出来的数字是3,频率是3;但其实真正的数字是2,频率是4

这样不是有问题了吗?

2
  1. 任意IPv4地址可以使用32 bit表示出来,几亿个ip相当于几亿个无符号32bit整数
  2. 4GB = 4294967296BB,即42亿+字节,则1GB相当于10.5亿+字节
  3. 估算1GB内存空间可以存下几亿个数字,若用哈希表直接计数,空间却可能不够,因此,可将输入二分或者四分
  4. 设原输入数据为S={si}S = \{s_i\},二分时,i=1,2i = 1, 2;四分时i=1,2,3,4i = 1, 2, 3, 4sis_iSS的任意真子集
  5. 对于sis_i,使用1GB空间,用哈希表计数,得到sis_i中出现频率最高的数字NiN_i及其出现频率FiF_i
  6. argmaxNiFi\mathop{\arg\max}_{N_i} {F_i},其中i=1,2 or1,2,3,4i=1,2\ or 1, 2, 3, 4
1

考虑下 哈希,分治,分布式处理

1

哈哈,你说的对,所以分治前得先过一遍哈希

他的意思应该是用取余的方法等分,这样每个相同的数据会被分到一起,因为数据量足够大,可以认为是等分

这个实在是太难了

脑洞再大点,还可以构建一个树模型。再扩展一下,就是最近邻检索(ann),一堆算法干上去

第一题当时回答ip转成unsigned int然后取余1000储存到不同的文件,每个文件单独排序取最大然后堆排序(topk)
第二个问题我是真的没想到有什么好的解决办法想要问问大家
第三个位图