uncategorized

大量数据的排序算法

0.介绍

假设有10GB数据文件,数据形式如下

1
2
3
4
5
6
...
120
123
58
789
...

每条数据元素使用换行符\n分割开,即每一行为一条数据。

现在需要排序该文件并输出结果文件。 由于数据量较大,无法直接在内存小于10G的计算机中排序。

下面介绍一种处理方法。

1.标记数据块

建立数据结构Block来保存文件分块信息

1
2
3
4
5
type Block {
id: Number, // 文件块ID
start: Number, // 文件块开始位置
end: Number // 文件块结束位置
}

打开数据文件,每次读取1MB的数据,处理好数据块边界,使得每块数据包含完整的记录。
这样我们得到数据块数组Block[]

2.对每个数据块排序

遍历数据块数组,对每块约1MB的数据排序并写回原文件。
这时数据文件大概是这样子:每块数据是有序的,总体数据无序的。

1
1 4 7 || 3 6 9 || 2 5 8

3.建立堆结构

遍历数据块数组Block[],从每个数据块取出一个元素,建立小顶堆。
这里的每个元素要构造一个数据结构,要包含元素所在数据块的ID。

1
2
3
   1
/ \
3 2

4.堆排序

  1. 调整堆,取出堆顶元素并写入结果文件
  2. 如果取出元素所在数据块还有数据,则从该数据块读取一个元素放到堆顶。
  3. 否则,把堆的最后一项元素移动到堆顶,堆大小减一。
  4. 调整堆。
  5. 循环前面的步骤直至堆为空。
  6. 结束。

5.内存分析

  • 至少需要 数据块大小 的内存。
  • 至少需要 (总数据大小 / 数据块大小)* 堆元素大小 的内存。

分析以上条件得出数据块大小 = (总数据大小 / 数据块大小)* 堆元素大小时占用内存最小, 即

Share