6

我有一组范围，例如 {(2-8)、(13-22)、(380-7931)、(40032-63278)}。为了简单起见，我们可以假设它们不重叠（重叠范围已经合并）。

我的目标是使用一组给定的“长度”组合来“覆盖”这些范围，例如 {4、64、1024、16384}。我最多只能使用 N 个长度，例如 N=32。我不在乎我使用了多少“长度”，只要我低于我的最大值，但我想最小化总“额外”区域 - 由不在初始范围集中的长度“覆盖”的数字。

由 (2-66) 覆盖的示例 {(2-8)}（使用长度为 64）有 58 个“额外”数字。{(2-6), (6-10)} 覆盖的 {(2-8)} （两个长度为 4）只有 2 个“额外”数字并且是可取的。

我的真实世界应用程序涉及对固定的 MMU TLB 进行预编程，以确保只能访问特定范围的内存地址（TLB 未命中因此表示禁止访问并且可以相应地处理）。我想尽可能紧密地覆盖范围，以便尽早发现违规行为，但我只有 32 个插槽和 4 个固定页面大小。我可以手动将我的代码调整到足够的性能水平，但我很好奇是否有更优雅/通用的解决方案来解决这个问题。它似乎与背包问题有关，但不同的是很难搜索。

4

3 回答 3

1

这可以表述为最短路径问题的变体。

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

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

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

由于生成的图是DAG，因此可以在线性时间内找到最短路径，方法是按照拓扑顺序（或者更简单，按照相应内存地址的顺序）处理顶点。

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

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

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

于 2012-09-24T18:40:28.297 回答
0

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

首先获取您想要覆盖的所有间隔（“范围”）以及它们之间的“额外”。

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

2) 迭代并删除其间最昂贵的“额外”（即最大跨度），并将划分计算为创建额外的“覆盖”，直到覆盖的数量变为 N 或您用完昂贵的“额外”。

于 2012-09-24T16:08:55.947 回答
0

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

从一组最少覆盖所有范围的最小长度间隔开始。迭代合并最长的运行，直到低于最大范围计数。

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

于 2012-09-24T16:15:03.947 回答