一种玩家列表更新、查询的方法及系统与流程

2021-01-11 15:01:55|

336|

起点商标网

本发明涉及计算机技术领域，尤其涉及一种玩家列表更新、查询的方法及系统。

背景技术：

网络游戏开发过程中，不免会涉及到玩家和玩家之间的交互，这时候就需要实现一个玩家列表，客户端请求每个玩家的信息，服务器返回对应玩家的信息，这时候服务器需要维护一个数据结构，考虑如下几种情况：

a)玩家上线；

b)玩家下线；

c)玩家信息变更；

d)玩家请求获取全服玩家列表；

e)玩家请求某个玩家信息；

一般的玩家列表实现方式采用的是数组，在实现以上操作的时候，时间复杂度基本都是o(n)的，随着玩家数的增加呈现线性复杂度，会大大提升服务器的cpu占用率；

a)玩家上线：插入到数组尾部，时间复杂度o(1)；

b)玩家下线：遍历玩家列表，找到对应玩家，进行删除；遍历时间复杂度o(n)，删除时间复杂度o(n)；

c)玩家信息变更：遍历玩家列表，找到对应玩家，进行信息变更；遍历时间复杂度o(n)，更新时间复杂度o(1)；

d)玩家请求获取全服玩家列表：一般采用分页下发，但是服务器存储只有一个数组，所以需要下标索引到对应分页，请求数c，复杂度o(c)；

e)玩家请求某个玩家信息：遍历玩家列表，找到对应玩家，下发玩家信息；遍历时间复杂度o(n)；

当玩家数到达一定量级，就会对服务器的承载产生巨大影响。

因此，现有技术中遍历玩家列表需要遍历整个列表，会对服务器的承载产生巨大影响。

技术实现要素：

本发明的目的是针对现有技术的缺陷，提供了一种玩家列表更新、查询的方法及系统，利用这种高效更新查找技术来对玩家信息进行存储，查找，平均时间复杂度都能达到o(logn)。

为了实现以上目的，本发明采用以下技术方案：

一种玩家列表更新、查询的方法，包括：

s1.获取每个玩家的玩家信息，并将每个玩家的信息用结构体表示，得到玩家信息的玩家结构体；

s2.初始化玩家列表的数组，并将数组中的每个元素与一个映射槽相对应，每个映射槽存储多个玩家结构体的链表头节点；

s3.判断是否有玩家上线，若是，则计算当前玩家的信息所处的映射槽，并执行步骤s4；

s4.判断计算得到的映射槽中是否存在当前玩家的信息，若否，则对所处的映射槽进行扩充，并将当前玩家结构体的链表头节点存储于所处的映射槽中；若是，则执行步骤s5；

s5.判断当前玩家是否下线，若是，则计算当前玩家的信息所处的映射槽，并遍历计算得到的所处的映射槽中玩家结构体的链表头节点，得到当前玩家的信息，将所述当前玩家的信息删除；若否，则不做处理。

进一步的，所述步骤s3之前还包括：

根据玩家的信息作离散化映射，得到玩家所处的映射槽。

进一步的，所述步骤s3中计算当前玩家的信息所处的映射槽是根据玩家信息通过o(1)的时间计算出当前玩家所处的映射槽。

进一步的，所述步骤s3中计算出当前玩家所处的映射槽后还包括将当前玩家的信息插入映射槽的有序链表中，其中有序链表中玩家的排序方式为按照玩家的总在线时长进行排序。

进一步的，所述步骤s5中计算当前玩家的信息所处的映射槽是根据玩家信息通过o(1)的时间计算出当前玩家所处的映射槽。

进一步的，所述步骤s1中玩家信息包括玩家id。

相应的，还提供一种玩家列表更新、查询的系统，包括：

获取模块，用于获取每个玩家的玩家信息，并将每个玩家的信息用结构体表示，得到玩家信息的玩家结构体；

初始化模块，用于初始化玩家列表的数组，并将数组中的每个元素与一个映射槽相对应，每个映射槽存储多个玩家结构体的链表头节点；

第一判断模块，用于判断是否有玩家上线；

第二判断模块，用于判断计算得到的映射槽中是否存在当前玩家的信息；

第三判断模块，用于判断当前玩家是否下线。

进一步的，还包括：

处理模块，用于根据玩家的信息作离散化映射，得到玩家所处的映射槽。

进一步的，所述第一判断模块中判断是否有玩家上线，若是，则根据玩家信息通过o(1)的时间计算出当前玩家所处的映射槽。

进一步的，所述第二判断模块中判断计算得到的映射槽中是否存在当前玩家的信息，若否，则对所处的映射槽进行扩充，并将当前玩家结构体的链表头节点存储于所处的映射槽中。

与现有技术相比，本发明具有以下有益效果：

1、本发明比常见的数组实现更加高效，每一步操作都能在o(x)的时间复杂度内完成，以目前的人数来看，不会影响服务器的效率；

2、单个玩家上线、下线，不需要遍历全服玩家进行玩家的插入和删除，查找映射槽的时间永远为o(1)；

3、玩家信息的修改和查找不需要遍历全服玩家；

4、玩家id的范围[a,b]中的a不一定要从0开始，可以定义很大的数比如1000000000000，最后采用的是离散化映射机制，对于合服的时候id冲突做了很好的兼容；

5、分页请求可以不需要遍历全服玩家，大大节省了遍历的效率；

6、x的取值可以根据实际情况而定，参考值128，256，可以认为查询的时间复杂度是常量的。

附图说明

图1是实施例一提供的一种玩家列表更新、查询的方法流程图；

图2是实施例一提供的数组示意图；

图3是实施例一提供的有序链表示意图；

图4是实施例一提供的结构体的值域示意图；

图5是实施例二提供的一种玩家列表更新、查询的系统结构图。

具体实施方式

以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需说明的是，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。

本发明的目的是针对现有技术的缺陷，提供了一种玩家列表更新、查询的方法及系统。

实施例一

本实施例提供一种玩家列表更新、查询的方法，如图1所示，包括：

s11.获取每个玩家的玩家信息，并将每个玩家的信息用结构体表示，得到玩家信息的玩家结构体；

s12.初始化玩家列表的数组，并将数组中的每个元素与一个映射槽相对应，每个映射槽存储多个玩家结构体的链表头节点；

s13.判断是否有玩家上线，若是，则计算当前玩家的信息所处的映射槽，并执行步骤s14；

s14.判断计算得到的映射槽中是否存在当前玩家的信息，若否，则对所处的映射槽进行扩充，并将当前玩家结构体的链表头节点存储于所处的映射槽中；若是，则执行步骤s15；

s15.判断当前玩家是否下线，若是，则计算当前玩家的信息所处的映射槽，并遍历计算得到的所处的映射槽中玩家结构体的链表头节点，得到当前玩家的信息，将所述当前玩家的信息删除；若否，则不做处理。

在步骤s11中，获取每个玩家的玩家信息，并将每个玩家的信息用结构体表示，得到玩家信息的玩家结构体。

结构体是由一批数据组合而成的一种新的数据类型。组成结构型数据的每个数据称为结构型数据的“成员”。

每个玩家的信息用一个结构体来表示，结构体中采用玩家的id作为全局的唯一标识，结构体的值域从a到b连续；a和b的范围不需要控制，但是b-a一定是可控范围内，比如2的32次以内；

在本实施例中，a是自然数区间[a，b]的下界，b是自然数区间[a，b]的下界。因为最后映射到数组的时候是x-a去映射，比如说a+1映射到1，a+10映射到10，以此类推。所以b-a代表了实际有多少玩家的量，这个是需要控制的，而a本身的值是多少并无大碍，如图4所示。

每个玩家的信息用一个结构体来表示，如：

在步骤s12中，初始化玩家列表的数组，并将数组中的每个元素与一个映射槽相对应，每个映射槽存储多个玩家结构体的链表头节点。

将玩家列表用数组的形式表示，并初始化该数组，该数组中的每个元素对应一个映射槽，映射槽用于存储玩家结构体的链表头节点，且每个映射槽存储多个玩家，设每个映射槽存储的玩家数量为x家。

本实施例为了避免频繁的重分配内存，将数组长度定义为8(定义的太小，前期会有各种内存重分配机制，产生内存碎片)，如图2所示。

在本实施例中，还包括：

根据玩家的信息作离散化映射，得到玩家所处的映射槽。

根据玩家的id作离散化映射；例如，玩家id为s，那么这个玩家就落在floor((s-a)/x)号映射槽内，其中floor代表向下取整。

在步骤s13中，判断是否有玩家上线，若是，则计算当前玩家的信息所处的映射槽，并执行步骤s14。

当有玩家上线时，根据玩家id通过o(1)的时间计算出它应该属于哪个映射槽。

在本实施例中，如图3所示，每个映射槽均设有一个有序链表，即每个映射槽维护一个有序链表，其中有序链表中玩家的排序方式为按照玩家的总在线时长进行排序，总在线时间越长的放越后面，这样做的目的是为了在玩家下线的时候以最快的速度从链表中移除玩家，插入时间复杂度为o(x)；

在步骤s14中，判断计算得到的映射槽中是否存在当前玩家的信息，若否，则对所处的映射槽进行扩充，并将当前玩家结构体的链表头节点存储于所处的映射槽中；若是，则执行步骤s15；

当玩家上线后，判断登录的玩家的id是否处于所处的映射槽中，若不在，则对原本应该所处的映射槽进行倍增扩容。例如将数组长度扩大为16、32、64倍等等，然后将该玩家原来的数据拷贝到扩容后的映射槽中，拷贝的时候只需拷贝链表头即可，因为链表本身是通过链表的形式链接过去的，所以不需要重新生成内存。

在步骤s15中，判断当前玩家是否下线，若是，则计算当前玩家的信息所处的映射槽，并遍历计算得到的所处的映射槽中玩家结构体的链表头节点，得到当前玩家的信息，将所述当前玩家的信息删除；若否，则不做处理。

当有玩家下线时，根据玩家id通过o(1)的时间计算出它应该属于哪个映射槽，遍历对应的链表，移除下线玩家的信息。

在本实施例中，当批量请求玩家列表的时候，根据玩家id通过o(1)的时间计算出它应该属于哪个映射槽，然后遍历链表找到对应的起始玩家id，再往后找y个玩家(y代表客户端请求的一页玩家数，供客户端显示用，一般不会超过20)，如果超过当前映射槽，则去下一个映射槽继续找剩下的玩家，组成列表后将信息下发给客户端。

本实施例通过线性连续标识、初始分配策略、有序线性链表结点数组、有序链表、倍增策略、离散化映射槽、批量查询的方式来对玩家信息进行存储，查找，遍历时只需要遍历映射槽，不需要遍历整个列表，使平均时间复杂度都能达到o(logn)，减少了cpu占有率。

与现有技术相比，本实施例具有以下有益效果：

1、本实施例比常见的数组实现更加高效，每一步操作都能在o(x)的时间复杂度内完成，以目前的人数来看，不会影响服务器的效率；

2、单个玩家上线、下线，不需要遍历全服玩家进行玩家的插入和删除，查找映射槽的时间永远为o(1)；

3、玩家信息的修改和查找不需要遍历全服玩家；

4、玩家id的范围[a,b]中的a不一定要从0开始，可以定义很大的数比如1000000000000，最后采用的是离散化映射机制，对于合服的时候id冲突做了很好的兼容；

5、分页请求可以不需要遍历全服玩家，大大节省了遍历的效率；

6、x的取值可以根据实际情况而定，参考值128，256，可以认为查询的时间复杂度是常量的。

实施例二

本实施例提供一种玩家列表更新、查询的系统，如图5所示，包括：

获取模块11，用于获取每个玩家的玩家信息，并将每个玩家的信息用结构体表示，得到玩家信息的玩家结构体；

初始化模块12，用于初始化玩家列表的数组，并将数组中的每个元素与一个映射槽相对应，每个映射槽存储多个玩家结构体的链表头节点；