跳表切换案例问题

Question

我试图了解跳转表及其在switch case语句之间的关系.

我被告知跳转表是编译器生成的O(1)结构,它使得查找值基本上与您可以获得的速度一样快.但是在某些情况下,Hashtable/Dictionary可能会更快.我还被告知这只有在开关盒包含ordered数据值时才有效.

有人可以确认或否认这一点并解释跳转表是什么,它的重要性和时间复杂性与使用字典或散列表相比.谢谢.

Answer 1

甲跳转表是用于将一个抽象结构控制转移到另一个位置.转到,继续和中断是相似的,除了它们总是转移到特定位置而不是许多可能性.特别是,该控制流程与函数调用不同.(维基百科关于分支表的文章是相关的.)

一个switch语句是怎么写的跳转表在C/C++.在这种常见情况下,仅提供有限形式(只能打开整数类型)以使实现更容易和更快.(对于整数类型而言,如何有效地实现跳转表的研究比一般情况要多得多.)一个典型的例子是Duff的Device.

但是,通常不需要跳转表的完整功能,例如每个case都有break语句.这些"有限的跳转表"是一种不同的模式,它只利用跳转表的良好研究效率,并且在每个"动作"独立于其他动作时是常见的.

跳转表的实际实现采用不同的形式,主要是索引映射的键的完成方式不同.该映射是"字典"和"哈希表"之类的术语,而这些技术可以独立于跳转表使用.说一些代码"使用跳转表"并不意味着你有O(1)查找.

编译器可以自由地为每个switch语句选择查找方法,并且不能保证你会获得一个特定的实现; 但是,应该考虑编译器选项,例如优化速度和优化尺寸.

您应该研究数据结构,以了解它们所施加的不同复杂性要求.简而言之,如果"字典"是指平衡的二叉树,则它是O(log n); 哈希表取决于其哈希函数和冲突策略.在switch语句的特定情况下,由于编译器具有完整信息,因此它可以生成完美的散列函数,这意味着O(1)查找.但是,不要仅仅考虑整体算法的复杂性而迷失方向:它隐藏了重要的因素.

Answer 2

跳转表基本上是一个指向代码段的指针数组，用于处理 switch 语句中的各种情况。它最有可能在您的案例密集时生成（即您有一个范围内每个可能值的案例）。例如，给定如下语句：

switch (i) {
   case 1: printf("case 1"); break;
   case 2: printf("case 2"); break;
   case 3: printf("case 3"); break;
}

它可以生成大致相当于这样的代码：

void case1() { printf("case 1"); }
void case2() { printf("case 2"); }
void case3() { printf("case 3"); }

typedef void (*pfunc)(void);

pfunc functions[3] = {case1, case2, case3};

if ((unsigned)i<3)    
    functions[i]();

这具有 O(K) 复杂度。一个典型的哈希表也有大约 O(K) 的预期复杂度，尽管最坏的情况通常是 O(N)。跳转表通常会更快，但通常只有在表非常密集的情况下才会使用它，而哈希表/字典即使在案例非常稀疏的情况下也能很好地工作。