海量数据处理方法
海量数据处理方法
当数据量特别大时，首先排除直接加载到内存中的算法，最核心的思路往往是分治，比如排序时先将大文件分割成多个足以加载到内存中的小文件，然后利用内存排序算法分别排序得到有序的一些小文件，最后通过归并排序得到最终的结果。
中位数
一共有 N 个机器，每个机器上有 N 个数。每个机器最多存 O(N)个数并对它们操作。如何找到 N^2 个数中的中数
方案 1：先大体估计一下这些数的范围，比如这里假设这些数都是 32 位无符号整数（共有 2^32 个）。我们把 0 到 2^32-1 的整数划分为 N 个范围段，每个段包含（2^32）/N 个整数。比如，第一个段位 0 到 2^32/N-1，第二段为（2^32）/N 到（2^32）2/N-1，……，第 N 个段为（2^32）（N-1）/N 到 2^32-1。然后，扫描每个机器上的 N 个数，把属于第一个区段的数放到第一个机器上，属于第二个区段的数放到第二个机器上，……，属于第 N 个区段的数放到第 N 个机器上。注意这个过程每个机器上存储的数应该是 O(N)的。下面我们依次统计每个机器上数的个数，一次累加，直到找到第 k 个机器，在该机器上累加的数大于或等于（N^2）/2，而在第 k-1 个机器上的累加数小于（N^2）/2，并把这个数记为 x。那么我们要找的中位数在第 k 个机器中，排在第（N^2）/2-x 位。然后我们对第 k 个机器的数排序，并找出第（N^2）/2-x 个数，即为所求的中位数的复杂度是 O（N^2）的。
方案 2：先对每台机器上的数进行排序。排好序后，我们采用归并排序的思想，将这 N 个机器上的数归并起来得到最终的排序。找到第（N^2）/2 个便是所求。复杂度是 O（N^2*lgN^2）的。
排序
对海量数据进行排序
方案：海量数据肯定无法直接加载到内存中执行排序，所以考虑使用外部排序，外部排序的执行步骤如下：
- 根据可用内存的大小，将外存上含有 n 个记录的文件分成若干长度为 t 的子文件（或段）；
- 其次，利用内部排序的方法，对每个子文件的 t 个记录进行内部排序，并写回外存。
- 对这些排过序的文件两两进行归并，直到所有待排序记录最后保存到同一个有序文件中。
去重
特别大量的字符串，怎么去掉其中重复的，保留没有重复的字符串。
如果是小文件，可以考虑直接使用trie树或HashMap来去重。
如果是大文件，就需要先把字符串hash到小文件，再对小文件做去重了。
在2.5亿个整数中找出不重复的整数，内存不足以容纳这2.5亿个整数。
方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32*2bit=1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
方案2：划分小文件。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。