@Catyee
2021-08-26T09:32:39.000000Z
字数 4053
阅读 1116
面试
先有一个基本印象：
有了基础印象之后，就知道其实一亿条数据是可以直接放入到内存中用快排、堆排序、归并排序的方法进行排序的（现在内存一般都超过了400M），但是要注意如果使用递归实现的快排，由于数据量过大有可能出现递归次数超过了栈深度而抛异常（没有详细计算过，但是有这种可能性）
如果没有重复数据，或者排序之后去除重复数据，还可以用位图的方式来实现。
但如果在有重复数据的情况下，依然用位图的思路的话，就需要在每一位记录重复的次数，实际上就已经不是位图了，之所以用位图，是因为位图只用一个bit来记录数据有或者无，空间占用非常小，如果另外增加记录的信息，就不能使用bit了，因为记录其它信息必然会增加空间的消耗，可能内存根本就放不下。比如说有10亿数据，都不重复，只需要10亿个bit，大概238M，但是如果要记录重复次数，至少每个位置需要一个int类型，那不就是退化成了10亿的int数组了？
如果现在有一百亿、一千亿的数据，再放入内存就不太现实，只能采用MapReduce的思路来进行，先将大文件切分成小文件，对每个小文件的数字进行排序，然后对所有文件整体进行归并排序。大致思路就是这样，因为最终是要全排序，切分小文件的时候能尽量做到小文件之间也有序就更好了，这样直接就省去了reduce的过程。思路确定了怎么操作呢？一般切分文件都会想到取模，但如果有大量重复数据，用取模运算的话，同一个数据会路由到同一个文件，可能导致这一个文件太大，也就是常说的数据倾斜的情况，从而影响整体效率；就算没有重复数据，也并不能做到小文件整体有序，综合来看，取模并不是一个很好的方式。其实最好的方式还是分桶，但是分桶需要知道最小值和最大值(明确范围，然后才能分桶，分桶可能造成数据不均匀)，比如现在有100亿int类型数据，文件大概37G, 这里面有大量重复数据，假如我们一台机器预留了计算用的内存之后能够处理大概400M的数据，也就是说如果每个桶一个文件，这个文件最大只能400M，这样至少要划分是100个桶，int的最大值小于22亿，就按25亿算，假如1亿为分界线，可以划分为25个桶，如果2500万为界限，就可以划分为100个桶，然后将数据全部入桶。理想情况下，每个桶数据均匀，都只产生了一个文件，都没超过400M的极限，那就好办了，先每个桶内部排序，排完序也就整体有序了。
但是这只是理想情况，仍然有可能某个桶的数据过多，超过400M，这个时候就要再写另外一个文件，也就是说某个桶可能会有多个文件，那这个桶内部的排序会稍微复杂一点，可以用同样的方式进一步分桶，但是这样会增加io的次数。
如果采用分桶的方式，每个桶内的数据都能够直接放进内存，在内存中用快排或者堆排进行全排序，全排序结束桶间也有序，这样效果是最好的。
如果不是分桶的方式，那每个切片排序只能做到局部有序，不能做到整体有序，所以还要对每个切片做归并排序，才能达到整体有序。
TopK有好几种情况，主要有
依然是MapReduce思路，依然最好是分桶。最大的k个数肯定在最后一个桶，寻找方式有两种，一种是用最小堆，即用一个k个元素的最小堆去在最后一个桶中找最大的k个数，先放k个数建堆，堆定为堆中最小的数，遍历其余数字，如果比堆顶数大就入堆，最终堆中的数就是最大的k个数，这种时间复杂度是O(nlogn)。
另一种是用快排的思路，比如在100万个数据里面查找最大的10000个数据，先用快速排序的方法将数据分为2部分，如果大的那堆数的个数大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数还大于10000个，就接着递归，直到大的那堆数的个数小于10000个，如果个数是n，然后就去小的那堆数里面快速排序，递归找第10000-n大的数字；通过以上过程，就可以找到最大的一万个数。这种方式时间复杂度是O(n)。
如果不能分桶，则通过hash切分文件，切分成小文件之后，每个小文件内通过小根堆或者快排找到最大的k个数，然后再将每个文件中的最大k个数一起放入内存，通过小根堆和快排找到最终的最大k个数。
比如身份证号，ip地址，电话号码、热门商品名、热门搜索信息等等，其实都是海量数据统计词频的问题。这种统计词频的问题就不用分桶了，因为不需要比较目标数据本身的大小，而是按出现次数排序，所以第一步是统计出词频，然后再通过词频找出重复度最高的k个词。这种问题最关键在于把重复的数据放入到同一个文件，所以hash算法是关键。
比如数十G文件中统计前100个重复次数最多的ip地址：
把重复出现的IP都放到一个文件里面，一共分成100份，这可以通过IP对100取模得到，具体方法如把IP中的点转化为整型long型变量，这样取模为0,1,2...99的IP都分到一个文件了，但是要考虑一个问题，如果某个文件的IP取余之后还是特别多无法放入内存中，可以再对这一类IP做一次取模，直到每个小文件足够载入内存为止。这个分类很关键，如果是随便分成100份，相同的IP被分在了不同的文件中，接下来再对每个文件统计次数并做归并，这个思路就没有意义了，起不到“大而化小，各个击破，缩小规模，逐个解决”的效果了。
接下来把每个小文件载入内存，建立哈希表将每个IP作为关键字映射为出现次数，这个哈希表建好之后也得先写入硬盘，因为内存就那么多，一共要统计100个文件。（这里就涉及到优化点了：统计词频最好的方式不是hash表，而是字典树，每拿到一个单词直接放入字典树，边放入边统计，字典树利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，字典树相比hash表要省空间，字典树的查询效率只与单词长度有关，而与单词数量无关，单词长度有限，可以认为是O(1)。除了统计词频，字典树还可以用于字典序排序，寻找公共前缀，去除重复字符串等等）
在统计完100个文件之后，再建立一个小顶堆，大小为100，把建立好并存在硬盘哈希表载入内存，逐个对出现次数排序，挑出出现次数最多的100个，由于次数直接和IP是对应的，找出最多的次数也就找出了相应的IP。
100亿条无符号的int类型，找出中位数（中位数是排序后中间的那个数）
首先要有基本概念，100亿条数据大约37G，无符号的int类型大概是40亿，也就是说必然有很多重复数据。
最简单的思路当然是100亿条数据全排序，然后找中间第50亿条数据，但是这个代价太大了。
考虑进行分桶，加入内存限制为512M，也就是0.5G，所以每个桶大约只能处理1亿条数据，所以大概划分为100个桶就足够了，保证每个桶的数据在内存中都可以放的下，总共100个桶也就是说每个桶的范围大概是4千万，第一个桶0-4千万，第二个桶4千万-8千万，以此类推，遍历这100亿条数据，放入到桶中，边遍历还要记录每个桶中装载的数量，结束之后可以根据装载的数量找到第50亿条数据所在的桶，这个桶的装载量是已知的(已经统计出来)，根据前面桶的总装载量可以计算出第50亿条数据在当前桶的位置（用小一点的数据举例子，比如100个数据，中位数位于第3个桶，前面两个桶总共有38条数据，第三个桶有20条数据，那么第50条数据一定是第三个桶中第8大的数据），问题转换为在当前桶中找第n大的数，轮到大根堆或者快排出场了。
这种思路的主要问题在于数据倾斜，比如100亿条数据90%集中在最后一个桶，前面的桶几乎没有什么数据，这种情况应该怎么办？最后一个桶肯定放不下这么多数据，只能对数据非常集中的几个桶进行进一步的分桶，但是这种情况就会增加io的次数。
比如40亿条无符号int数据，找出其中重复的数。
看到这个题不止要判定一个数据是否存在，还要判定是否重复。前面说过如果统计重复次数，那使用位图就不合适了，但要只是判定是否重复而不用统计重复次数，使用位图还是可以做到的。
具体来说我们可以用2个bit位来记录数字的状态，00代表没有这个数字，01代表出现一次，10代表出现多次，这样通过位图就可以判断每个数字的情况了。这里要注意，位图擅长的其实是判定一个数是否存在，这样只有一个状态变量，用0或1就可以判定一个数是否存在，这里仅仅只是多了一个"数据是否重复"的状态变量，就会导致位图的大小多了一倍(原先只需要一个bit位，现在是两个)，同时出现状态位的浪费(11这种状态没有使用到)，如果需要记录更多状态，位图每次都需要翻倍，同时造成更多状态位的浪费，所以位图只适合记录状态非常少的情况。补充一点位图的知识：
位图适合用来快速查找（判定数据是否存在）以及排序，举一个排序的例子，比如这样一个数组：[6, 4, 2, 1, 5]，用位图进行排序，要怎么做呢？看到数据最大为6，申请8个bit位已经完全足够，初始化每个位都是0，遍历数组，用位来记录状态：
原始数组：[6, 4, 2, 1, 5]位图记录：[0 1 1 0 1 1 1 0]对应数字：[0,1,2,3,4,5,6,7]
将位图反向遍历一遍，如果位上的记录是1就输出对应的数字，就可以完成排序。
给定a、b两个文件，各存放50亿个URL，每个URL各占64B，内存限制是4G。请找出 a、b 两个文件共同的URL。
使用hash将相同的url写入同样的小文件，然后小文件之间进行对比，使用hashset。
如果容许一定出错率可以使用布隆过滤器，布隆过滤器可能出现一定的误判，需要评估。