漫画: 什么是外部排序?

﹏ヽ暗。殇╰゛Y 2023-03-01 05:52 118阅读 0赞

> 问： 目前给你一个包含20亿个int类型的整数，计算机的内存只有2GB，该怎么排序？

一个int数占4个字节（byte）， 20亿个int类型占`20*4=80`亿个字节， 80亿个字节大概要占用8GB的内存，而计算机只有2GB的内存

*  1GB = 1024MB = 1024 \* 1024KB = 1024 \* 1024 \* 1024bit=1073741824bit=10.7亿个字节
 *  80亿/1024/1024/1024 =7.45058GB≈8GB

计算机装不下。为了解决这个问题，我们可以将8GB的数据平分成4个2GB的数据来排，排好之后再把它们拼凑回去。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

排序的时候我们可以选择快速排序或归并排序等算法。

接着我们可以把两个小的有序子串合并成一个大的有序子串。  
![在这里插入图片描述][20201022223102694.png_pic_center]  
**注意：读取的时候是每次读取一个int数，通过比较之后在输出。**

按照这个方法来回合并，总共经过三次合并之后就可以得到8G的有序子串。

> 问： 举个例子

我们先假设需要排序的int数有12个，内存一次只能装下3个int数  
![在这里插入图片描述][20201022223236327.png_pic_center]  
接下来把12个数据分成4份，然后排序成有序子串  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]

然后把子串进行两两合并 【**两路归并**】  
![在这里插入图片描述][20201022223321379.png_pic_center]  
输出哪个元素，就在那个元素所在的有序子串再次读入一个元素  
![在这里插入图片描述][20201022223334719.png_pic_center]  
继续  
![在这里插入图片描述][20201022223349473.png_pic_center]  
重复直到合并成一个包含6个int的有序子串  
![在这里插入图片描述][20201022223402605.png_pic_center]  
再把两个包含6个int的有序子串合并成一个包含12个int数据的最终有序子串  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]

> 问： 刚刚的那个例子有很大的问题，请问是什么？

IO消耗太大，每个数据都从硬盘读了3次，写了3次。而硬盘的读写速度比内存慢得多，花了太多时间在硬盘的读写上。

*  解释下：例如对于数据2，我们把无序的12个数据分成有序的4个子串需要读写各一次，把2份3个有序子串合并成6个有序子串读写各一次；把2份6个有序子串合并从12个有序子串读写各一次，一共需要读写各3次。

> 问：该怎么优化呢？

第一反应就是减少硬盘读写的次数。

刚刚在归并的时候，我们采用的是两路归并，就是每次从磁盘读写两个数据。如果想要减少硬盘IO读写次数，我们可以每次从硬盘中读出来的就是多一点就可以了啊，也就是**多路归并**

比如：假设内存一共可以装4个int型数据。我们每次读取4个数据（**四路归并**）归并成有序子串，这样就只需要读写3次IO就可以了  
![在这里插入图片描述][20201022224428607.png_pic_center]  
如果每次读取n个归并成有序子串，这样的算法叫做**n路归并**

> 问： n是越大越好吗？

不是， n越大，IO次数越少（将n个数据读取到内存中）；但是由于在合并的时候，需要从n个数据中选出一个最小值，而n约到，选取就越花时间。

> 问：还可以继续优化吗？

我们采用另外一种排序方法

假设当前硬盘有12个无序的int类型的数据  
![在这里插入图片描述][20201023221716606.png_pic_center]  
读入3个到内存中  
![在这里插入图片描述][20201023222022649.png_pic_center]  
构建最小堆，且选出目标数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 3]  
读入下一个数86  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]

读入下一个数3，比70小，暂放一边，不加入堆结构中  
![在这里插入图片描述][20201023222233848.png_pic_center]  
读入下一个数据24，比81小，不加入堆结构  
![在这里插入图片描述][20201023222246848.png_pic_center]  
读入下一个数据8，比86小，不加入堆结构。此时p1已经完成了，把那些刚才暂放一边的数重新构成一个堆，继续p2的存放。  
![在这里插入图片描述][20201023222300686.png_pic_center]  
以此类推…

最后生成的p2如下：

![在这里插入图片描述][20201023222321141.png_pic_center]  
这样下来，最后只生成了2个有序子串，我们把这种方法称之为**置换选择**

按照这种方法的话：

*  最好的情况下，所有数据可以只生成一个有序子串
 *  最坏的情况下，还是得到4个子串
 *  平均情况下：**如果内存可以容纳n元素的话，那么平均每个子串的长度是2m，我们可以减少一半的子串个数**

这种方法适合要排序的数据太多，以至于内存一次性装载不下。只能通过把数据分几次的方式来排序，我们也把这种方法称之为外部排序

总结：

> 从12个数据中读取3个数据，构建成一个最小堆，然后从堆顶选择一个数写入到p1中。

> 之后再从剩余的9个数中读取一个数，如果这个数比刚才那个写入到p1中的数大，则把这个数插入到最小堆中，重新调整最小堆结构，然后在堆顶选一个数写入到p1中。

> 否则，把这个数**暂放在一边，暂时不处理**。之后一样需要调整堆结构，从堆顶选择一个数写入到p1中。

> 这里说明一下，那个被放在一边的数是不能再放入p1中的了，因为它一定比p1中的数都要小，所以它会放在下一个子串中

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20230209/0be985cf32724e6892f069d34c0b6643.png
[20201022223102694.png_pic_center]: /images/20230209/0053bff3bd884c97823a5777ca42b8a4.png
[20201022223236327.png_pic_center]: /images/20230209/bbac1d2a54e9480b970d4e2e0f32a909.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230209/7590caa20ec7447d80dc5f417e89a4cb.png
[20201022223321379.png_pic_center]: /images/20230209/b4848398777340b89beddb4224a00e52.png
[20201022223334719.png_pic_center]: /images/20230209/472ea441f22245e2981023c271a28154.png
[20201022223349473.png_pic_center]: /images/20230209/5634715c4f224281b3eea72aa8f85059.png
[20201022223402605.png_pic_center]: /images/20230209/da5e15b756344195afe0ae3df55ce288.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230209/c11ceb3c402c44f5a706c4253d1760e3.png
[20201022224428607.png_pic_center]: /images/20230209/04d4972fc29742e2a3d4e23db0f0d156.png
[20201023221716606.png_pic_center]: /images/20230209/9657a27eb8c149ab838ed9ff6f4de7f1.png
[20201023222022649.png_pic_center]: /images/20230209/72023cb7226b4bf5ba12eb6115f09f72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230209/54e3aea4d3444fd7867a8af5a93d46df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230209/16ea69ed142141eb91fe8ccb365fa4f1.png
[20201023222233848.png_pic_center]: /images/20230209/4cb617a7edc04aaa85fea1b47e5a0a76.png
[20201023222246848.png_pic_center]: /images/20230209/f9a41b352d6348569037420ba306f5d0.png
[20201023222300686.png_pic_center]: /images/20230209/176a867b3f2541e1a984abb3855af8b0.png
[20201023222321141.png_pic_center]: /images/20230209/9eb816c4ad614aabbee80238cbca4d78.png