海量数据相关面试问题（一）：海量数据文件排序问题（Bitmap、多路归并算法）_海量数据归并排序

---

前引

---

最近在刷面试题的时候 发现类似于海量数据相关问题 考察的频率还是非常高的 而且也基本上都是套路题

大概掌握住相关问题的解决办法 那么类似的问题也可以从这个点去研究
类似于Top-k啊 数据去重啊 数据查重啊 数据排序啊 等等 后面也都会挨着挨着大概把这部分类型自己给整理出来

毕竟百说不如一做
就像真的面试的时候 那种环境 如果不是真的东西心知肚明 仅仅只是靠刷面经 很多知识不牢靠的话 尤其是大厂面试 更是讲究

一、知识的广度 了解多少知识？
二、知识的深度 对于一部分大家都了解的东西 举个例子 vector怎么设计的 你是否了解 了解的话 一直往你的知识极限认知去问问题的话 你真的掌握了多少 了解多少 一下子面试官就能对你能够有个认知

所以 在刷了还是部分面经的时候
我太感谢之前这一年半自己 持之以恒的保持学习
说真的没有这一年半 面试真的在复习面经的时候 十有八九是肯定不会的 很多本来就是需要 在自己手动实践过才深刻认知的原理 光看面经是肯定止不住的

那废话少说 这类非常常考 而且相对一般的八股文难度又高的问题
我们还是自己做个整理吧 我对多路归并排序也只是粗浅的了解了一下
估计在下面自己写过代码后 自己才真的能够明白运行流程是什么

走着

---

海量数据相关面试问题（一）：海量数据文件排序问题（Bitmap、多路归并算法）

---

这里推荐大家关注一下这个博主 总结的特别好
CSDN 博主：v_JULY_v

很多面试非常常考的东西 这个博主也都介绍到了
详细的可以进主页去看看

---

1、如何给磁盘文件排序

---

下面是我截取的面试题
输入：给定一个文件，里面最多含有n个不重复的正整数（也就是说可能含有少于n个不重复正整数），且其中每个数都小于等于n，n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。

---

1、一些相关问题的 遐想总结

---

我看了类似的很多个这样的题目 都是有内存限制的
例如数据排序啊

对于数字容量较小的 排序 其实又和TOP-K扯上了关系
而TOP-K的算法 是必须必须 尤其是应届生校招啊 实习啊 出现是相当相当多的
这个之后会出一篇博客专门来总结TOP-K的 也是加深自己对TOP-K的印象

---

对于通常小数字的数据排序 下面几种算法是必须要掌握的 而且是在睡着的时候醒来 马上让写就能写出来的程度

1、最基本排序（冒泡、插入、选择）
2、进阶排序（堆排序、归并、快排）
3、减治法（Quick Select(以快排为基础 需要了解））

当然 一般以一道最简单的排序力扣或者牛客的排序题目 就是让你手撕这些算法 堆排序和快排应该是出现频率最高的 最后的Quick Select 则是在TOP K中需要掌握的

---

稍微数据大一点的 例如几十万 尤其是让去重 数据去重
下面几个是非常查用的方法
Hashtable 也就是我们非常常用的哈希表
Bitmap 这是我们省空间用的位图 当然这个也只能针对数字以及比较简单的场景 确认是否存在啊 或者省空间存储数字 还是相当好用的
Bloom Filter 布隆过滤器 必须需要掌握其实现原理 以及可能存在的问题（假阳 为什么会有假阳？）

这几个基本上就足够对付数据查重了 当然Bloom Filter的底层就是利用比特数组和Hash映射函数实现的 也算是整合了一下的应用

---

上面这部分就是小遐思了 但是我对于海量数据的处理
目前也只熟练掌握了目前这一种 对于去重 排序

对于热点数据啊 或者其他的重复数据这类我还没有掌握（或者说还没有开始看）

没事 这部分应该有可能会分成3篇来写 这三篇写完 这部分的问题就随便没问题了

---

2、bitmap排序（对于数据重叠无能为力/可排除重复数字）

---

1、bitmap排序 思路介绍

---

bitmap的适用场景比较窄 但是对于内存紧凑 尤其是数字类型的存储 或者对于 查询是否存在的的场景 则可以大展身手了

bitmap核心就是bit存储 本来一个数字需要四字节的 如果用位来表示 用字符数组来表示32位整数的话 那空间就节约的多了

例如bloom filter底层也是以这个作为桶映射 也是非常方便
唯一有缺陷 或者面试中相关问题 对于有重复数字的情况 需要存储重复数字的情况 那么bitmap则不能上场了
换种思路想 对于去重 那也是大杀四方 因为相同的数据 都被表示在1位上面了 不能表示重复数字 但是可以表示有数字 也就是这个道理了

---

上面对于bitmap详细的讲了一下
排序、去重的时候 可以考虑考虑

下面就是实际应用了 自己写了代码 对于这个东西的理解肯定就更深刻了
也就是解决上面那道题的解决办法的代码呈现形式

---

2、bitmap排序 代码实现（代码中排序数组大小为10000000）

---

设置10000000个随机数（包含重复）

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>

const int kMaxNum = 10000000;

int main() {
  srand(static_cast<unsigned long>(time(NULL)));
  
  int fd = open("data.txt", O_RDWR | O_CREAT | O_TRUNC, 0777);
  if (fd < 0) {
    return 0;
  }
  
  char buf[100] = {0};
  for (int i = 0; i < kMaxNum; ++i) {
    int num = rand() % kMaxNum;
    int size = sprintf(buf, "%d\n", num);
    write(fd, buf, size);
  }
  close(fd);
  return 0;
}
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

---

bitmap排序

#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>

#include <cstdio>
#include <bitset>

const int kOneLoopMaxNum = 5000000;
const int kMaxNum = 10000000;

using namespace std;

int main() {
  srand(static_cast<unsigned long>(time(NULL)));
  
  FILE* fp = fopen("data.txt", "rw+");
  if (!fp) {
    return 0;
  }
  
  bitset<kMaxNum> bitmap;
  int num;
  
  while (fscanf(fp, "%d\n", &num) != EOF) {
    if (num >= 0 && num < kOneLoopMaxNum) {
      bitmap[num] = 1;
    }
  }
  
  FILE* write_fp = fopen("sort_data.txt", "rw+");
  if (!write_fp) {
    fclose(fp);
    return 0;
  }
 
  char buf[100] = {0}; 
  for (int i = 0; i < kOneLoopMaxNum; ++i) {
    if (bitmap[i] == 1) {
      int size = sprintf(buf, "%d\n", i);
      fwrite(buf, size, 1, write_fp);
    }   
  }
  
  bitmap.reset();
  
  fseek(fp, 0, SEEK_SET);
  while (fscanf(fp, "%d\n", &num) != EOF) {
    if (num >= kOneLoopMaxNum && num <= kMaxNum) {
      num -= kOneLoopMaxNum;
      bitmap[num] = 1;
    }
  }
   
  for (int i = 0; i < kOneLoopMaxNum; ++i) {
    if (bitmap[i] == 1) {
      int size = sprintf(buf, "%d\n", i + kOneLoopMaxNum);
      fwrite(buf, size, 1, write_fp);
    }   
  }
  
  fclose(write_fp);
  fclose(fp);
  return 0;
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

---

2、bitmap排序 结果验证

---

原数据10000000个整型数字

---

排序后 数据经过验证正确（数字去重后）

---

3、多路归并算法（内部排序 + 外部排序）

---

1、多路归并算法 思路介绍

---

这里总算是把多路归并算法搞清楚了
多路归并算法多用于 无法一次性把数据放入内存中排序

先在内存中排序好 N个小文件块（例如十万级别数据的） 再通过(M / N)路在外部文件归并排序 外部排序本质就是将K个已经排序好的文件块 整合到一个大文件块中

这个相对bitmap运用范围就更广一点了 bitmap不能排序数据有重叠的情况 而这个多路归并则不影响
在说其算法本质 也就是每次遍历数据块 维护一个有K个堆节点的堆 然后取出来最小值 然后从最小值所在文件块中继续取出来下一格数据 放入最小堆 继续这样的操作 直到把所有的元素取出来

---

我们对此 肯定还是自己动手写写代码 这样才对这个运行过程了然于胸
下面这一篇文章 对于 从K个队列 如何取出来最小值有方法总结
其实本质也就是 一个动态维护TOP-K的问题

算法—外部排序&多路归并

三种方法
1、一个数组 先排好序 最前面的元素就可以取出来 然后下一个放进去的元素二分查找找到就可以插入位置 继续这样的操作
2、利用最小堆（下面的代码就是这样的办法）利用最小堆来存取元素
3、胜者树、败者树（其实方法不如上面两种） 节点数多 而且时间复杂度一样 还是提一嘴原理 就是通过比较 决出父节点 再让父节点去参与下一轮比较 从而决出最后的胜利的节点 就作为放入的元素 插入的时候 则将底部的元素替换上一个插入的元素 然后继续这样的比较 方法不好 不如上面两种

---

2、多路归并排序 代码实现（代码中排序数组大小为10000000）

---

那我们代码就放在下面了

#include <stdlib.h>
#include <time.h>
#include <fcntl.h>
#include <unistd.h>

#include <cstdio>
#include <algorithm>
#include <memory>
#include <vector>
#include <queue>

const int kOneLoopMaxNum = 1000000;
const int kMaxNum = 10000000;

using namespace std;

string GetFileName(int index) {
  char buf[100] = {0};
  int size = sprintf(buf, "data%d", index);
  return string(buf);
}

FILE* CreateNewFile(int index) {
  string filename = GetFileName(index);
  FILE* newfile_fp = fopen(filename.data(), "w");  
  if (!newfile_fp) {
    printf("ReadCreateNewfile create newfile failed!\n");
    return nullptr;
  }
  return newfile_fp;
}

int CreateFileAndSortInMemory(FILE* fp, int index) {
  unique_ptr<int> nums(new int[kOneLoopMaxNum]);
  int numsindex = 0;
  while (numsindex < kOneLoopMaxNum && fscanf(fp, "%d\n", &nums.get()[numsindex]) != EOF) {
    ++numsindex;
  }
  printf("read nums : %d\n", numsindex);
  if (!numsindex) {
    return 0;
  }
  
  FILE* newfile_fp = CreateNewFile(index);
  if (!newfile_fp) {
    printf("Create File failed!\n");
    exit(0);
  }
  sort(nums.get(), nums.get() + numsindex);
  for (int i = 0; i < numsindex; ++i) {
    fprintf(newfile_fp, "%d\n", nums.get()[i]);
  } 
  fclose(newfile_fp);
  return numsindex;
}

int MemorySort(FILE* fp) {
  int filenums = 0;
  while (true) {
    int readnums = CreateFileAndSortInMemory(fp, filenums);
    if (readnums) ++filenums;
    else break;
  }
  return filenums;
}

void MergeSort(int filenums) {
  vector<FILE*> files(filenums, nullptr);
  auto cmp = [&](const pair<int, int>& a, const pair<int, int>& b) -> bool { return a.first > b.first; };
  priority_queue<pair<int, int>, vector<pair<int, int>>,decltype(cmp)> queue(cmp);

  for (int i = 0; i < filenums; ++i) {
    string filename = GetFileName(i);
    files[i] = fopen(filename.data(), "r");
    if (!files[i]) {
      printf("MergeSort open file %s failed!\n", filename.data());
      return;
    }
  }
  
  FILE* write_fp = fopen("mergesort_sort_data.txt", "w");
  if (!write_fp) {
    printf("MergeSort create file mergesort_sort_data.txt failed!\n");
    return;
  }
  
  for (int i = 0; i < filenums; ++i) {
    fseek(files[i], 0, SEEK_SET);
  }
  
  int num = 0;
  for (int i = 0; i < filenums; ++i) {
    if (fscanf(files[i], "%d\n", &num) != EOF) {
      queue.emplace(num, i);
    }
  }
  
  while (true) {
    if (queue.empty()) break;
    
    const auto minnum = queue.top().first;
    const auto index = queue.top().second;
    queue.pop();
    fprintf(write_fp, "%d\n", minnum);
    if (fscanf(files[index], "%d\n", &num) != EOF) {
      queue.emplace(num, index);
    }
  }
  
  for (int i = 0; i < filenums; ++i) {
    fclose(files[i]);
  }
  fclose(write_fp);
  return;
}

int main() {
  FILE* fp = fopen("data.txt", "r");
  if (!fp) {
    return 0;
  }
  
  int filenums = 0;
  filenums = MemorySort(fp);
  MergeSort(filenums);
  
  fclose(fp);
  return 0;
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

---

3、多路归并算法 结果验证

---

其中data0->data9 我们采用1000000一百万的数字为一组 则产生了10个临时文件（已经排序完成）

---

最后看看多路排序的结果

---

2、浅浅总结一下

---

对于这种大数据排序的题
这两个是绝对可以在考虑范围之内上场的

至于大家都熟悉的set 咱们也就没有提了
那我们下篇再去看看其他 海量数据类型面试了

下篇再见 ヾ(￣▽￣)Bye~Bye~