空间换时间是一种常见的编程技巧。我们可以通过记忆函数的执行结果,在后续使用相同参数再次调用该函数时直接返回之前记忆的结果,来加快函数的运行速度。
假如有一个通用服务器,该服务器接收的请求是以字符串形式表示的 Lua
语言代码。每当服务器接收到一个请求时,它就对字符串运行 load
函数,然后再调用编译后的函数。不过,函数 load
的开销很昂贵,而且 发送给服务器的某些命令的出现频率可能很高。这样,与其每次收到一条诸如 "closeconnection()"
这样的常见命令就重复的调用函数 load
,还不如让服务器用一个辅助表记忆所有函数 load
的执行结果。在调用函数 load
时,服务器先在表中检查指定的字符串是否已经被处理过。如果没有,就(且只有在这种情况下)调用函数 load
并将返回值保存到表中。我们可以将这种行为封装为一个新的函数:
local results = {} function mem_loadstring(s) local res = results[s] if res = nil then -- 已有结果吗? res = assert(load(s)) -- 计算新结果 results[s] = res -- 保存结果以便后续重用 end return res end
这种模式节省的开销非常可观。但是,它也可能导致不易察觉的资源浪费。虽然有些命令会重复出现,但也有很多命令可能就出现一次。渐渐地,表 results
会堆积上服务器收到的所有命令及编译结果。在运行了一段足够长的时间后,这种行为会耗尽服务器的内存。
弱引用表为解决这个问题提供了一种简单的方案。如果表 results
具有弱引用的值,那么每个垃圾收集周期都会删除所有那个时刻未使用的编译结果(基本上就是全部):
local results = {} setmetatable(results, {__mode = "v"}) -- 让值称为弱引用的 function mem_loadstring(s) local res = results[s] if res = nil then -- 已有结果吗? res = assert(load(s)) -- 计算新结果 results[s] = res -- 保存结果以便后续重用 end return res end
实际上,因为索引永远是字符串,所以如果愿意的话,我们可以让这个表变成完全弱引用的:
setmetatable(results, {__mode = "kv"})
最终达到的效果是完全一样的。
记忆技术还可以用来确保某类对象的唯一性。例如,假设一个系统用具有三个相同取值范围的字段 red
、 green
和 blue
的表来表示颜色,一个简单的颜色工厂函数每被调用一次就生成一个新颜色:
function createRGB (r, g, b) return {red = r, green = g, blue = b} end
使用记忆技术,我们就可以为相同的颜色复用相同的表。要为每一种颜色创建一个唯一的键,只需要使用分隔符把颜色的索引连接起来即可:
local results = {} setmetatable(results, {__mode = "v"}) function createRGB(r, g, b) local key = string.format("%d-%d-%d", r, g, b) local color = results[key] if color == nil then color = {red = r, green = g, blue = b} results[key] = color end return color end
这种实现的一个有趣的结果是:由于两种同时存在的颜色必定是由同一个表来表示,所以用户可以使用基本的相等运算符比较两种颜色。因为随着时间的迁移垃圾收集器会清理表 results
,所以一种指定的颜色在不同的时间内可能有不同的表来表示。不过,只要一种颜色正在被使用,它就不会从 results
中被移除。因此,一种颜色与一种新颜色相比已经存在了多长时间,这种颜色对应的表也存在了对应长度的时间,也可以被新颜色复用。