文章目录
  1. 1. 找中位数
    1. 1.1. 常规情况
      1. 1.1.1. 复杂度推导
    2. 1.2. 面试问题
  2. 2. 找众数
    1. 2.1. 易得做法
    2. 2.2. 改良
    3. 2.3. 网传版本
    4. 2.4. top K问题
  3. 3. 广义的众数问题
  4. 4. 参考文献

引言:内存不足引起的若干面试问题。


找中位数

常规情况

如何O(n)找中位数?

思考快排算法,我们可以在O(n)复杂度内,得到任意元素在数组中的位置。

那么任取一个数,我们可以得到有a个数大于它,有b个数小于它,如果恰好a=b,则找到中位数就是该数。

如果有a<b,则筛去所有大于等于该数的数,中位数必定位于剩下的数中,并且记录筛去了sa+=a+1个数。

如果有a>b,则筛去所有小于等于该数的数,中位数必定位于剩下的数中,并且记录筛去了sb+=b+1个数。

在剩余的b个数中,再任取一个数,可以得到有a个数大于它,有b个数小于它,如果恰好a+sa=b+sb,则找到中位数就是该数。

复杂度推导

而每次问题规模缩小一半,每次递归需要消耗O(n)时间,因此套用公式:

T(n)={O(1),n=1aT(n/b)+O(nk),n>1T(n)= \begin {cases} O(1),&n=1\\ aT(n/b)+O(n^k),&n>1 \end {cases}

推得:

T(N)={O(Nlogba),a>bkO(NklogbN)=O(NklogN),a=bkO(Nk),a<bkT(N)=\begin {cases} O(N^{log_ba}),&a>b^k\\ O(N^klog_bN)=O(N^klogN),&a=b^k\\ O(N^k),&a<b^k \end {cases}

其中a=1,b=2,k=1,得T(n)=O(n)。

面试问题

如果有10G个32bit的数乱序存放在文件中,内存是2G,请问怎么找出它们的中位数?

如果有40GB的文件,乱序存放32bit的数,内存是2G,请问怎么找出它们的中位数?

经典题。

假设32bit的数都是无符号整数。

首先可以想到,能不能在内存中记录这10G个数的出现次数。

出现次数肯定是小于10G的,那么可以用一个long long即64位(Bit),8个字节来表示。

那么2GB=231Byte2GB=2^{31}Byte内存最多可以开2282^{28}长度的,每个元素占232^3字节的数组记为cntcnt,每个数组元素都可以表示出现次数。

可是我们一个整数的数据范围是2322^{32}的,只能把它分段了,段大小是232/228=24=162^{32}/2^{28}=2^4=16

也就是说,扫一遍这10G个数,记该无符号整数为V,则令cnt[V/16]++cnt[V/16]++

再扫一遍arr数组,统计前缀和,直到sum[i]<5Gsum[i]<5Gsum[i]+cnt[i+1]>=5Gsum[i]+cnt[i+1]>=5G,就可确信中位数在区间[(i+1)16,(i+1)16+15][(i+1)*16,(i+1)*16+15]中了。

再扫一遍10G个数,对数值位于该区间的数,开长度为16的long long数组,每个数都记录它出现的次数。

我们可知小于该区间的数有多少个,大于该区间的数有多少个,很方便即可统计得中位数。

提问,按照这种算法找中位数,文件大小的上限是多少?假设一个数仍然是32bit,内存仍是2GB。

可以看出这种算法最重要的思路是缩减数据量,当我们将一个数分段后,问题规模就被缩小了。

也就是说,即使我们分成两段,我们也可以知道中位数是位于cnt值更大的那个区间里的,然后递归求解。

也就是说,2GB内存可以化作21230B2^1*2^{30}B,可以使用大数算法维护一个数组元素为8230=2338*2^{30}=2^{33}位的2个长度的数组。

也就是说,文件中整数的个数最多可达22332^{2^{33}}个,那么文件大小可达4B22334B*2^{2^{33}}

找众数

如果有10G个32bit的数乱序存放在文件中,内存是2GB,请问怎么找出它们的众数?

易得做法

10G的次数是大于2332^{33}的,32位的unsigned存不下,可以用64位long long存放。

那么2GB=231B=234bit=22864bit2GB=2^{31}B=2^{34}bit=2^{28}*64bit,可以开数组长度为2282^{28}即256M长度的long long数组。

32bit的长度为232=4G2^{32}=4G,我们将4G的数据范围分为k=232/228=24=16k=2^{32}/2^{28}=2^4=16段。如果分段找众数,需要扫描16次原始数组,每次只统计在当前段的数的出现次数。每次统计需要O(m)扫描这个数组。

T(n)=16(n+m)=O(n+m)T(n)=16(n+m)=O(n+m),其中m=228m=2^{28},题意中n=10Gn=10G

改良

在扫一遍的时,按数所在的区间将数push_back到16个不同的子文件中,在每个子文件分别统计众数,最终取各众数中最大的数作为最终的众数。

如何统计每个文件里的众数?

由于每个子文件的数的数据范围不超过228=256M2^{28}=256M,因此如法炮制开一个256M长度的long long数组,用桶的方法找众数,每次统计的复杂度O(m)O(m)m=228m=2^{28}

T(n)=2n+16m=O(n+m)T(n)=2n+16m=O(n+m),题意中n=10Gn=10G

网传版本

https://blog.csdn.net/qq_31617121/article/details/79935801

【题目】有一个包含20个全是32位整数的大文件,在其中找到出现次数最多的数。
如果用HashMap,key是int型,value也是int型
2*20 * 10^8 * 4B = 16GB内存
将20亿个整数用哈希函数分成16个小文件,根据哈希函数的性质,同一种数不可能被哈希到不同的小文件,假设哈希函数足够好,每个小文件的内存不会超过1GB。

然后统计每个小文件每种数出现的次数,得到16个小文件中各自出现次数最多的数,只要从16个数中选出最大的出现次数的数。

如果用hash函数,将避免所有的数集中在一个文件里。

但是如果我所有的数都集中在了一个区间中,我可以直接进行众数统计,耗时T(n)=2n+mT(n)=2n+m,反而更快。

所以为什么要用hash呢?

于是我找到了原始版本

https://cloud.tencent.com/developer/article/1442848

可以看到在现场时小秋的表现还是比较慌乱,没办法考虑到所有情况的,而面试官显然也没办法洞察到所有问题。

80亿是多大呢?

大概是2332^{33},显然80亿个整数,这个出现次数可以用long long轻松表示下,毕竟long long是64位,可以表示[263,2631][-2^{63},2^{63}-1]的范围呢。

别说80亿了,1亿亿(2532^{53})都可以支持呢。

如果用hash_map去统计,根据鸽巢原理,如果数据都集中在1~20000000,那么最多有20000000个不同的数,占用160000000B即152MB的内存,完全可以统计下。

top K问题

如果有10G个32bit的数乱序存放在文件中,内存是2GB,请问怎么找出它们最大的K个数?

维护一个长度为k的优先队列即可。

广义的众数问题

1,海量日志数据,提取出某日访问百度次数最多的那个IP。

这个问题还可以把IP给整数化,如13.129.3.42可整数化为13129003042,然后用上述法子做。

2,有一个1GB大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1MB。返回频数最高的100个词。

这个问题没办法对数据范围整数化,这里就得使用广义的众数问题的做法:哈希化。

将每一个词x取hash(x)%2048,根据不同的值分到2048个文件中去,每个文件小于0.5MB或偶尔大于0.5MB,对于大于0.5MB的文件,将其内的词再次用另一个哈希函数hash2(x)%5,再细分为5个文件,直到小于0.5MB。

模的这个值取决于你想使文件大小低于多少,文件大小一般取决于读入内存后会使得hash_map占用多少。

比如说假如0.5MB的文件每个词都不同,hash_map的key占用4B,value占用4B,那么假设词的平均长度为4Byte,则刚好可填满1MB的内存。

这样hash化之后,相同的词必定在同一个文件中,但一个文件里也可能包含多个不同的词,这个无所谓。hash化的目的是让相同的词归类到同一个文件中去。

然后针对每一个文件,使用hash_map统计其个数,这个问题是TOP K问题,所以再用一个优先队列维护频率最大的100个词。

3,有10个文件,每个文件1GB,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。你有一台2GB内存的电脑,要求你按照query的频度排序。

现在有10个文件,我们先得把不同文件里的相同的query集中在一起,再挨个统计,因此想到hash化。

同样hash(x)%10得到10个近1GB的文件,这时相同的query已经集中在一起了。

如果有大于1GB的文件,可以再hash下去,见问题2。

然后用hash_map对每个文件的query进行统计,然后内部进行去重再排序,最后再归并排序。

4,如果有10G个32bit的数乱序存放在文件中,内存是2GB,请问怎么找出它们的众数?

一共40GB的文件,那么hash(x)%70分到70个文件中去,对每个超过0.6GB的文件采用另一个hash函数hash化直至收敛(收敛是指无论使用什么样的hash函数均无法再细分,基本上说明得到的数已经纯了)。

一般准备2个hash函数就够了,不收敛也快收敛了。

此时如果存在超过0.6GB的文件也无所谓,因为此时一个文件里必定包含众多的重复数,不重复的数的个数已经无法使得它们塞满内存了,已经可以用hash_map存储并统计个数了。

为什么要分成0.6GB呢,因为hash_map的key和value分别占4B和8B,共3倍的32bit。

参考文献

  1. 教你如何迅速秒杀掉99%的海量数据处理面试题
  2. 左神算法 只用2GB内存在20亿个整数中找到出现次数最多的数
  3. 如何只用2GB内存从20/40/80亿个整数中找到出现次数最多的数
文章目录
  1. 1. 找中位数
    1. 1.1. 常规情况
      1. 1.1.1. 复杂度推导
    2. 1.2. 面试问题
  2. 2. 找众数
    1. 2.1. 易得做法
    2. 2.2. 改良
    3. 2.3. 网传版本
    4. 2.4. top K问题
  3. 3. 广义的众数问题
  4. 4. 参考文献