我在执行虚拟机的编译器，自然，我来实现开关的点。也自然，简称开关，顺序查找数组将是最佳的，但怎么样更大的交换机？

I am implementing a VM compiler, and naturally, I've come to the point of implementing switches. Also naturally, for short switches, a sequential lookup array would be optimal but what about bigger switches?

到目前为止，我想出了一个数据结构，它给了我一个pretty的良好的查找时间。我不知道该结构的名称，但它类似于一个二叉树但整料，用它仅应用于一组静态整数的差，不能添加或移除。它看起来像一个表，其中值增大到顶部和右侧，这里是一个例子：

So far I've come up with a data structure that gives me a pretty good lookup time. I don't know the name of that structure, but it is similar to a binary tree but monolith, with the difference it only applies to a static set of integers, cannot add or remove. It looks like a table, where value increases to the top and the right, here is an example:

整数-89，-82，-72，-68，-65，-48，-5，0，1，3，7，18，27，29，32，37，38，42，45，54 ，76，78，87，89，92

Integers -89, -82, -72, -68, -65, -48, -5, 0, 1, 3, 7, 18, 27, 29, 32, 37, 38, 42, 45, 54, 76, 78, 87, 89, 92

和表：

-65    3   32   54   92
-68    1   29   45   89
-82   -5   18   38   78
-89   -48  7    37   76

这给了我最糟糕的情况下，宽+高迭代。让我们说的情况是37，-65小于37，所以向右移动，同样为3向右移动，同样为32向右移动，54是更大，所以向下移动（步骤的宽度，因为它是一个顺序排列反正），45是更大，所以向下移动，38是更大，所以向下移动，并且有，我们有37 7跳。

Which gives me the worst possible case width + height iterations. Let's say the case is 37, -65 is less than 37, so move to the right, same for 3 move to the right, same for 32 move to the right, 54 is bigger so move down (step a width since it is a sequential array anyway), 45 is bigger so move down, 38 is bigger so move down and there we have 37 in 7 hops.

有没有可能更快的查找算法？

Is there any possible faster lookup algorithm?

此外，有没有对这种安排的名字吗？我想到了它在我自己的，而是别人最有可能有人却在我前面，所以它是最有可能命名了。

Also, is there a name for this kind of arrangement? I came up with it on my own, but most likely someone else did that before me, so it is most probably named already.

编辑：好的，据我知道了，完美哈希将提供我更好的理论性能。但如何将这个打出来在现实生活中？如果我理解正确两级完美哈希将是相当US $ p $垫出来，而不是连续的存储器块，因此，尽管理论上的复杂性较低，有几十个潜在的罚款，如果在此之前没有几百个周期内存是牵强。与此相反，较慢的理论最坏的情况下，实际上有更好的表现，只是因为它是更多的缓存友好的不是完美的哈希...还是不行？

OK, as far as I got it, a "perfect hash" will offer me better THEORETICAL performance. But how will this play out in real life? If I understand correctly a two level "perfect hash" will be rather spread out instead of a continuous block of memory, so while the theoretical complexity is lower, there is a potential penalty of tens if not hundreds of cycles before that memory is fetched. In contrast, a slower theoretical worst case scenario will actually perform better just because it is more cache friendly than a perfect hash... Or not?

推荐答案

在实施方案中的不同组开关，您有几种选择：

When implementing switches among a diverse set of alternatives, you have several options:

请几组平查找数组。例如，如果你看到数字 1，2，3，20000，20001，20002 ，你可以做一个单一的如果带你到1-s或20000-s，然后采用两种平板查找数组。 探索模式。例如，如果你看到数字 100，200，300，400，500，600 ，通过把数 100 ，然后去为一个单位查找数组。 请哈希表。由于所有的，你是哈希是已知的，你的号码，你可以用表的负载因子发挥，以确保查找不会采取了很多探测。 Make several groups of flat lookup arrays. For example, if you see numbers 1, 2, 3, 20000, 20001, 20002, you could do a single if to take you to 1-s or to 20,000-s, and then employ two flat lookup arrays. Discover a pattern. For example, if you see numbers 100, 200, 300, 400, 500, 600, divide the number by 100, and then go for a flat lookup array. Make a hash table. Since all the numbers that you are hashing are known to you, you can play with the load factor of the table to make sure that the lookup is not going to take a lot of probing.

您的算法是类似二进制搜索，在这个意义上，它是从一分治的家庭。这种算法具有对数时间复杂度，这可能是不能接受的开关，因为他们预计将 O（1）。

Your algorithm is similar to binary search, in the sense that it's from the "divide an conquer" family. Such algorithms have logarithmic time complexity, which may not be acceptable for switches, because they are expected to be O(1).