问简单的“碎片整理”逻辑，使变化最小化？

EN

编辑：

很明显，我没有很好地解释这个问题，所以让我用例子再试一次。我有一个给定大小的“管道”，信号在给定的偏移量下通过。由于信号在不同的偏移量中，管道会变得支离破碎，因此无法容纳新信号。我想要一个算法，它将告诉我如何安排信号来整理管道；但是实际移动的信号数量最少！举个例子。

假设我有一个16码的管子，它有下面的信号，上面有描述的尺寸和偏移量。

offset 0: A (size of 4; fills slots 0-3)
offset 5: C (size of 2, fills slot 5-6)
offset 8: B (size of 4, fills 8-11)
offset 14: D (size 2, fills 14-15)

Pipe: AAAA_CC_BBBB__DD

在这种情况下，我有一个插槽在偏移4和7，两个在偏移12-13。现在，让我说，我想添加一个4大小的信号到这个管道。现在它没有连续的空间，但我知道如果我整理一下，我就有足够的空间。“显而易见”的解决方案是将所有信号集中在“顶部”，如下所示：

offset 0:  A (size 4, fills 0-3)
offset 4:  B (size 4, fills 4-7)
offset 8:  C (size 2, fills 8-9)
offset 10: D (size 2, fills 10-11)

Pipe: AAAABBBBCCDD____

这给我的新信号留出了12-15个空位。然而，为了做到这一点，我重新定位了3个信号(B)。对于我移动的每一个信号，我都必须将命令发送到硬件，等待一段相当长的时间。

如果我更聪明，我会意识到还有另一种方法。我可以这样重新定位：

offset 0:  A(size 4, fills 0-3)
offset 8:  B(size 4, fills 8-11)
offset 12: C(size 2, fills 12-13)
offset 14: D(size 2, fills 14-15).

Pipe: AAAA____BBBBCCDD

我现在可以把我的新信号装在4-7的偏移中，我只需要重新定位一个信号(B)。这样就节省了硬件调用。

我想知道是否有一个很好的算法来检测这样的位置；在那里，我可以将一个信号“安装”到一个管道上，并且移动的信号最少。脑海中浮现的是一个N！算法；它基本上是为了“生成每一个可能的分布，计算它导致的移动次数”。我在寻求更快的接近。

批准不一定是100%完美的，我主要是希望尽量减少平均情况，只要最坏的情况不是太可怕。我知道，在一个给定的管道上，我永远不会有超过255个信号，所以我可能可以“逃脱”N！听起来很糟糕。我也知道每个信号的大小是2的幂，管的大小也是如此。

此外，是否有任何灵活的算法来放置信号，以尽量减少碎片？

问题已回答；见下文。

我想稍微解释一下这个答案，以便更好地解释碎片整理对任何人阅读的影响；巴迪解释说，我想指出一种更简单的方法来概念化和更详细地解释碎片整理部分，因为这是最初的问题。

我正在解释我的方法，这是一个稍微不同的/简单的方法，但有效地保持了“伙伴”的概念。我不是预计算块或标记它们，这是太多的努力实现和维护。对我来说，与信号的实际放置/删除相比，计算信号去向的CPU成本非常小；因此，我可以通过不预先计算来简化我的逻辑而损失一个微小的、线性的、CPU的数量。因此，这个过程是：

供插入：

所有信号都保持在与信号大小相等的信号边界内，因此信号将在偏移量为零散% signalsize=0的情况下启动。实际上，对于所有的偏移量，我们走过去，找出保持这一边界的间隔。所以，如果我的信号是16口径管道上的4码，我会看到间隔0-4，5-7，8-11，12-15。

对于每个间隔，检查是否该间隔中的所有空格都是空闲的。在简单的情况下，我们有一个没有信号的区间，我们把信号放在那个区间上。重要的是，我们按顺序查看间隔，并将我们的信号放在第一个空闲间隔中，这确保我们在添加信号时打破最小的“块”(使用伙伴项)。这应该与im3l96描述的伙伴方法相同；除非没有块的预计算。

如果没有完全空闲的间隔，我们就得整理。为此，我们找到了信号中最未使用的插槽。如果多个间隔有相同数量的未使用的槽，请选择第一个间隔。然后，我们在这个间隔中找到最大的信号，并递归地为较小的信号调用相同的插入算法(除了将我们选择的插入第一个信号的间隔标记为不可用)。这会将信号转移到其他地方，使之适合。然后，我们在我们选择的间隔中找到下一个最小的信号，然后做同样的事情，直到我们移动所有的信号。最坏的情况是2^n-1信号移动；其中N是潜在信号大小的数目，<=our信号(假设信号是2的倍数，然后是N=log2(signalSize))。

下面是一个例子。*表示递归调用此方法时标记为不可用的时隙(即调用方法希望将其信号放入的时间间隔，因此不希望递归调用尝试将信号放入其中)。

这里有一个简单、简单的例子，我可以想出这个例子，它仍然证明了完全的复杂性。注意:下面的结构将很难创建，但如果有人非常努力地尝试，则可能会导致好友的接近。

FFFFFFFF__AA_B__EEEE_HGGCC_DII_J

有人经过一个大小为8的信号Z

我们选择偏移量8：

defragInsert(z，8码)

effective structure: FFFFFFFF__AA_B__EEEE_HGGCC_DII_J

placing signal in interval: __AA_B__

defragInput(A，尺寸2)

effective structure: FFFFFFFF********EEEE_HGGCC_DII_J
place signal in interval (offset 20)  _H

defragInput(H，size1)

effective structure: FFFFFFFF********EEEE**GGCC_DII_J
place signal between C & D

返回defragInput(H，size1)

effective structure: FFFFFFFF********EEEE__GGCCHDII_J
place H at offset 20 now that it's open

返回defragInput(A，大小2)

有效结构: FFFFFFFF_____B__EEEEAAGGCCHDII_J现在移动B.

defragInput(B，size1)

有效结构:I&J之间的FFFFFFFF****EEEEAAGGCCHDII_J场所B

返回defragInput(B，size1)

有效结构: FFFFFFFF____EEEEAAGGCCHDIIBJ加B

返回defragInsert(z，大小8)

fianl structure: FFFFFFFFzzzzzzzzEEEEAAGGCCHDIIBJ