给定硬盘上的100 GB整数数据,RAM为2 GB,如何使用最少的磁盘操作对整数进行排序.这里从磁盘中获取一个数字被视为一个磁盘操作(尽管实际上可以获取一个数据块).
我们可以使用磁盘上的额外空间进行临时存储,而无需考虑清理使用的临时空间的操作.
正如其他人所说,你可以使用O(n)计数排序.但是,您还需要考虑一些其他问题.我们假设你存储32位整数,所以100GB~27e9整数.
如果所有整数都相同,那么它将发生~27e9次,这大于32位int.因此,您的计数器必须是64位整数.
使用2GB RAM,您一次只能在RAM中存储~125e6计数器.如果我们不能对整数的分布做出任何假设,我们要么必须:
我认为后一种选择更好.由于我们需要~4e9 64位计数器并且只能存储2GB,我们需要遍历整个阵列~16次.如果我们考虑遇到一个整数序列,如0,1 << 31,0,那么第一个选项显然没有用.这些计数器不会同时存储在RAM中,因此至少需要2次HD写入.
因此,我认为对于问题的具体大小(100GB),N路合并排序会更好,因为这只需要读取整个数组log_2(100)~8次.
但是,如果面试官立即将问题改为"10TB阵列,仍然是2GB的RAM",那么计数排序很容易获胜.
由于要排序的数据是整数类型（4 个字节）并且数据量是 100 GB（其中 GB 是 2^30），您将有 26,843,545,600 个整数要排序。由于您有 4,294,967,296 个可能的整数值，您可以将此数据表示为用作计数器的 long 数组，这将消耗大约 34 GB 的磁盘空间。读取 100 GB 数据一次，为每个可能的整数值递增各个计数器（300 GB 总磁盘访问读取值、读取计数器、写入递增计数器），然后按顺序读取计数器，写出数字您读取的每个值的值（134 GB 总磁盘访问）。
这将使用总共 434 GB 的磁盘访问对数据进行排序。如果您使用 RAM 来存储整数值计数器范围的一部分，则从技术上讲，您可以进一步降低磁盘访问量。