作者:林冠宏 / 指尖下的幽灵
GitHub : https://github.com/af913337456/
腾讯云专栏: https://cloud.tencent.com/developer/user/1148436/activities
仅列举一些解决方法,事实的解决方案是非常多的。
这些问题都是面临着有如下的考虑:
- 内存不足以放下所有的数。
- 机器CPU的核数不够。
- ...
问这些问题的意义:
如果能把这些问题答好,必然是综合计算机各方面的知识,从内存到数据结构甚至还涉及到硬件,方法面面。至此,我给它定位是,综合考量一个程序员计算机基础能力的面试题。
一,找出不重复的
在2.5亿
个正整数
中找出不重复的整数。
思路一:
分治法 + HashMap
(HashMap 不要局限在 Java 语言)
将 2.5 亿个整数,分批操作,例如分成 250 万一批,共100批次。每批使用循环遍历一次,存入 HashMap<int1,int2>
里面,int1
对应这个数,int2
对应它出现的次数,没出现就默认是 1 次。每操作完一批,就进行当前的 HashMap
的去重操作
,读出 int2 > 1
的,排除掉。接下来的批次,以此类推,得出 100,剩下的自然就是不重复的。
好了,我们现在来计算下上面这个方案的双间复杂度,时间
& 空间
时间复杂度
:250W * 100轮 + 其它批次
。对于多核机器,可以启动线程操作。
空间复杂度
:使用 int 来进行存每一个数,保证不溢出情况下,那么就是 --> Key + Value : (250W * 4字节,4Byte)/(1024*1024) ~ (Key + 9.5MB)
内存。
思路二:
位图法 Bitmap
(一个 bit 仅会是 0 或 1)
对于此题,我们可以设计每两个 bit
位,标示一个数的出现情况。00
表示没有出现,01
表示出现一次,10
表示出现多次。2.5 亿个正整数,首先我们要知道是正整数
,我们就不需要考虑负数,也就是无符号,无符号的整形占四个字节
。
我们以这个为例子,开始计算位图
内存。
1B = 8b,4B = 32b,它可以表示的最大
的整数是 2^32-1(不溢出)
,也就是说,我们需要 2^32-1 ~ 2^32
个位
来表示这2.5
亿个数。我们上面说了,每个状态
是两个位
,那么总共就是2^32*2
个位。
那么我们可以一次申请的 位图 内存是:2^32*2 bit ,(2^32*2)/(1024*1024*8) = 1GB
即可。当然,我们也可以加上分治
的思路,分批处理,不用直接用 1G,哈哈。
那么这样做的情况下怎样找到这个数呢?我举个例子,例如我们此时读入一个数是:64
,64
对应的所在bit
位是:64*2=128
,也就是说第 127
和 128
位共同标示了它的出现状态
。其他的以此类推。每当我们读出一个数,我们就这样去找到它对应的bit位
,先读出bit位
的值,再做记录,已经是01
的,再次来到,那么就应该修改为10
。最后的我们这样得出结果:扫描整个位图,如果是10
的,就下标/2
得出这个数。
二,找出出现次数最多的
第一题:找出一篇文章中,出现次数最多的单词。
第二题:10亿个正整数
找出重复次数最多的100个整数。
思路一:
分治法 + HashMap
没错,分治法 + HashMap
这个方法就是可以用来处理很多 Top K
问题的。
对于问题一
,其实比较简单,这道题也是我 2016 年腾讯第三轮技术面要求当场写代码的题目
。我们可以先判断,这篇文章可能很长,也可能很短,那么我们应该规定一个字数的标志
,作为一批的字数限制,例如100
个文字。每100
个文字是一批的处理极限,我们先读出100
个,100以内的就直接全部读出。读出后,打散成字符串,例如英语文章它以空格和一些符号分割。使用split
方法就可以打散。此时我们得出一个字符串数组String[] array
,有了这个之后就可以参考 找出不重复
问题的解法。每批使用循环遍历一次,存入 HashMap<String,Integer>
里面,string
对应这个数的字符串,Integer
对应它出现的次数,最后最大的自然就是出现次数最多的。下面直接给出个 Demo 函数
。
// LinGuanHong
public static void search(String limitText){
String maxWord = "";
int maxTime = 0;
String[] words = limitText.split(" |\\.|,");
int length = words.length;
HashMap<String,Integer> one = new HashMap<>();
for(int j=0;j<length;j++){
Integer number = one.get(words[j]);
if(number != null){
number = number + 1;
/** 找到次数加 1 */
one.put(words[j],number);
if(maxTime < number){
maxTime = number;
maxWord = words[j];
}
}else{
/** 没找到,赋值 1 */
one.put(words[j],1);
}
}
System.out.println("maxTime is :"+maxTime+" ; maxWord is :"+maxWord);
}
第二题对应的 分治法 + HashMap
按照前面的案例,我们首先一样是要把这十亿
个数分成很多份。例如 1000份
,每份 10万
。然后使用 HashMap<int,int>
来统计。在每一次的统计中,我们可以找出最大的100个数
,为什么只找10万
中的100个啊?因为我们有1000份
,其它份里面的第二大可能是这份里最小的。这样全部加起来都100*1000个
数了。OK,在我们找出这100*1000
个侯选数后,继续分治处理,或者直接进行排序,如果直接排序就是10W个数
。排序算法可以选快排
等之类的,前100个
就是结果。
思路二:
位图法 Bitmap
第一题,略。不是纯数字的,不建议采用位图法
。
第二题:
有了 找出不重复的
的例子做基础。我们此时直接知道这题的 正整数
最大也是只能到 2^32-1
,对于这道题,我们不需要乘2
,所以我们申请的内存大小也是512MB
。这样我们就能使用这个位图
把所有数都存进去。如果出现了一次,该bit位 = 1
,没有就是0。多次出现的话,我们就不能累加到bit位
里面了,因为它最大就是1
。这时候我们会发现,出现多次的话,是无法通过bit位
进行累加记录的。所以,此题也是不适合采用位图法
。
实际操作(参考网上)
实际上,最优的解决方案应该是最符合实际设计需求的方案,在时间应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。
下面针对不容的应用场景,分析了适合相应应用场景的解决方案。
-
单机+单核+足够大内存
如果需要查找10亿个查询次(每个占8B)中出现频率最高的10个,考虑到每个查询词占8B,则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存,直接在内存中对查询次进行排序,顺序遍历找出10个出现频率最大的即可。这种方法简单快速,使用。然后,也可以先用HashMap求出每个词出现的频率,然后求出频率最大的10个词。
-
单机+多核+足够大内存
这时可以直接在内存总使用Hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑同(1)类似,最后一个线程将结果归并。 该方法存在一个瓶颈会明显影响效率,即数据倾斜。每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程。而针对此问题,解决的方法是,将数据划分成c×n个partition(c>1),每个线程处理完当前partition后主动取下一个partition继续处理,知道所有数据处理完毕,最后由一个线程进行归并。
-
单机+单核+受限内存
这种情况下,需要将原数据文件切割成一个一个小文件,如次啊用hash(x)%M,将原文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用Hash的方法对数据文件进行分割,知道每个小文件小于内存大小,这样每个文件可放到内存中处理。采用(1)的方法依次处理每个小文件。
-
多机+受限内存
这种情况,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用(3)中的策略解决本地的数据。可采用hash+socket方法进行数据分发。
其他的
例如问:XXXXX中找出最大的一个,最小的一个,最大的几个,最小的几个
。这类的就可以使用分治法+最小堆/最大堆
秒之。