在一个旋转的磁盘上,我有 N 条记录要排列。在 RAM 中,我有一个包含 N 个索引的数组,其中包含所需的排列。我也有足够的 RAM 一次保存 n 条记录。考虑到顺序磁盘访问要快得多这一事实,我可以使用什么算法尽快在磁盘上执行排列?
如果需要,我有足够的磁盘空间用于中间文件。
最佳答案
这是一个已知问题。在您的排列顺序中找到循环。例如,给定五个要排列 [1, 0, 3, 4, 2] 的记录,您有循环 (0, 1) 和 (2, 3, 4)。您可以通过选择一个未使用的起始位置来做到这一点;跟随索引指针,直到返回起点。指针序列描述了一个循环。
然后您用一个内部临时变量排列记录,一个记录长。
temp = disk[0]
disk[0] = disk[1]
disk[1] = temp
temp = disk[2]
disk[2] = disk[3]
disk[3] = disk[4]
disk[4] = temp
请注意,您还可以在遍历指针时执行排列。您还需要一些方法来调用哪些位置已经排列,例如清除排列索引(将其设置为 -1)。
你能看出如何概括吗?
关于algorithm - 置换外部存储器的实用算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55938368/