论文标题
分析LUA混合表的数学模型以及为什么需要修复
Mathematical Models to Analyze Lua Hybrid Tables and Why They Need a Fix
论文作者
论文摘要
Lua（Ierusalimschy等，1996）是一种著名的脚本语言，在许多程序员中很受欢迎，最著名的是游戏行业。值得注意的是，LUA中唯一的数据结构机制是称为表的关联阵列。使用LUA 5.0，LUA的参考实现引入了混合表，以同时使用hashmap和动态增长的数组组合在一起实现表：与整数密钥相关的值将存储在数组部分中，如果合适，其他所有内容都存储在Hashmap中。所有这些都是对用户透明的，用户将获得一个独特的简单接口来处理表。在本文中，我们通过考虑各种最坏情况和概率的场景，对LUA表格的性能进行理论分析。特别是，我们发现了简单概率模型的一些有问题的情况，在该模型中，我们添加了一个带有固定概率$ p> \ frac12 $的新键，并删除带有概率$ 1-p $的键：执行此类操作的成本被证明是$ω（t \ log t \ log t）$，具有很高的概率，预计是线性复杂性的。
Lua (Ierusalimschy et al., 1996) is a well-known scripting language, popular among many programmers, most notably in the gaming industry. Remarkably, the only data-structuring mechanism in Lua are associative arrays, called tables. With Lua 5.0, the reference implementation of Lua introduced hybrid tables to implement tables using both a hashmap and a dynamically growing array combined together: the values associated with integer keys are stored in the array part, when suitable, everything else is stored in the hashmap. All this is transparent to the user, who gets a unique simple interface to handle tables. In this paper we carry out a theoretical analysis of the performance of Lua's tables, by considering various worst-case and probabilistic scenarios. In particular, we uncover some problematic situations for the simple probabilistic model where we add a new key with some fixed probability $p>\frac12$ and delete a key with probability $1-p$: the cost of performing T such operations is proved to be $Ω(T\log T)$ with high probability, where linear complexity is expected instead.
