7

考虑类似 C 语言中的典型枚举类型，如下所示：

enum foo {
    FOO_A,
    FOO_B,
    FOO_C,
    /* ... */
    FOO_N
};

对 type 的值有 switch 语句enum foo，可能不处理某些枚举值：

enum foo bar;
/* ... */
switch (bar) {
case FOO_A: /* ... */
case FOO_B: /* ... */
case FOO_D: /* ... */
case FOO_L: /* ... */
default: /* ... */
}

现在，为了处理足够多的枚举值，编译器将使用大小为(<highesthandled value> - <lowesthandled value> + 1) * sizeof(void*)的跳转表来实现 switch 语句。

考虑一下我有多个已知使用跳转表的这样的 switch 语句，因为每个语句都知道哪些值正在被处理，哪些值没有被处理。如何enum foo以某种方式重新排序值，以使生成的所有跳转表的总大小最小？

例子

这是一个稍微简化的示例，它假设编译器为所有 switch 语句生成跳转表。这是枚举：

enum example {
    EX_A,
    EX_B,
    EX_C,
    EX_D
};

这些是两个开关语句：

enum example a, b;

switch (a) {
case EX_A: /* ... */
case EX_C: /* ... */
default: /* ... */
}

switch (b) {
case EX_B: /* ... */
case EX_D: /* ... */
default: /* ... */
}

对于此示例，编译器将生成两个跳转表，每个表包含三个条目（在第一种情况下 from EX_Ato EX_C，在第二种情况下 from EX_Bto EX_D），总计 6 个用于跳转表的机器字。如果我确实像这样重新排序枚举：

enum example {
    EX_A,
    EX_C,
    EX_B,
    EX_D
};

跳转表只需要 4 个数据字。

4

2 回答 2

4

这个问题是 NP-hard，因为它将最小线性排列问题 (MinLA) 从图推广到超图，并且 MinLA 是 NP-hard (Garey--Johnson--Stockmeyer 1976)。

已经对求解 MinLA 进行了一些研究，包括精确和近似。有一个 Theta(2^nm) 时间动态程序 (Koren--Harel 2002) 看起来可以推广。在线性规划松弛方面有很多工作，既可以获得有保证的近似值，也可以用于分支定界。不幸的是，这些松弛对于求解器的直接消耗来说似乎都太大了。可能有人尝试过约束编程，但我粗略的搜索一无所获。有许多启发式方法，包括 Juvan 和 Mohar (1992) 提出的以下可爱想法：根据拉普拉斯算子的第二个特征向量对标签进行排序。

只有 50 个标签，如果可以找到可证明的最优安排，我不会感到惊讶，但如果不需要对感兴趣的实例进行几轮新颖的算法设计、实现和实验，我会感到惊讶. 如果你想学习其中的一些技术，我会推荐 Pascal van Hentenryck 在 Coursera 上的离散优化课程（我在他隶属于布朗大学时学习了早期版本）。

于 2013-09-02T21:30:47.853 回答
-1

一种解决方案（可能有更快的解决方案）。是通过做部分蛮力。

如果您将每个开关视为一个集合，则所有集合（即开关）的交集可能首先被捆绑。

具有以下枚举：

enum example {
    EX_A,
    EX_B,
    EX_C,
    EX_D,
    EX_E
};

而这两个 switch 语句：

枚举示例 a, b;

switch (a) {
case EX_A: /* ... */
case EX_C: /* ... */
case EX_E: /* ... */
default: /* ... */
}

switch (b) {
case EX_B: /* ... */
case EX_D: /* ... */
case EX_E: /* ... */
default: /* ... */
}

路口是：

{ EX_E }

其余元素是：

{ EX_A, EX_B, EX_C, EX_D }

所以你可以把交集放在第一位，然后遍历其余的所有排列，生成所有的跳转表，看看哪个是较小的。这是n！（在此示例中，您必须查看 4！= 24 个配置）。

于 2013-09-02T18:15:47.430 回答