10亿个数中如何高效地找到最大的一个数以及最大的第K个数

  1. 10亿个数中如何高效地找到最大的一个数
    将10亿个数据分成1000份，每份100万个数据，找到每份数据中最大的那个数据，最后在剩下的1000个数据里面找出最大的数据。 从100万个数据遍历选择最大的数，此方法需要每次的内存空间为10^6*4=4MB，一共需要1000次这样的比较。
  2. 10亿个数中如何高效地找到第K个数
    对于top K类问题，通常比较好的方案是分治+hash+小顶堆：

先将数据集按照Hash方法分解成多个小数据集
然后用小顶堆求出每个数据集中最大的K个数
最后在所有top K中求出最终的top K。
如果是top词频可以使用分治+ Trie树/hash +小顶堆：

先将数据集按照Hash方法分解成多个小数据集
然后使用Trie树或者Hash统计每个小数据集中的query词频
之后用小顶堆求出每个数据集中出频率最高的前K个数
最后在所有top K中求出最终的top K。
时间复杂度：建堆时间复杂度是O(K),算法的时间复杂度为O(NlogK)。

  1. top K常用的方法

快排+选择排序：排序后的集合中进行查找
时间复杂度： 时间复杂度为O(NlogN)
缺点：需要比较大的内存，且效率低

分治法：将10亿个数据分成1000份，每份100万个数据，找到每份数据中最大的K个，最后在剩下的1000K个数据里面找出最大的K个，100万个数据里面查找最大的K个数据可以使用Partition的方法
时间复杂度： 时间复杂度为O(N+1000K)

Hash法： 如果这10亿个数里面有很多重复的数，先通过Hash法，把这10亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的K个数。

小顶堆： 首先读入前K个数来创建大小为K的小顶堆，建堆的时间复杂度为O(K)，然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。
时间复杂度： 时间复杂度为O(NlogK)

Trie树： 如果是从10亿个重复比较多的单词找高频词汇，数据集按照Hash方法分解成多个小数据集，然后使用Trie树统计每个小数据集中的query词频，之后用小顶堆求出每个数据集中出现频率最高的前K个数，最后在所有top K中求出最终的top K。
适用范围：数据量大，重复多，但是数据种类小可以放入内存
时间复杂度：O(Len*N)，N为字符串的个数,Len为字符串长度

桶排序：一个数据表分割成许多buckets，然后每个bucket各自排序，或用不同的排序算法，或者递归的使用bucket sort算法。也是典型的divide-and-conquer分而治之的策略。
使用范围：如果已知了数据的范围，那么可以划分合适大小的桶，直接借用桶排序的思路
时间复杂度：O(N*logM)，N 为待排序的元素的个数，M为桶的个数

计数排序：计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
适用范围：只能用在数据范围不大的场景
时间复杂度：O(N)

基数排序：将整数按位数切割成不同的数字，然后按每个位数分别比较。
适用范围：可以对字符串类型的关键字进行排序。
时间复杂度： O(N*M)，M为要排序的数据的位数

  1. 实际情况

（1）单机+单核+足够大内存
顺序遍历（或先用HashMap求出每个词出现的频率）
查找10亿个查询次（每个占8B）中出现频率最高的10个，考虑到每个查询词占8B，则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存，直接在内存中对查询次进行排序，顺序遍历找出10个出现频率最大的即可。
优点： 简单快速
（2）单机+多核+足够大内存

partition + （1）
直接在内存总使用Hash方法将数据划分成n个partition，每个partition交给一个线程处理，线程的处理逻辑同（1）类似，最后一个线程将结果归并。
瓶颈：数据倾斜。每个线程的处理速度可能不同，快的线程需要等待慢的线程。
解决的方法：将数据划分成c×n个partition（c>1），每个线程处理完当前partition后主动取下一个partition继续处理，知道所有数据处理完毕，最后由一个线程进行归并。
（3）单机+单核+受限内存

分治 + （1）
将原文件中的数据切割成M小文件，如果小文件仍大于内存大小，继续采用Hash的方法对数据文件进行分割，直到每个小文件小于内存大小，这样每个文件可放到内存中处理。采用（1）的方法依次处理每个小文件。
（4）多机+受限内存

数据分发 + （3）
将数据分发到多台机器上，每台机器采用（3）中的策略解决本地的数据。可采用hash+socket方法进行数据分发。
Hadoop
首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上，最好可以让数据划分后一次读入内存，这样不同的机器负责处理不同的数值范围，实际上就是Map。
得到结果后，各个机器只需拿出各自出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是Reduce过程。
对于Map函数，采用Hash算法，将Hash值相同的数据交给同一个Reduce task；对于第一个Reduce函数，采用HashMap统计出每个词出现的频率，对于第二个Reduce 函数，统计所有Reduce task，输出数据中的top K即可。

海量数据排序——如果有1TB的数据需要排序，但只有32GB的内存如何排序处理

1、外部排序　　
外排序采用分块的方法（分而治之），首先将数据分块，对块内数据按选择一种高效的内排序策略进行排序。然后采用归并排序的思想对于所有的块进行排序，得到所有数据的一个有序序列。

例如，考虑一个1G文件，可用内存100M的排序方法。首先将文件分成10个100M，并依次载入内存中进行排序，最后结果存入硬盘。得到的是10个分别排序的文件。
接着从每个文件载入9M的数据到输入缓存区，输出缓存区大小为10M。
对输入缓存区的数据进行归并排序，输出缓存区写满之后写在硬盘上，缓存区清空继续写接下来的数据。对于输入缓存区，当一个块的9M数据全部使用完，载入该块接下来的9M数据，一直到所有的9个块的所有数据都已经被载入到内存中被处理过。最后我们得到的是一个1G的排序好的存在硬盘上的文件。

美团面试
有10亿个整形数据，用逗号分割在一个文件里，将排序后的写到另一个文件里。
将每个整形数/（Integer.MAX_VALUE/10)，分配到10个桶里，然后分别排序，序号小的桶必然在前面。还有个优化的点就是用频率压缩长度。

  1. class Main{
  2.     public static void main(String[] args){
  3.         Scanner scanner  = new Scanner(System.in);
  4.         String temp = "";
  5.         List<Integer>[] list = new ArrayList<>()[10];
  6.         while(scanner.hasNext()){
  7.             char c = scanner.nextChar();//没有这个方法，不过面试官说不介意
  8.             if(Charcter.isDigtal(c)){
  9.                 temp += c;
  10.             }else{
  11.                 int e = Integer.parseInt(temp);
  12.                 list[e/(Integer.MAX_VALUE/10)].add(e);
  13.                 temp ="";
  14.             }
  15.         }
  16.         ...//排序
  17.     }
  18. }

10亿个int，一个int是4字节，那就是40亿字节，1GB是10的9次方字节，也就是10亿字节，也就是说10亿int是4GB，Linux单个文件最大也是4GB。

如何从100亿个URL中找出相同的URL？

100亿个网址（URL）要占用多少空间呢？如果每个网址平均长度为100个字符，每个字符要占用4字节，则这份100亿个网址的列表将占用约4兆兆字节（4TB）。在内存中可能放不下那么多数据。

若将所有数据存储在一台机器上，可以对数据进行两次扫描。第一次扫描是将网址列表拆分为4000组，每组1GB。简单的做法是将每个网址u存放在名为.txt的文件中，其中x=hash(u)%4000。也就是说，我们会根据网址的散列值（除以分组数量取余数）分割这些网址。这样一来，所有散列值相同的网址都会位于同一文件。
第二次扫描时，我们其实是在实现前面简化版问题的解法：将每个文件载入内存，创建网址的散列表（HashMap），找出重复的。

40亿个不重复并且没有排过序的无符号的int整数

一台普通PC，2G内存，要求处理一个包含40亿个不重复并且没有排过序的无符号的int整数，给出一个整数，问如果快速地判断这个整数是否在文件40亿个数据当中？
40亿个int占（40亿*4）/1024/1024/1024 大概为14.9G左右，很明显内存只有2G，放不下，因此不可能将这40亿数据放到内存中计算。要快速的解决这个问题最好的方案就是将数据搁内存了，所以现在的问题就在如何在2G内存空间以内存储着40亿整数。一个int整数在java中是占4个字节的即要32bit位，如果能够用一个bit位来标识一个int整数那么存储空间将大大减少，算一下40亿个int需要的内存空间为40亿/8/1024/1024大概为476.83 mb，这样的话我们完全可以将这40亿个int数放到内存中进行处理。

1个int占4字节即48=32位，那么我们只需要申请一个int数组长度为 int tmp[1+N/32]即可存储完这些数据，其中*N代表要进行查找的总数，tmp中的每个元素在内存在占32位可以对应表示十进制数0~31,所以可得到BitMap表:

(1)如何判断int数字放在哪一个tmp数组中：将数字直接除以32取整数部分(x/32)，例如：整数8除以32取整等于0，那么8就在tmp[0]上；
(2)如何确定数字放在32个位中的哪个位：将数字mod32(x%32)。上例中我们如何确定8在tmp[0]中的32个位中的哪个位，这种情况直接mod上32就ok，又如整数8，在tmp[0]中的第8 mod上32等于8，那么整数8就在tmp[0]中的第八个bit位（从右边数起）