C 中的高效数组查找

Question

我正在尝试为 C 中的自定义语言编写一个简单的语言解释器。由于 C 的简单性，我想使用 C 而不是 C++。

我不确定如何在 C 中做的事情是存储变量和变量查找。

我打算将变量存储在一个数组中，但我想我需要一个可变大小的数组。

除了循环遍历数组之外，我也不知道从数组中查找变量的有效方法。

所以我想知道，创建可变大小数组的有效方法是什么？Python 或 Ruby 或 Go 如何有效地存储和检索变量？

Answer 1

Python 或 Ruby 或 Go 如何有效地存储和检索变量？Python 和 Ruby 使用哈希表：变量的名称被转换为一个整数，并且该整数被用作数组的索引。总是可能发生多个名称冲突（转换为相同的整数），因此需要通过允许在同一插槽中从名称到值的多个绑定来考虑这一点，但每个名称只会检查几个。Go 被编译，因此变量在编译时被转换为地址（静态或相对于堆栈或帧指针的偏移量）。创建可变大小数组的有效方法是什么？如果您决定这样做，您将使用malloc和realloc。在调整哈希表的桶数组大小的情况下，realloc不幸的是没有用，因为旧桶数组中的所有键都需要一一重新散列以找到它们在新数组中的位置。如果您知道解释器将解释的程序的最大大小，则可以直接以适用于最大程序的大小分配哈希表，并避免编写哈希表大小调整函数。

Answer 2

我认为当您尝试自己实现变量存储时，您可能真的会忘乎所以。我建议您使用像uthash这样的现有哈希映射，只是为了从概念上了解它是如何工作的，并尽可能好地封装它。如果结果证明是瓶颈，您可以稍后再回来进行优化。我有点自信地说，那个时候，你不会选择一个动态扩展的数组。您必须考虑到您需要实现基于字符串的搜索以按名称查找变量，因此您将很难比具有动态扩展数组的哈希图做得更好。如果未排序，则对其进行搜索将是 O(n)，如果已排序，则为 O(log n)，而哈希图的搜索复杂度为 O(1)。