如何优化跳转表的大小？

Question

考虑一种类似C语言的典型枚举类型,如下所示:

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

有关于类型值的switch语句enum foo,可能不处理某些枚举值:

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

现在,为了处理足够多的枚举值,编译器将使用具有大小(<最高处理值> - <最小处理值> + 1)*sizeof(void*)的跳转表来实现switch语句.

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

例

这是一个略微简化的示例,假设编译器为所有switch语句生成跳转表.这是枚举:

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

这些是两个switch语句:

enum example a, b;

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

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

对于此示例,编译器会生成(从在第一种情况下,每个三个条目两个跳表EX_A到EX_C,在从第二壳体EX_B到EX_D),达总共用于跳转表6机器字.如果我像这样重新排序枚举:

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

跳转表我只需要4个数据字.

Answer 1

这个问题是 NP 困难的，因为它将最小线性排列问题（MinLA）从图推广到超图，而 MinLA 是 NP 困难的（Garey--Johnson-Stockmeyer 1976）。

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

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