用Lua实现插入、删除和查找时间复杂度为O(1)的集合

利用下面代码可以定义一个集合S，对该集合所有的操作，比如插入、删除元素和查找元素都是O(1)，代码如下：

function newset()

local reverse = {} --以数据为key，数据在set中的位置为value

local set = {} --一个数组，其中的value就是要管理的数据

return setmetatable(set,{__index = {

insert = function(set,value)

if not reverse[value] then

table.insert(set,value)

reverse[value] = table.getn(set)

end

end,

remove = function(set,value)

local index = reverse[value]

if index then

reverse[value] = nil

local top = table.remove(set) --删除数组中最后一个元素

if top ~= value then

--若不是要删除的值，则替换它

reverse[top] = index

set[index] = top

end

end

end,

find = function(set,value)

local index = reverse[value]

return (index and true or false)

end,

}})

end

local s = newset()

s:insert("hi0")

s:insert("hi1")

for _,Value in ipairs(s) do

print(Value)

end

print(s:find("hi0"))

s:remove("hi0")

print(s:find("hi0"))

--[[--output--

hi0

hi1

true

false

--]]

上面set之所以能做到插入、删除和查找为O(1)，首先是lua中table实现的保证，另外一个是利用了一个额外的数组reverse，来保存数组s中每个数据在s中的位置，相当于以空间换时间。

ps:上面代码是对luasocket源码samples/tinyirc.lua中代码的改写。

　　　　　　　　　　　　　 查看评论 回复