跳表开关盒问题 [英] Jump Table Switch Case question

问题描述

我正在尝试了解一些关于跳转表的事情以及它与 switch case 语句之间的关系.

I am trying to understand some things about jump tables and its relationship between a switch case statement.

有人告诉我，跳转表是编译器生成的 O(1) 结构，它使查找值的速度基本上与你能得到的一样快.但是在某些情况下，哈希表/字典可能会更快.我还被告知这仅在 switch case 包含 ordered 数据值时才有效.

I was told that a jump table is a O(1) structure that the compiler generates which makes lookup of values essentially about as fast as you can get. However in some cases a Hashtable/Dictionary might be faster. I was also told this will only work if the switch case contains ordered data values.

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

Can someone please confirm or deny this and explain what a jump table is, it's importance and the time complexity versus using a dictionary or hashtable. Thanks.

推荐答案

跳转表是一种抽象结构，用于将控制权转移到另一个位置.Goto、continue 和 break 是相似的，只是它们总是转移到一个特定的位置，而不是从多个位置中选择一种.特别是，此控制流与函数调用不同.(维基百科关于分支表的文章是相关的.)

A jump table is an abstract structure used to transfer control to another location. Goto, continue, and break are similar, except they always transfer to a specific location instead of one possibility from many. In particular, this control flow is not the same as a function call. (Wikipedia's article on branch tables is related.)

switch 语句是如何在 C/C++ 中编写跳转表.仅提供了一种有限的形式(只能打开整数类型)，以便在这种常见情况下更容易和更快地实现.(对于整数类型，如何有效地实现跳转表的研究比一般情况要多得多.)一个经典的例子是 达夫的装置.

A switch statement is how to write jump tables in C/C++. Only a limited form is provided (can only switch on integral types) to make implementations easier and faster in this common case. (How to implement jump tables efficiently has been studied much more for integral types than for the general case.) A classic example is Duff's Device.

但是，通常不需要跳转表的全部功能，例如当每个 case 都有一个 break 语句时.这些有限跳转表"是一种不同的模式，它只是利用了跳转表经过充分研究的效率，并且在每个动作"独立于其他动作"时很常见.

However, the full capability of a jump table is often not required, such as when every case would have a break statement. These "limited jump tables" are a different pattern, which is only taking advantage of a jump table's well-studied efficiency, and are common when each "action" is independent of the others.

跳转表的实际实现采用不同的形式，主要区别在于如何完成键到索引的映射.该映射是字典"和哈希表"等术语的来源，这些技术可以独立于跳转表使用.说某些代码使用跳转表"本身并不意味着您有 O(1) 查找.

Actual implementations of jump tables take different forms, mostly differing in how the key to index mapping is done. That mapping is where terms like "dictionary" and "hash table" come in, and those techniques can be used independently of a jump table. Saying that some code "uses a jump table" doesn't imply by itself that you have O(1) lookup.

编译器可以自由选择每个 switch 语句的查找方法，并且不能保证你会得到一个特定的实现；但是，应该考虑诸如 optimize-for-speed 和 optimize-for-size 之类的编译器选项.

The compiler is free to choose the lookup method for each switch statement, and there is no guarantee you'll get one particular implementation; however, compiler options such as optimize-for-speed and optimize-for-size should be taken into account.

您应该研究数据结构以掌握它们所施加的不同复杂性要求.简而言之，如果字典"是指平衡二叉树，那么它是 O(log n);一个哈希表取决于它的哈希函数和碰撞策略.在switch语句的特殊情况下，由于编译器有完整的信息，它可以生成一个完美的哈希函数 这意味着 O(1) 查找.但是，不要只看整体算法复杂性就迷失了:它隐藏了重要因素.

You should look into studying data structures to get a handle on the different complexity requirements imposed by them. Briefly, if by "dictionary" you mean a balanced binary tree, then it is O(log n); and a hash table depends on its hash function and collision strategy. In the particular case of switch statements, since the compiler has full information, it can generate a perfect hash function which means O(1) lookup. However, don't get lost by just looking at overall algorithmic complexity: it hides important factors.

这篇关于跳表开关盒问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！