问覆盖内存范围的算法？

EN

这可以被表述为Shortest path problem的变体。

我们需要用最多N个页覆盖一组总长度为M的范围。页面可能有不同长度的L，它们没有对齐(可以放在任何地址)。页面的总“额外”区域和总长度之间的差值等于常数M，它允许最小化页面的总长度。

让我们构造一个与这个问题相关的图。任何范围内的每个内存地址在图中都有相应的顶点。每个顶点都有L传出边，对应于L页，从给定地址开始。每条边的长度等于页面长度。每条边都会到达图中的某个顶点，具体取决于对应页面的结束位置：

1. 页在某个未占用的位置结束。边到达顶点，对应于此position.
2. Page在某个范围内结束后第一个范围的起始地址。边到达顶点，对应于页面的结束地址。
3. 页面在未被占用的位置结束，地址大于任何范围的地址。边到达目标顶点。(第一个范围的起始地址对应于源顶点，我们应该找到这两个顶点之间的最短路径)。

由于所得到的图是DAG，通过以拓扑顺序(或者，更简单地，按照相应存储器地址的顺序)处理顶点，可以在线性时间内找到最短路径。

对于每个顶点，保留一个路径N个指针对的数组{-，back-}。当最短路径算法访问任何顶点时，使用路径中的跳数索引此数组，如果路径比存储的路径长度短，则替换{ path -length，back-pointer}。在处理每个顶点时，在结点对数组中找到属于目的顶点的最短路径，然后使用反向指针重构路径。这条路径描述了最佳覆盖。

最坏情况时间复杂度O(L*M*N)由最大边数(L*M)和阵列中属于每个顶点的元素数(N)确定。如果范围是稀疏的，则大多数边都会到达某个范围的起始地址，对应于内部地址的大多数顶点都是未使用的，并且时间复杂度要小得多。

该算法需要O(M*N)空间，但对于稀疏范围，如果我们将所有图顶点(或可能所有长度/指针对)放入哈希图中，这可能会显着减少。

考虑到您想要覆盖的范围是非常低值的区间(让我们称它们为“范围”)，而间隔(称为“附加”)是非常昂贵的区间。现在我们希望最小化总成本，最多N个间隔(称为“封面”)，它覆盖了所有的“范围”，并可能包含一些“额外的”。下面的算法本质上是贪婪的。

首先取你想要覆盖的所有区间(“范围”)，以及它们之间的“额外”。

1)用从最小到最大的“范围”的大间隔来覆盖它们。

2)迭代并删除其间代价最高的“额外”(即最大跨度)，并将除法计算为创建额外的“覆盖”，直到覆盖的数量变为N或耗尽了代价高昂的“额外”。

自下而上的贪婪方法，当每个长度是最后一个长度的倍数时：

从一组最小长度的区间开始，这些区间最小地覆盖所有范围。迭代合并最长的游程，直到低于最大范围计数。

在您的情况下，在TLB上，您可能有对齐约束，这将使问题变得更加棘手。