python - C中的高效数组查找

Question

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

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

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

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

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

Answer 1

How does Python or Ruby or Go store and retrieve variables efficiently?

Python 和 Ruby 使用 hash-tables :变量的名称被翻译成一个整数，并且该整数用作数组的索引。几个名称总是会发生冲突(转换为相同的整数)，因此需要通过允许在同一插槽中从名称到值的多个绑定(bind)来考虑这一点，但每个名称只会检查几个。

Go 是经过编译的，因此变量在编译时被转换为地址(静态地址或相对于堆栈或帧指针的偏移量)。

what is an efficient way of creating a variable sized array?

如果您决定这样做，您将使用 malloc 和 realloc。

在调整哈希表的桶数组大小的情况下，realloc 不幸的是没有用，因为旧桶数组中的所有键都需要一个一个地重新哈希以找到他们在新数组中的位置。如果您知道将由您的解释器解释的程序的最大大小，您可以直接以适用于最大程序的大小分配哈希表，并避免编写哈希表大小调整函数。