算法
算法
海量数据
5亿整数的大文件，怎么排？
内存估算
假设每个数最多64位，8字节
5,0000,0000x8 ~ 500MBx8 = 4000MB ~ 4G
假设5亿数不重复
内存装的下：
直接快排，得算好久吧..
内存装不下：
- 读文件，数取模%4000存入4000个小文件，每个文件约1M
- 读每个小文件，快排
- 多路归并排序输出
分治/hash映射 + hash统计 + 堆/快排/归并排序
- hash分成n个小文件，满足内存要求：好处是，可以让相同的数或字符串进入同一个小文件
- 小文件排序或统计，或没有本步骤，输出另一份小文件
- 最终要求
- 全排序：使用多路归并
- 找top k：直接小顶堆（找最大top k）or大顶堆；或者每个小文件先找top k，再对比n个top k
- 找两文件不同：两两小文件set对比
数据结构
- bitmap 可用于整数去重等
- trie树 名字来源retrieval
1亿个手机号码，判断重复
不允许有误差的：
- hash到n个小文件中
- 每个文件做统计
- 个数大于1的是重复的
允许有误差的：
布隆过滤器
排序
常见的排序算法
冒泡排序-复杂度O(n^2)-交换排序
对所有相邻记录的关键码值进行比较，如果是逆序（L.r[1].key > L.r[2].key），则将其交换，最终达到有序化。
对无序区从前向后依次将相邻记录的关键码进行比较，若逆序，则将其交换，从而使得关键码值小的记录向上“飘浮”（左移），关键码值大的记录向下“坠落”（右移）。
每经过一趟冒泡排序，都使无序区中关键码值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过n-1趟冒泡排序，就可将这n个记录重新按关键码顺序排列。可看出，若“在一趟排序过程中没有进行过交换记录的操作”，则可结束整个排序过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21/**
* 冒泡排序--更像坠落排序
*
* @param nums
*/
public void sort(T[] nums) {
int len = nums.length;
boolean isSorted = false;
// i区分无序区和有序区
for (int i = len - 1; i >= 0 && !isSorted; i--) {
isSorted = true;
// j将大元素右移
for (int j = 0; j < i; i++) {
if (less(nums[j + 1], nums[j])) {
isSorted = false;
swap(nums, j, j + 1);
}
}
}
}
选择排序-复杂度O(n^2)-选择排序
每一趟从待排序的记录中选出关键码最小的记录，顺序放在已排好序的子序列后面，直到全部记录排序完毕。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18/**
* 选择排序
*
* @param nums
*/
public void sort(T[] nums) {
for (int i = 0; i < nums.length; i++) {
// index指向每轮最小的数
int index = i;
for (int j = i + 1; j < nums.length; j++) {
if (less(nums[j], nums[index])) {
index = j;
}
}
swap(nums, i, index);
}
}
插入排序-复杂度O(n^2) -插入排序
基本思想是，将待排序的记录，按其关键码的大小插入到已经排好序的有序子表中，直到全部记录插入完成为止。
1
2
3
4
5
6
7
8
9
10
11
12
13/**
* 插入排序
*
* @param nums
*/
public void sort(T[] nums) {
for (int i = 1; i < nums.length; i++) {
for (int j = i; j > 0 && less(nums[j], nums[j - 1]); j--) {
swap(nums, j, j - 1);
}
}
}
归并排序-复杂度O(nlogn)-归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/**
* 归并排序
*
* @param nums
*/
public void sort(T[] nums, Class<T> clazz) {
T[] copy = (T[]) Array.newInstance(clazz, nums.length);
System.arraycopy(nums, 0, copy, 0, nums.length);
sort(nums, copy, 0, nums.length);
}
private void sort(T[] nums, T[] copy, int begin, int end) {
if (begin + 1 == end) {
return;
}
int half = (end - begin) / 2;
sort(nums, copy, begin, begin + half);
sort(nums, copy, begin + half, end);
merge(copy, nums, begin, begin + half, end);
}
private void merge(T[] nums, T[] copy, int begin, int mid, int end) {
int i = begin, j = mid, k = begin;
while (i < mid && j < end) {
if (nums[i].compareTo(nums[j]) < 0) {
copy[k] = nums[i++];
} else {
copy[k] = nums[j++];
}
k++;
}
while (i < mid) {
copy[k++] = nums[i++];
}
while (j < end) {
copy[k++] = nums[j++];
}
}
快速排序-复杂度O(nlogn)-交换排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29/**
* 快速排序
*
* @param nums
*/
public void sort(T[] nums) {
sort(nums, 0, nums.length - 1);
}
private void sort(T[] nums, int begin, int end) {
int left = begin + 1, right = end;
while (left < right) {
while (left <= end && less(nums[left], nums[begin])) {
left++;
}
while (right >= begin && less(nums[begin], nums[right])) {
right--;
}
if (left < right) {
swap(nums, left, right);
}
}
if (right <= end && right >= begin) {
swap(nums, begin, right);
sort(nums, begin, right - 1);
sort(nums, right + 1, end);
}
}
堆排序-复杂度O(nlogn)-堆排序
位置 k 的节点的父节点位置 为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
* 堆排序 排成最大堆
* 数组第 0 个位置不能有元素
*
* @param nums
*/
public void sort(T[] nums) {
int cnt = nums.length - 1;
for (int k = cnt / 2; k >= 1; k--) {
sink(nums, k, cnt);
}
while (cnt > 1) {
swap(nums, 1, cnt);
cnt--;
sink(nums, 1, cnt);
}
}
/**
* 下沉
*
* @param nums
* @param k
*/
private void sink(T[] nums, int k, int len) {
while (k * 2 <= len) {
int child = k * 2;
// 判断child + 1未越界
if (child + 1 < len && less(nums[child], nums[child + 1])) {
child++;
}
// 如果子节点比k小，退出循环
if (less(nums[child], nums[k])) {
break;
}
swap(nums, k, child);
k = child;
}
}