Lua的混合数组和哈希表;它存在于其他地方吗?
Lua's implementation of tables keep its elements in two parts: an array part and a hash part.
Does such a thing exist in any other languages?
Take a look at section 4, Tables, in The Implementation of Lua 5.0.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
这个想法是 Roberto Ierusalimschy 和 Lua 团队其他成员的原创。我在 2003 年的麻省理工学院轻量级语言研讨会上听到 Roberto 做了关于这个问题的演讲,在这次演讲中,他讨论了之前的工作,并令人信服地认为这个想法是新的。我不知道此后其他语言是否复制了它。
最初的 Awk 的语言模型比 Lua 的限制更严格;数字或字符串都可以用作数组中的键,但数组本身不是一流的值:数组必须有名称,并且数组不能用作数组中的键。
关于实现,我检查了Brian Kernighan维护的原始Awk的来源,并且Awk的实现使用哈希表,而不是Lua的混合数组/表结构。这种区别很重要,因为在 Lua 中,当表与连续整数键一起使用时,空间开销与 C 数组相同。对于原始的 Awk 来说,情况并非如此。
我没有费心去研究所有后来的 awk 实现,例如 Gnu Awk、mawk 等等。
This idea was original with Roberto Ierusalimschy and the rest of the Lua team. I heard Roberto give a talk about it at the MIT Lightweight Languages workshop in 2003, and in this talk he discussed prior work and argued convincingly that the idea was new. I don't know if other languages have copied it since.
The original Awk has a somewhat more restricted language model than Lua; either a number or a string can be used as a key in an array, but arrays themselves are not first-class values: an array must have a name, and an array cannot be used as a key in the array.
Regarding the implementation, I have checked the sources for the original Awk as maintained by Brian Kernighan, and the implementation of Awk uses a hash table, not Lua's hybrid array/table structure. The distinction is important because in Lua, when a table is used with consecutive integer keys, the space overhead is the same as for a C array. This is not true for original Awk.
I have not bothered to investigate all later implementations of awk, e.g., Gnu Awk, mawk, and so on.
编辑:这并没有回答与实现有关的问题。
AWK 也做到了。
有趣的是,某些语言如何将其他语言中不同的操作合并在一起:
a[10]
a['foo']
a.foo
a('foo')
/a.foo()
非常不完整的示例:
Perl 是罕见的语言其中顺序/关联索引具有单独的语法 -
a[10]
/a{'foo'}
。 AFAIK,对象字段映射到其他操作之一,具体取决于类的实现者想要使用的操作。在 Python 中,这 4 个都是不同的;顺序/关联索引使用相同的语法,但单独的数据类型针对它们进行了优化。
在 Ruby 中,对象字段是不带参数的方法 -
a.foo
。在 JavaScript 中,对象字段
a.foo
是关联索引a['foo']
的语法糖。在 Lua 和 AWK 中,关联数组也用于顺序索引 -
a[10]
。在 Arc 中,顺序索引和关联索引看起来像函数调用 -
(a 10)
/(a "foo")
,我认为a.foo
也是这个的语法糖(?)。EDIT: This doesn't answer the question, which was about the implementation.
AWK also did it.
It's interesing how some languages conflate operations that are different in others:
a[10]
a['foo']
a.foo
a('foo')
/a.foo()
Very incomplete examples:
Perl is the rare language where sequential/associative indexing have separate syntax -
a[10]
/a{'foo'}
. AFAIK, object fields map to one of the other operations, depending on which the implementor of the class felt like using.In Python, all 4 are distinct; sequential/associative indexing use same syntax but separate data types are optimized for them.
In Ruby, object fields are methods with no arguments -
a.foo
.In JavaScript, object fields
a.foo
are syntax sugar for associative indexinga['foo']
.In Lua and AWK, associative arrays are also used for sequential indexing -
a[10]
.In Arc, sequential and associative indexing looks like function calls -
(a 10)
/(a "foo")
, and I thinka.foo
is syntax sugar for this too(?).我能想到的最接近的是 Javascript - 您使用 new Array() 创建一个数组,然后继续按数字或字符串值进行索引。出于性能原因,某些 Javascript 实现很可能选择使用两个数组来执行此操作,原因请参阅您链接到的 Lua 文档中所述。
The closest thing I can think of is Javascript - you create an array with
new Array()
, and then proceed to index either by number or by string value. It could well be for performance reasons some Javascript implementations choose to do so using two arrays, for the reasons noted in the Lua documentation you linked to.ArrayWithHash 是 C++ 中数组哈希表混合的快速实现。
由于 C++ 是静态类型语言,因此 ArrayWithHash 中只允许使用整数键(无法插入字符串或指针键)。换句话说,它类似于一个带有大索引哈希表备份的数组。它还使用不同的哈希表实现,其内存效率低于 Lua 表实现。
ArrayWithHash is a fast implementation of array-hashtable hybrid in C++.
Since C++ is a statically typed language, only integer keys are allowed in ArrayWithHash (no way to insert string or pointer key). In other words, it is something like an array with hash table backup for large indices. Also it uses different hash table implementation which is less memory-efficient than Lua table implementation.