为什么我们要尽量避免FileSort(文件排序)

故事

现在，假设阅读此文的你穿越回了小学二年级的时光，此时的你正在不断的追求着隔壁班的班长小红，恨不得把家里所有东西都送给TA。那么问题来了，如果你要把家里东西都搬光送给小红，你有几种办法？以下是我想到

• 一件一件的搬，如果搬不动那就拆分（不排除你被你父母揍一顿的可能性）
• 试图通过吃药让自己变成大力士

上述例子看似滑稽，但其实这是一直以来人类解决大规模数量问题的解决方案，即要么提升自身的能力以应付大规模的数量，要么进行拆分，分而治之。

对应到IT行业，由于传统小型机处理能力有限于是便有了大型机。如果不用大型机那咋办吗？只好拆分服务，于是便有了微服务。

经典面试题

面试官：假设你只有100M的内存可用，现在有一个大小为1G的文件，里面存放着整数，每个整数用4个字节来存储，要你对这个这个文件中数据进行排序，你有什么解决方案?

我：打电话找行政的妹子跟她要一条8G的DDR4内存条,为了表示感谢顺便约她去吃饭, 说不定还能顺利脱单。

面试官：emmm….., 回去等通知吧

解决方案

我：要解决这个问题，首先我们需要分为两种情况:

• 数据不重复 如果数据不重复我们可以使用位图来标记相应的数据，在需要输出结果的时候遍历位图即可（此方案较为简单，不在本文的讨论范围内)

• 数据重复 由于只有100M的内存可用，完全利用这100M内存的情况下意味着我们一次可以对26214400个整数(100 * 1024 * 1024 / 4 ) 进行排序, 这意味着我们要分次读取文件并对读取的内容进行排序，并将每一次排序的结果保存到文件系统中,之后再对这些文件进行合并。

面试官：可以用画图表示一下吗？

我：过程如下图所示

面试官：可以，要不你现场写一下代码吧

解决方案的实现

解决方案的实现总的来说有以下几步

• 根据缓冲区的大小读入相应的数据量，并把他们转为整数数组，进行排序，并写入文件，重复这一步直到原始数据文件中没有数据可读。

• 合并这些已排序的文件直到只剩一个文件

将问题拆分开来看的话，我们需要解决以下子问题

• 由于我们采用4个字节的数据来保存整数，因此我们需要解决整数按字节存取的问题

你可以考虑一下为什么我们要用四个字节来存取整数?而不是将其转为字符串

.

• 合并已排序的文件的算法

方案一、预读取一部分的数据写入缓存中，然后进行归并排序(拆分之后的文件中的数据都是有序的)，当数据用完时再去文件中读取，重复此步骤直到没有数据可读

方案二、每次只从两个文件中读取一个整数，进行比较，然后将较大/较小(取决于你要增序还是降序)的数据写入文件中

.

方案一,相对来说比较简单并且速度比较快留给大家实现。

对于方案二，由于最近开发中有涉及状态机，因此对于方案二我采用了状态机的设计模式来实现。

该状态机如下所示

外部排序的实现

给大伙提供个参考，我实现的方案还有进一步优化的空间