岁虚山

行由不得,反求诸己

0%

编程珠玑-磁盘文件排序

问题

假设现在有一个包含有 5000000(500万)个整数型的数据列表,其中的数据范围为 0 — 9999999,并且无重复数据。现在,我们想对这个列表进行排序,该如何去做呢?

答案似乎很简单,无论是最简单的冒泡排序,选择排序到稍微复杂点的快速排序、归并排序,甚至许多编程语言都内置了相关的排序算法,都能简单的解决这个问题。

那么,如果再加上一点限定条件呢?比如说这些数据存在于磁盘中的一个文件中,我们需要将这个文件内的数据排序后输出到另一个文件中,又该怎么做呢?

我们知道,一个 int 型的数据在绝大多数编程语言中占 4 个字节,即 4B ,那么500万个整型数据就是2千万个字节,大概是 19M,即这个文件的大小大概在 19M 左右。

无论上述的各种排序算法性能如何,都有一个共同的特点:所有的操作都是在内存中完成的。也就是说,我们如果想使用以上所述的排序算法,所做的第一件事便是读取文件,将文件中的所有数据读入到一个内存中,然后再通过以上算法进行排序运算,最后输出到一个文件中。

听起来似乎很简单,我们要做的无非是三步:

1、读取文件,将数据存入一个500万大小的数组中;

2、对这个数组进行排序;

3、将排序后的数组中的数据输出到一个文件中。

本文肯定不会讨论如此简单的问题。那么,让我们再做点有难度的事情。

上面我们计算过,500万个整型数据,需要开辟一个500万大小的整型数组,大概需要 19M 的内存。那么,我们再加一点限定条件:整个系统只有 2M 内存可供使用,也就是说,我们所能使用的内存不能超过 2M。

事情似乎变得有趣起来,我们该如何使用 2M 的内存,来读取大概 19M 的数据,然后对其进行排序呢?

上面我们所说的几种排序算法似乎面对这种情况有些无能为力,那么我们就要思考其他的方法了。

首先我么考虑下, 2M 内存有多大,能够做些什么?

2M 内存,能够存储 524288 个整型数据,即大概52万个数据。显然距离我们的500万个数据规模相差甚远。

既然一次读不完,那么我们是否能够分批对这个文件进行读取处理呢?

我们似乎看到了曙光。500万个数据,我们每次加入只读取50万个数据进行处理,那么只需要10次处理就行了,那还等什么,让我们开始动手吧!

分批排序

首先,我们先创建一个包含500万个不重复的 0 - 9999999 之间的整数列表,并将其写入到一个文本文件中。

1
2
3
4
5
6
7
sampleList = random.sample(range(0, 9999999), 5000000)
with open("./磁盘排序_sample.txt", "w") as file:
for i in range(0, len(sampleList)):
if i < len(sampleList) - 1:
file.writelines(str(sampleList[i]) + "\n")
else:
file.writelines(str(sampleList[i]))

文本内容如下:

样本数据

现在,让我们开始吧!

1
2
3
4
5
6
7
8
9
10
11
12
batch = [0 for i in range(0,500000)]
with open("./磁盘排序_sample.txt", "r") as read:
index = 0
for readLine in read:
batch[index] = int(readLine)
index += 1
if index == len(batch):
with open("./磁盘排序_sorted.txt", "a") as write:
batch.sort()
for i in range(0, len(batch)):
write.writelines(str(batch[i]) + "\n")
index = 0

让我们打开排序后的文本文件看一下内容:

似乎看起来成功了!

等一下,我们再详细看一下文本:

情况似乎有些不对,让我们来分析下我们这个方法:

通过示意图,我们可以看到:我们将样本数据分为 10 个 batch 来处理,对每个 batch 进行排序后输出到文件中去,我们只能保证的是,在样本数据的 10 个 batch 中的每个 batch 内部,数据是有序的,也就是说,batch1 中的数据是有序的,batch2 中的数据也是有序的,但是,batch1 和 batch2 内的数据是有序的吗?

并不是,因为我们的排序的数据只局限于每个 batch 中,batch 之间并没有进行过排序操作,因此无法保证分批处理后,得到的所有数据都是有序的。

这个方法失败了,似乎分批的想法行不通,那么该怎么办呢?

别急,我们换个角度思考。让我们再审一边问题:

假设现在有一个包含有 5000000(500万)个整数型的数据列表,其中的数据范围为 0 — 9999999,并且无重复数据。现在,我们想对这个列表进行排序,并且使用的内存不能超过 2M,该如何去做呢?

既然将数据分批的思路行不通,那么我们是否能够将样本数据的数据范围进行分批操作呢?

由问题可知,样本数据的范围是 0 — 9999999,即样本中的每个数据都是1000万内的数字,我们可以使用的内存是 2M ,大概能够记录 50 万个数据。现在,我们把 0—9999999 ,分成 0—499999,500000—999999 …… 9500000—9999999,共20组,我们每次只读取样本数据中的一组数值范围内的数据,并进行排序操作,然后写入文件中去,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
batchSize = 500000
batch = [0 for i in range(0, batchSize)]
batchCount = int(10000000 / batchSize)
for i in range(0, batchCount):
low = i * batchSize
height = low + batchSize
index = 0
with open("./磁盘排序_sample.txt", "r") as read:
for line in read:
if int(line) >= low and int(line) < height:
batch[index] = int(line)
index += 1
with open("./磁盘排序_sorted.txt", "a") as write:
for value in sorted(batch[0 : index]):
write.writelines(str(value) + "\n")

看一下运算结果:

可以看到,这个方法成功得在限定条件内完成了对样本数据的排序。

那么,我们看一下这个方法的运行消耗:

我们可以看到,500万个样本数据,总共读取了20次,相当于总共在磁盘中读取了20 x 500万,即1亿个数据。我们知道,电脑对磁盘的读写速度是远不如对内存读写的速度的。虽然我们成功将数据进行了排序,但是其运行速度十分缓慢,绝大部份时间都消耗在对磁盘数据的读写。

那么,还有没有更好的方法(更快的方法)完成对磁盘文件的读写呢?让我们继续往下看。

位向量

我们设想一种方法,能够最少次数地读取样本文件,能够最少次数的写入结果文件,同时,其排序部分有尽量小的耗时。

我们再观察一遍问题:

假设现在有一个包含有 5000000(500万)个整数型的数据列表,其中的数据范围为 0 — 9999999,并且无重复数据。现在,我们想对这个列表进行排序,并且使用的内存不能超过 2M,该如何去做呢?

我们之前所关注的重点是:

1、500万个整型数据;

2、数据分布范围为 0 —9999999;

3、内存不能超过 2M。

我们似乎忽略了一个重要的点:

> 1、无重复数据

这个要点能否帮助我们完成我们期待的算法呢?

我们来看一个简单的例子,假如我们有一组数据:

0 ,9,4,7,3

我们该如何将这组数据通过一种简单的方法进行排序呢?

假如我们有10个桶,每个桶只有两种状态:空和满,给这十个桶写上编号,分别是 0 ,1 ,2 …… 9:

f3_1

现在,10个桶都是空的,我们把这组数据按照其元素的值的大小,放入编号与值相同的桶中,如 9 放入编号为 9 的桶里,3 放入编号为 3 的桶里。

f3_2

现在,我们的10个桶里总共有5个桶是满的,我们只要从头遍历这10个桶,遇到满的桶就将其编号记录下来:

0 ,3 ,4 ,7 ,9

我们似乎已经得到了排序好的数据。那么,我们是否能用这个方法来解决我们最初的问题呢?

首先,我们来分析一下上面方法能够使用的条件:

1、要有足够多的桶(桶的编号要能包含样本数据中所有元素的可能值);

2、样本数据不重复;

我们来看我们的题目是否满足以上两点要求:

1、要有足够多的桶:

​ 我们的样本数据范围是 0 — 9999999 ,那么我们就需要 1000万个桶,假如我们定义一个 int 型数组来当作桶,那么这个数组的大小应该是 int a[10000000];很容易算出来,a 的大小应该是 10000000 x 4 / 1024 /1024 = 38.15M ,但是我们能够使用的内存只有 2M,不满足条件。

2、数据不重复:

​ 由题目可知,我们的样本数据无重复数据,因此是满足条件的。

似乎又陷入了僵局,还是内存大小不满足条件,那我们真的没有别的办法了吗?

等一下,我们知道,一个 int 型数据占 4 个字节,而一个字节是 8 个比特位,我们能否用一个比特位来当作一个桶呢?

稍微计算一下,1000万个桶就是1000万个比特位 = 1.2M,比问题中要求的要小,似乎是可行的!

我们来尝试一下(1000万比特位是 312500 个 int 型数组的大小):

1
2
3
4
5
6
7
8
9
10
11
12
13
bucketCount = 312500
buckets = [0 for i in range(0, bucketCount)]
with open("./磁盘排序_sample.txt", "r") as read:
for line in read:
bucketIndex = int(int(line) / 32)
byteIndex = int(line) % 32
buckets[bucketIndex] = buckets[bucketIndex] | (1 << byteIndex)

with open("./磁盘排序_sorted.txt", "a") as write:
for i in range(0, bucketCount):
for j in range(0, 32):
if buckets[i] & (1 << j) != 0:
write.writelines(str(i * 32 + j) + "\n")

查看运行结果:

成功!

引申1

如果我们再加一个限定条件,所使用内存不能超过 1M,那我们这个算法还适用吗?

答案显而易见,我们想要使用这个算法,最少需要使用大概 1.2M 的内存空间,因此这个算法就不能适用了。那我们该怎么办呢?

会想下我们最开始的做法,我们只要将样本数据的数据范围 0—9999999 分为两批:

0—4999999

5000000—9999999

然后将这两种算法相结合,便能满足我们的需求。

引申2

如果样本数据中的数据是可以重复的,但是每个数据的重复次数不超过10次,那么这个算法还能适用吗?

这种情况下,我们只需要将算法进行稍微的变动。我们原本的做法是将 1 个比特位当作一个桶,现在,我们将 4 个比特位当作一个桶,那么,一个桶的状态便有 16 种情况,即一个桶可以表示 0—15 的数据,我们只要将重复的数据塞到同一个桶里,同时,这个桶通过其本身的 4 比特位进行计数。读取完毕后,再反过来遍历桶,便能达到我们的目的。

如果将 4b 当作一个桶,我们需要的内存大概是 4.7M,超出了 2M 的内存大小,这事,我们便可以将样本数据的范围进行分批处理,同样能够满足问题的要求。

-------------本文结束 感谢阅读-------------
打赏一包辣条