用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中代码的改写。

Lua 语言 15 分钟快速入门

Lua程序设计(第2版)中文 PDF

Lua程序设计(第二版)阅读笔记

NetBSD 将支持用 Lua 脚本开发内核组件

CentOS 编译安装 Lua LuaSocket

Lua 的详细介绍请点这里
Lua 的下载地址请点这里

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/64377907d9b03fcd2e1aae5c970b1bf5.html