跳转表开关外壳的问题 [英] Jump Table Switch Case question

问题描述

我想了解有关跳转表和它的一个开关case语句之间关系的一些东西。

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

有人告诉我，跳转表是O（1）结构，编译器生成，这使得价值本质上查找关于一样快，你可以​​得到的。然而，在某些情况下，一个Hashtable /词典可能更快。我也告诉本报，如果在开关盒中包含订购数据值才有效。

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.

推荐答案

A 跳表是用于传输控制到另一个位置的抽象结构。后藤，继续和断裂是相似的，只是它们总是从多传送到一个​​特定的位置，而不是一个可能性。特别是，该控制流程是不一样的一个函数调用。 （维基百科上关于有关分支表的文章。）

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.)

A 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.

然而，跳转表的全部功能通常不要求，如当每一个案件都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.

---

实际实现中采取不同的形式，在键索引映射是如何完成的主要不同。这映射就是诸如字典和哈希表进来，这些技术可以独立的跳转表中。说有些code使用跳转表本身并不意味着你有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语句的查找方法，并且也不能保证你会得到一个特定的实施;然而，编译器的选项，如优化换速度和优化换大小应加以考虑。

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屋！