杰哥瞎扯蛋之MUD机器人的数据结构

jarlyyn

作为一个行动力比某贼秃高N遍的人，昨天重新开始整lua代码时实在受不了lua的table,把golang标准库的list容器和ring容器搬到了lua里。一时兴起，开个帖子随便扯扯Mud机器里数据结构的相关应用。

当然，我自己不是科班出身，基础可能有所欠缺，本身也不想扯原理只想扯应用，外加计算机技术本身发展的复杂性，可能写的不是最精确，只是希望能介绍一点基本概念，方便大家自己去找方向研究。

entangle

抢占杰哥的沙发

jarlyyn

1.数组和切片

数据结构本质就是怎么堆放和查找数据的方式。那么最直接的，最简单的方式必然是把所有数据连续堆放，一个一个找。

这就是数组，参考 https://baike.baidu.com/item/%E6%95%B0%E7%BB%84/3794097?fr=ge_ala。

数组的本质就是一块连续的内存。当你知道第一个元素的地址后，通过加上偏差量*数据长度,就能得到之后任何一个元素的值了，这也是绝大部分语言的数组的下标是从0开始的原因。

在读取的场景下，数组的获取效率是非常高的。缺点是必须分配足够大的空间，以及维护时涉及扩容和移动的操作。

而切片，其实就是获取数组种的一部分，比如一个40个空间的内存段，我使用其中的第3-20号空间。这样当我需要时，还能继续改变长度追加数据，起到变长数组的效果。

对于脚本面对的场景来说，绝大部分场景只需要应用号数组和切片就够了。

在lua里有一个最想接近数组的类型

那就是～

table同学做下，没你啥事

那就是字符串，string同学，掌声给起～～～～

开个玩笑，string并不是真的是数组，他对应的还是C语言里的字符串，参考, 只不过他是lua里最像数组的一个东西,以至于同样没有数组的javascript语言还搞了个TypedArray来解决诸如图片处理之类的功能。

而table中的list部分，那就是个孽种，让我一看就头大，情愿把链表弄进来……

总体来说，如果要形象的形如数组的话。

数组就是承包一整块地造房间，然后用连续的编号给房间命名，给房间里的人送饭只要一路走下去每个房间发一个盒饭就行，而要找第N号房间的住户，主要从第一个房间向后走N步，直接开门就行。简单，粗暴，直接。

jarlyyn

2.指针

指针这玩意是数据结构么？

不是……

只不过除了数组这类连续的数据结构，其他结构难免会扯到指针。

一般来说，不追求精确的说法，指针其实就是由一个数据地址，和一数据类型组成。

比如我们在lua里执行代码

1. print({})

复制代码

会得到大概这样的响应

1. table: 0x55600a386470
   

复制代码

我们大体可以认为，这是一个位置在16进制数55600a386470，类型为table的对象。

那当我们修改数据时，我们就是当他做table,把55600a386470里的数据进行调整。

而所以指向同一个table的数据都得到一样的调整后的结果，因为是同一份数据，同一个房间。

lua里本身没有指针，只有引用的概念

参考：
https://blog.51cto.com/leejia/1945378

指针或者引用，你可以理解为一个名片。有了名片，你就可以知道一个地址，以及那个地址是一个什么单位。

上海市虹口区曲阳路1111号
虹口税务局(瞎编的）

这个理解很不靠谱，但这是为了解释之后的内容，可以先这么理解着。

jarlyyn

3.链表

有了指针是名片的错觉，我们可以开始误解，哦不，理解链表了。

链表，大概可以说，是一串有顺序的数据，通过指向下一个数据的指针(对对对，下家的名片），串起来的数据。

理论上来说，链表和数组不同，存放的是散乱的数据，优点是维护，插入，删除很方便，都是散乱的，不需要挪窝，麻烦的是找人，必须按数序一家一家向下找。

参考：https://www.hello-algo.com/chapt ... edlist/linked_list/

这个看起来还是优点专业，没时，让我来继续瞎比喻。

链表等于是物流。

你是司机，你要送很多快递

每个快递有一份收件人地址的名片(指针)和货物(数据）

你不听的去下一张名片的地址，送货物，拿新的名片，送货物，直到没有名片为止，你一天的工作就结束了，可以回家喝老酒吃烧烤了。

如果哪一天你的工作发生了变化，也很简单，把对应的名片换掉就好。本来是北京->天津->南京->上海的，直接改北京->南京->上海就行。要插入也一样方便。

如果给快递加一张上家名片，那就叫双向队列，很明显，下家可以退货(反向查找)了。

所以，链接就是维护容易，随机查找(盘货)慢，讲究顺序的数据。

一般来说，发送队列和遍历路径就是典型的链表应用。

只不过一般来说，脚本语言涉及的复杂度和性能要求，不需要链表，一个数组或切片就能搞定了。

除非你用的语言维护数组和切片是在蛋疼(没错，我说的就是lua的table)

jarlyyn

4.队列，栈，环

这三个本质来说不是数据结构(来自民科的自信)，而是使用数据的方式

就是通过 先进先出(FIFO),先进后出(FILO)，或者循环使用数据。

参考：https://www.hello-algo.com/chapter_stack_and_queue/

对于我而言，因为写go用习惯了，直接把list(双向列表）和ring(环状列表）拿了过来，准备做队列和历史信息记录。

瞎扯扯，别当真。

jarlyyn

5.树

树是啥玩意？长果子的？好吃不？

树，从我的角度来说，就是通过将数据合理分类，能通过分支，快速搜索到数据的一种工具。

参考 https://www.hello-algo.com/chapter_tree/

他的外形就是有一个根节点(起点），通过不同的分支(其他数据），把所有数据串起来。

形象的说，与其说是树，不如说是水流，从水源不听分支，流向祖国大地各处。

链表每个房间只有一张名片，而树的话每个房间有不同的名片，吃饭用的，洗脚用的，打球用的，直接向不同的方向延展。

他的作用，举个例子，你要在64个房间里找到一个人。

通过数组或者链表，你需要64个房间一个一个找。

而如果人的住宿有一定规律 ，你可以通过2分法，分别排除 32间，16间，8间，4间，2间，1间，5次就找到具体的房间了。

是不是很高效？很性能？很牛比？

什么二叉树，红黑树，B树(我真的没B数），听起来就高科技号的不行吧？

可你那么看中效率，写脚本干嘛？

所以，至少在我眼里，写加本基本没啥机会用树相关的数据结构，了解下就行。

jarlyyn

6.hash表

hash表是除了切片外，大部分语言最常用的数据结构之一。

参考 https://www.hello-algo.com/chapter_hashing
lua的table就是实现了hash表的功能(注意，lua的table是非常复杂的东西，涉及到伪数组的功能和元表)

最大的用途是可以用非连续的数字/字符串来对应数据，实现数据与数据之间的对应。

hash指的是摘要

https://baike.baidu.com/item/Hash/390310?fr=ge_ala

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

举个歪例子

我们把妹子们按外貌肤色腿长胸围等固定几个标准进行分类。

在我们要找貂蝉时，我们眼睛一扫，直接找桃花眼瓜子脸大胸长腿细腰大波浪的那个名片夹，那速度，杠杠滴。

至于hash碰撞，就是我们有好几个妹子都是桃花眼瓜子脸大胸长腿细腰大波浪，所以我们这个名片夹有好多张名片，只能慢慢招，想想就美滴很啊，吸溜，吸溜。

harrychencyh

虽然看不懂，但是杰哥终于管自己叫杰哥了
我认为这是成功！（确信）

jarlyyn

7.hash表的应用。

能想到的hash表的应用，最直接的就是表驱动了。

就是在hash表里存函数。

比如

1. hello={
   
2. 'ambi'=function() chat 大全真天下第一 end,
   
3. 'man'=function() chat 又是一分钱红包么 end,
   
4. 'wxliu'=function() chat 杀上少林山，砸光秃脑壳' end,
   
5. ''=function() chat* hi)
   
6. }
   

复制代码

就能通过不同的id来做不同的回复了。

表驱动的优点主要时易于维护，可以控制反转，由不同的包来添加和维护，以及能很方便的以文本或数据库的方式进行数据和程序的脱离

https://baike.baidu.com/item/%E8%A1%A8%E9%A9%B1%E5%8A%A8%E6%B3%95