3

我正在实现一个 VM 编译器，自然而然地，我已经到了实现开关的地步。同样自然地，对于短开关，顺序查找数组将是最佳的，但更大的开关呢？

到目前为止，我已经想出了一个数据结构，它给了我一个很好的查找时间。我不知道该结构的名称，但它类似于二叉树但整体结构，不同之处在于它仅适用于一组静态整数，不能添加或删除。它看起来像一个表格，其中值从顶部和右侧增加，这是一个示例：

整数 -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

这给了我最坏的情况width + height迭代。假设情况是37，-65小于37，所以向右移动，3向右移动，32向右移动，54更大所以向下移动（步宽，因为它是无论如何顺序数组），45 更大所以向下移动，38 更大所以向下移动，我们在 7 跳中有 37 个。

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

另外，这种安排有名称吗？我自己想出了它，但很可能有人在我之前做过，所以它很可能已经被命名了。

编辑：好的，据我所知，“完美的哈希”将为我提供更好的理论性能。但这将如何在现实生活中发挥作用？如果我理解正确，两级“完美哈希”将被分散而不是连续的内存块，因此虽然理论上的复杂性较低，但在获取该内存之前可能会有数十个甚至数百个周期的潜在损失。相比之下，理论上较慢的最坏情况实际上会表现得更好，因为它比完美的哈希更缓存友好......或者不是？

4

2 回答 2

2

在多种备选方案之间实施切换时，您有多种选择：

  • 制作几组平面查找数组。例如，如果您看到 numbers 1, 2, 3, 20000, 20001, 20002，您可以执行一次单次if以将您带到 1-s 或 20,000-s，然后使用两个平面查找数组。
  • 发现一种模式。例如，如果您看到 numbers 100, 200, 300, 400, 500, 600，将数字除以100，然后使用平面查找数组。
  • 制作一个哈希表。由于您知道要散列的所有数字，因此您可以使用表的负载因子来确保查找不会进行大量探测。

您的算法类似于二进制搜索，因为它来自“分而治之”系列。此类算法具有对数时间复杂度，这对于交换机来说可能是不可接受的，因为它们预计为O(1).

于 2013-08-20T13:25:26.900 回答
0

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

二分查找更快。

二分查找在 log2(w*h) = log2(w) + log2(h) 中完成。

您的算法在 w+h 内完成。

于 2013-08-20T13:25:14.340 回答