目录
1、10亿个整数里面求最大的100个
2、求大文件交集
3、查找出现次数前210的ip地址
1、10亿个整数里面求最大的100个
经典的tok问题,可以使用堆来解决
2、求大文件交集
给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?
这里的query是查询,理解为字符串即可,所以不能使用位图
分析:假设平均每个query字符串50byte,100亿个query就是5000亿byte,约等于500G(1G 约等于 10亿多Byte)
哈希表/红⿊树等数据结构肯定是⽆能为⼒的
法一:使用布隆过滤器,⼀个⽂件中的query放进布隆过滤器,另⼀个⽂件依次查找,在的就是交集。此时在交集中的query一定能被找到,但找出来的并不一定是交集,因为存在误判
法二:使用哈希切分。
⾸先内存的访问速度远⼤于硬盘,⼤⽂件放到内存搞不定,那么我们可以考虑切分为小文件,再放进内存处理
因为这一个大文件的大小大约是500G,所以可以将一个大文件切分成1000个小文件,这样就可以让小文件一个是500MB。将大文件A平均切分成A1,...,A999这1000个文件,大文件B平均切分成B1,...,B999这1000个文件,此时再将A1与大文件B切分出来的1000个文件比较,如何A2,...,A999一样,时间复杂度是O(N^2),时间复杂度太高了
此时可以使用哈希切分。
先将大文件A和B里面的query映射为整数,根据映射的值放进小文件中,每次只比较一组Ai和Bi,相同的就是交集。时间复杂度是O(N)。
此时会有一个问题,就是现在并不是平均切分,所以每个小文件的大小是不确定的,如果有某一组小文件Ai和Bi之和的大小大于1G了,要如何处理呢?此时就需要就行二次切分,将过大的这一组Ai和Bi重新映射到新的小文件中。此时可以解决大部分情况,但是假如Ai有5G,其中有4G都是同一个query,这样二次切分是解决不了的,所以我们不能用Ai和Bi之和的大小来判断是否需要二次切分,因为这里面太大可能是因为重复的query造成的,而找交集并不需要重复元素,并且哈希表和红黑树都是不允许数据冗余的。所以,我们不管Ai和Bi的和是多大,直接将其往哈希表或者红黑树中放,当哈希表或者红黑树的大小大于1G了,此时再进行二次切分,因为此时一定不是由于重复的query造成的内存太大
3、查找出现次数前10的ip地址
给⼀个超过100G⼤⼩的log file, log中存着ip地址, 设计算法找到出现次数最多的ip地址?查找出现次数前10的ip地址
本题的思路跟上题完全类似,依次读取⽂件A中ip,i = HashFunc(ip)%500,ip放进Ai号⼩⽂件(这样小文件中的就是相同的ip或冲突的ip),然后依次⽤map<string, int>对每个Ai⼩⽂件统计ip次数,同时求出现次数最多的ip或者topk ip。本质是相同的ip在哈希切分过程中,⼀定进⼊的同⼀个⼩⽂件Ai,不可能出现同⼀个ip进⼊Ai和Aj的情况,所以对Ai进⾏统计次数就是准确的ip次数
注意:这里是模500,不是一定要像上一题一样模1000,上一题是为了让一个小文件大概是500MB