• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Lua设计与实现--读书笔记

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

lua简介

C++底层核心模块,暴露核心接口给lua脚本层,网络的收发都在c++层完成,本书简述lua解释器的实现原理,工业级脚本语言

特性:简洁高效可移植可嵌入可扩展

纯C编写

Lua的数据结构、Lua虚拟机、Lua的其他内容

我缺少的知识:词法分析、语法分析、递归下降分析、BNF规则

Lua代码是解释成lua虚拟机能识别的字节码而运行的

  • 翻译成字节码
  • 字节码装载到虚拟机执行

Lua是有宿主系统的

Lua采用一种通用的数据类型来表示所有的类型,Lua只有字符串和表两种基本的数据结构

一种通用的数据类型:lua_TValue

  • 一个字段存储数据类型
  • 存储不同的数据类型的数据(联合体)

commonHeader+union,lua还要标出处理GC的对象

配图:

字符串

每当创建字符串时,会先查找内存中是否有一份相同的字符串数据,如果存在就直接复用,将引用直接指向字符串数据,否则就重新创建一份数据,这样在进行字符串数据比较和查找时性能会提升不少,系统内部维护了一个全局的字符串的表用来存放字符串(LUA虚拟机使用一个散列桶来管理,global_state的strt),比较时可以直接比较字符串散列值,这样也是有空间优化,相同字符串只有一份数据

应当尽量少的使用字符串连接符,每次使用都会创建一个新的字符串,大量重复的相同字符连接可以用一个table缓冲区一个字符一个字符的缓存起来,然后再调用table.concat将其全部连接

Table

有数组和散列表部分,唯一的要求就键值不能为nil

数组从1开始索引,内涵散列桶数组起点和终点的指针还有元表,意思0和负数的索引都是哈希表里的内容,如果数字的很大,超过了数组长度则是在散列表里面存

存的数据有可能在数组或者在散列表部分

查找数据:使用key来查找。我们看这个key是否为正整数且他是否大于0且小于等于数组长度,在则在数组中查找,不在则跑到散列表去查

设置数据:set setnum setstr三个set数据的函数先找对应的key,找不到则内部是调用一个newkey函数分配一个新key,大小不够会重新散列

个人实践规律:取长度符号#

取长度,只对表的序列部分进行,序列指的是表的一个子集,

当既有数组部分又有散列表部分,优先取数组部分长度,

当只有数组部分时候取数组的长度

(#{1,2,3,nil,4,5,6,} == 6)

当散列表的key和数组的Index一致的时候,遇到[num] = nil的时候便停止计数

(#{[1] = 10,[2]=20,[3]=nil,[4]=60} ==2)

(#{[1] = 10,[2]=20,[3]=32,[5]=60} ==3) 缺少4

当只有散列表部分时,取key从1开始的最大正整数

(#{["asd"] = 10,["sd1"]=20,["aasd"]=nil,[45]=60} == 0)

(#{["asd"] = 10,["sd1"]=20,["aasd"]=nil,[1]=60,[2]=899} == 0)

一般要规避重新散列操作,一般通过只使用数组部分、预分配等方式来避免重新散列

尽量不要混用数组和散列表部分,一个table最好只放一类数据

lua实现一个队列

网上的版本,用起来,pushright存数据会往数组里的填很多东西,pushleft突破了0,会往哈希表里填东西,如果一直popleft多了则数组部分的头部会被回收吗?推测不会,数组部分的指针指向的数组整体,前面几个元素回收了头部会改变,如果是popright回收数组部分是可以理解的,如果pop的是哈希的部分应该是可以回收的

List = {}
function List.new ()
    return {first = 0, last = -1}
end

function List.pushleft (list, value)
    local first = list.first - 1
    list.first = first
    list[first] = value
end

function List.pushright (list, value)
    local last = list.last + 1
    list.last = last
    list[last] = value
end

function List.popleft (list)
    local first = list.first
    if first > list.last then error("list is empty") end
    local value = list[first]
    list[first] = nil -- to allow garbage collection
    list.first = first + 1
    return value
end

function List.popright (list)
    local last = list.last
    if list.first > last then error("list is empty") end
    local value = list[last]
    list[last] = nil -- to allow garbage collection
    list.last = last - 1
    return value
end

插入、删除时间复杂度 O(1),空间复杂度可能会随着消息变大而变大,O(n)

使用Insert和Remove的版本,空间复杂度是O(1)的,时间复杂度是(n)

关于清空lua table

a = {1,2,3,4,5}
 
function upDate(t)
 print("====")
 print(t)
 t = {}
 print(t)
end
 
upDate(a)
print(a)
print(a[1])

这里设置t = {} 或者 t = nil都不会真的清空table对象 a

只是处理了变量和值之间的关系,t的地址是值传递的,尝试用一个新表的地址给它赋值会出现函数参数值传递,对地址t引用的实际值并不会有影响,但是通过t改动引用table里的实际值是会对a有影响的比如t[1]=999,这里就是通过地址改动到了实际值的区域

我的方法是使用——table套table,其实就是相当于指针的指针

local a = {1,2,3,4,5}
local b = {9,99,999,9999}
function upDate(t)
 print("====")
 print(t.a)
 t.a = nil
 --a = nil
 print(t.a)
end

local ta ={}
ta.a = a
upDate(ta)

print(ta.a)
print(a)

这样子ta.a可以便可以正确的赋值为nil了

我实现的一份LuaQueue代码

local LuaQueue = {}
-- pure array table, if you want to iterate use lua "ipairs"
function LuaQueue.New()
    return {_length = 0,_maxLength=10,_queue={}}
end

function LuaQueue.SetMaxLength(queue,length)
    if(queue==nil) then
        error("Queue is nil")
    end
    queue._maxLength = length
end

function LuaQueue.GetLength(queue)
    if(queue==nil) then
        error("Queue is nil")
    end
    return queue._length
end

--push in array last pos O(1)
function LuaQueue.Push(queue,val)
    if(queue==nil) then
        error("Queue is nil")
    end
    if(queue._length<queue._maxLength) then
        table.insert(queue._queue,val)
        queue._length = queue._length+1
    else
        error("Already reach last pos")
    end

end

--O(n)
function LuaQueue.Pop(queue)
    if(queue==nil) then
        error("Queue is nil")
    end
    if(queue._length>0) then
        table.remove(queue._queue,1)
        queue._length = queue._length-1
    else
        error("Queue is Empty")
    end
end

function LuaQueue.GetData(queue)
    if(queue==nil) then
        error("Queue is nil")
    end
    local data={}
    if(queue._length>0) then
        for _,v in ipairs(queue._queue) do
            table.insert(data,v)
        end
        return data
    else
        print("Queue is Empty")
    end
end
function LuaQueue.ClearData(queue)
    if queue == nil then
        error("Queue is nil")
    end
    queue._queue = {}
    queue._length = 0
end
--[[Example:
    local testQueue = LuaQueue.New()
    LuaQueue.Push(testQueue,10)
    LuaQueue.Push(testQueue,20)
    LuaQueue.Push(testQueue,30)
    LuaQueue.Push(testQueue,40)

    local data = LuaQueue.GetData(testQueue)
    for _,v in pairs(data) do
    	print(v)
    end
    print("-------------------------------------")
    LuaQueue.Pop(testQueue)

    local data = LuaQueue.GetData(testQueue)
    for _,v in pairs(data) do
    	print(v)
    end
    print("-------------------------------------")
    LuaQueue.Pop(testQueue)
    LuaQueue.Push(testQueue,909)
    local data = LuaQueue.GetData(testQueue)
    for _,v in pairs(data) do
    	print(v)
    end
    LuaQueue.ClearData(testQueue)
--]]


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap