algorithm – 从硬盘中排序巨大的整数

给定硬盘上的100 GB整数数据,RAM为2 GB,如何使用最少的磁盘操作对整数进行排序.这里从磁盘中获取一个数字被视为一个磁盘操作(尽管实际上可以获取一个数据块).

我们可以使用磁盘上的额外空间进行临时存储,而无需考虑清理使用的临时空间的操作.

正如其他人所说,您可以使用O(n) counting sort.但是您还需要考虑其他一些问题.我们假设你存储了32位整数,所以100GB~27e9整数.

如果所有整数都相同,那么它将发生~27e9次,这大于32位int.因此,您的计数器必须是64位整数.

使用2GB的RAM,您一次只能在RAM中存储~125e6计数器.如果我们不能对整数的分布做出任何假设,我们要么必须:

>单独增加HD上的计数器,或
>忽略我们遇到的所有不在我们当前存储在RAM中的计数器数组中的整数.

我认为后一种选择更好.由于我们需要~4e9 64位计数器并且只能存储2GB,我们需要遍历整个阵列~16次.如果我们考虑遇到诸如0,1 << 31,0的整数序列,则第一种选择显然是不好的.这些计数器不会同时存储在RAM中,因此至少需要2次HD写入. 因此,我认为对于问题的具体大小(100GB),N-way merge排序会更好,因为这只需要读取整个数组log_2(100)~8次.

但是,如果面试官立即将问题改为“10TB阵列,仍然是2GB内存”,则计数排序很容易获胜.

相关文章
相关标签/搜索