« pvp 游戏如何解决玩家匹配等待时间过长的问题 | 返回首页 | Shop Heroes 的经济系统 »

Lua 稀疏数组

Lua 的 table 可以做数组用,但是前提是数组里不能有空洞。也就是不能在数组里保存 nil ,否则取长度和迭代的行为都是不确定的。

能不能用比较小的额外代价在 Lua 中实现一个支持空洞的数组呢?

首先,我们定义一下,带空洞的 array 的正确行为应该是怎样的:

  1. 数组只能用正整数做 key ,设置其它 key 会抛出 error 。

  2. 可以用 pairs 迭代数组,和普通的 table 一样,迭代器会跳过那些值为 nil 的键值对。但要求迭代器一定从 1 开始从小到大按次序迭代。

  3. 用取长度 (#) 操作符,可以正确的返回数组的大小,即最大一个正整数 key 。

  4. ipairs 的行为不变,会在第一个 nil 处停下来。


我想,可以依旧用 table 来充当数组,而只需要重定义这个数组对象的 __newindex __pairs__len 三个元方法就可以了。

我们可以认为,在触发 __newindex 时,如果 key 在 lua_rawlen 返回的范围内,那么新的值还是保存在 table 的 array part 的,不用特别干预。

而如果在 hash part, 可以额外把这个 key 记录下来,我想以负数为下标就可以了。

每当 pairs 迭代前,或是取 # 长度前,我们可以对稀疏部分,哪些负数下标记录的额外 key 做一次排序去重整理。之后的运算复杂度就可以控制在 log(n) 内。

实现的代码见 github 上的仓库

Comments

别老折腾lua,好多年前,说好的3D引擎呢。

你的博客非常不错哦,我的个人网站 http://www.javaxxz.com 相互学习下。

你的博客非常不错哦,我的个人网站 http://www.javaxxz.com 相互学习下。

叹为观止。风魂 简直神

Post a comment

非这个主题相关的留言请到:留言本