如何优化跳转表的大小？

考虑一个类似C语言的典型枚举类型：

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

有关于enum foo类型的值的switch语句，可能无法处理某些枚举值：

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
};

这是两个交换语句：

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个数据字作为跳转表。

---

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

已经在解决MinLA方面进行了一些研究，无论是精确还是近似。 有一个Theta（2 ^ nm）时间动态节目（Koren - Harel 2002），看起来很普遍。 在线性规划松弛方面有很多工作要做，以获得有保证的近似值并用于分支定界。 不幸的是，这些放松似乎都太大，不适合解决者直接消费。 可能有人尝试过编程，但我的粗略搜索没有任何结果。 有很多启发式方法，包括由Juvan和Mohar（1992）提出的以下可爱创意：根据拉普拉斯的第二个特征向量对标签进行排序。

只有50个标签，如果可以找到可证明的最佳安排，我不会感到惊讶，但是如果它不需要对感兴趣的实例进行几轮新颖的算法设计，实现和实验，我会感到惊讶。 如果你想学习一些涉及的技术，我会推荐Pascal van Hentenryck在Coursera上的离散优化课程（我从他和布朗大学合作的时候开始阅读早期版本）。

---

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

如果你将每个开关当作一个集合，那么所有集合（即开关）的交集都可以先集合起来。

有以下枚举：

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

而这两个开关语句：

枚举示例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的配置）。

链接地址: http://www.djcxy.com/p/15633.html

上一篇: How to optimize the size of jump tables?

下一篇: Fi C++