用于置换外部存储器的实用算法

Question

在旋转的磁盘上，我有N个记录，我想要置换。在RAM中，我有一个包含所需排列的N个索引数组。我也有足够的RAM来一次保存n条记录。我可以使用什么算法尽快执行磁盘上的排列，同时考虑到顺序磁盘访问速度要快得多？

如果需要，我有足够的多余磁盘用于中间文件。

Answer 1

这是一个已知问题。查找排列顺序中的循环。例如，给定5个记录来置换[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）。

你能看出如何概括吗？

Answer 2

这是间隔协调的问题。我将通过改变M记录的可用内存来略微简化符号 - 大写和小写的N有点令人困惑。

首先，我们将排列重新转换为一系列间隔，即记录需要驻留在RAM中的旋转跨度。如果需要将记录写入编号较低的位置，我们会按列表大小增加端点，以指示环绕 - 必须等待下一个磁盘旋转。例如，使用我之前的示例，我们扩展了列表：

[1, 0, 3, 4, 2]
0 -> 1
1 -> 0+5
2 -> 3
3 -> 4
4 -> 2+5

现在，我们应用标准的贪婪调度解决方案。首先，按端点排序：

[0, 1]
[2, 3]
[3, 4]
[1, 5]
[4, 7]

现在，将算法应用于M-1“lanes”;交换空间需要额外的一个。我们填充每个通道，将该区间附加到最早的终点，其起点不重叠：

[0, 1]   [2, 3]   [3, 4]   [4, 7]
[1, 5]

如果M> = 3，我们可以在总共7个“刻度”中执行此操作。如果M = 2，我们将第二个车道推迟2转到[11,15]。

---

Sneftal的好例子给我们带来了更多麻烦，更深层次的重叠：

[0, 4]
[1, 5]
[2, 6]
[3, 7]
[4, 0+8]
[5, 1+8]
[6, 2+8]
[7, 3+8]

这需要4个“通道”（如果可用），如果M <5，则根据需要推迟通道。

---

病理情况是需要将排列中的每个记录复制回一个位置，例如[3,0,1,2]，其中M = 2。

[0, 3]
[1, 4]
[2, 5]
[3, 6]

在这种情况下，我们多次遍历延迟循环。在每次旋转结束时，我们必须将所有剩余间隔推迟一次，从而产生

[0, 3]   [3, 6]   [2+4, 5+4]   [1+4+4, 4+4+4]

这会让你感动吗，还是需要更多细节？

Answer 3

我有一个想法，可能需要进一步改进。但它在这里：

假设hdd具有以下结构：

5 4 1 2 3

我们想写出这个排列：

2 3 5 1 4

由于hdd是一个循环缓冲区，并且假设它只能在一个方向上旋转，我们可以使用shift来编写上面的排列：

5 >> 2
4 >> 3
1 >> 1
2 >> 2
3 >> 2

所以让我们把它放在一个数组中，因为我们知道它是一个圆形数组，让我们把它的镜子放在一起：

| 2 3 1 2 2 | 2 3 1 2 2| 2 3 1 2 2 | 2 3 1 2 2 |... Inf

由于我们希望顺序读取（或写入），我们可以将成本函数放到上面的系列中。让成本函数是线性的，即E：

0 1 2 3 4 5 6 7 8 9 10 ... Inf

现在，让我们将成本函数添加到上面的系列中，但是如何选择起点呢？

我们的想法是选择起始点，以便获得最大的一致单调递增序列。

例如，如果你选择0点为“3”，你就会得到

(1)    | - 3 2 4 5 | 6 8 7 9 10 | ...

如果您选择0点为“2”，恰好是“1”，您将得到：

(2)    | - - - 2 3 | 4 6 5 7 8 | ...

由于我们试图支持连续读取，因此我们将读写函数定义为：

F（）：

• 在任何当前指向的hdd位置，函数将读取当前指向的hdd文件到可用的RAM中。 （即总空间 - 1，因为我们想保存1换掉）
• 如果RAM上没有剩余可用空间用于读取，则该函数将置位并且程序将停止。
• 在任何当前的hdd位置，如果ram保存我们想要写入该hdd位置的值，则函数将当前文件读入交换空间，将所需值从ram写入hdd，并销毁ram中的值。
• 如果将值放入hdd，函数将检查序列是否完成。如果是，程序将返回成功。

现在，我们应该注意如果以下情况：

shift amount <= n - 1              (n : available memory we can hold)

我们可以使用上面的功能一次遍历硬盘。例如：

current: 4 5 6 7 0 1 2 3
we want: 0 1 2 3 4 5 6 7
n      : 5

我们可以从我们想要的任何地方开始，比如从最初的“4”开始。我们按顺序读了4个项目（n现在有4个项目），我们从0 1 2 3开始放置，（因为n = 5总计，使用4个.1用于交换）。因此总操作是4次连续读取，然后是r-w操作8次。

使用这个类比，很明显，如果我们从等式（1）和（2）中减去“n-1”，那么具有值“<= 0”的位置将更适合初始位置，因为高于零的那些肯定会需要另一个通行证。

所以我们选择eq。 （2）并减去，因为我们说“n = 3”，我们从eq中减去2。 （2）：

(2)    | - - - 0 1 | 2 4 3 5 6 | ...

现在很明显，使用f（），并从0开始，假设n = 3，我们将有一个如下的启动操作：r，r，r-w，r-w，...

那么，我们如何做其余的事情并找到最低成本？我们将放置一个初始最小成本的数组，正好在等式（2）之下。该数组中的位置将表示我们希望f（）执行的位置。

| - - - 0 1 | 2 4 3 5 6 | ...
| - - - 1 1 | 1 1 1 1 1 | ...

第二个数组，1和0的数组告诉程序执行f（）的位置。请注意，如果我们假设这些位置错误，f（）将断言。

在我们开始实际将文件放入hdd之前，我们当然想看看f（）位置是否正确。我们检查是否存在断言，我们将尝试在删除所有断言的同时最小化成本。所以，例如：

(1) 1111000000000000001111
(2) 1111111000000000000000

（1）显然具有较高的成本（2）。所以问题简化了找到1-0阵列。

关于找到最佳阵列的一些想法：

• 最简单的解决方案是写出所有1并将断言转换为0。 （基本上它是一个跳过）。这种方法保证有效。
• 蛮力：写一个如（2）所示的数组并开始向右移动1，按照这样的顺序尝试每个可用的排列： 1111111100000000 1111111010000000 1111110110000000 ...
• 完全随机方法：插入mt1997并开始置换。每当您看到成本急剧下降时，请停止执行并实施硬盘复制粘贴。你不会找到全局最小值，但你会得到一个很好的权衡。
• 遗传算法：对于“移位计数远低于n - 1”的排列，本答案中提供的方法应该（？）提供全局最小和平滑的梯度。这使得人们可以使用遗传算法而不必过多依赖突变。

我在这种方法中发现的一个优点是，由于OP提到这是一个现实生活中的问题，该方法提供了一种简单（更好）的方式来改变成本函数。更容易检测出这样的效果，有很多需要复制的备用小文件而不是单个巨大的文件。或者也许rrwwrrww比rrrrwwww更好？

这有甚么有意义吗？我们将不得不尝试......