0
0

Tag set 的数据结构优化

云风 发表于 2021年07月27日 10:44 | Hits: 653
Tag: ECS | 算法

在最近实现的 ECS 库中,Tag 是一种非常重要的数据结构。它是一类特殊的 Component ,不携带数据,但会关联到同一 Entity ,最重要的用途是用于筛选。我在设计 Comonent 的数据结构时,采用了一种简单的数据结构。它采用连续内存储存的数组,按 Entity id 有序排列。并在查询算法上做了一些优化,可以使得大部分查询时间小于 Log(N),接近常量时间。

但是,这样做的代价是插入和删除操作都是 O(n) 的。为了避免大量的插入删除操作堆积在一起时,整体的时间复杂度变成 O(n^2) ,我禁止 Component 的删除,而删除 Entity 改为标记,待一帧结束后一起删除。这样,可以让批量删除保持在 O(n) 的复杂度。

标记操作实质上就是打 Tag 。Tag 作为一种特殊的 Component 就需要支持动态的增删(Enable/Disable) 。

好在 Tag 不携带数据,我找到一种方法可以针对这种数据结构,让平均复杂度优于 O(n) 。

因为 Tag 本质上储存的就是有序的 Entity id 数组。例如,当有 5 个 entity 1,3,5,7,9 被打上特定 tag 时,就是有这么一个长度为 5 的 id 数组,{ 1,3,5,7,9 } 。

如果我们需要 disable 5 ,传统方法就是从数组中删除 5 这一项,变成 { 1,3,7,9 } 。这个算法的复杂度是 O(n) 的,查找到 5 的比较次数为 Log(n) ,平均移动的数据为 n/2 项。

但,考虑到这个数组仅用于确定一个 id 是否存在,以及遍历这些 id 。我们可以做这样的优化:当需要删除 5 时,并不移动 5 后面的 id ,而是复制它前面或后面临近的 id 。即,把数组变成 { 1,3,3,7,9 } 或 { 1,3,7,7,9 } 。这样,删除操作就是 O(log N) 了。同时,也没有给遍历增加太多的负担。我们可以在遍历的同时,重新整理这个数组,去掉重复项。

另外,当数组集合经过若干次删除后,出现了重复 id ,之后的增加 (Enable) 新的 id 时,插入操作需要移动的条目也会相对减少。

原文链接: https://blog.codingnow.com/2021/07/tag_set.html

0     0

我要给这篇文章打分:

可以不填写评论, 而只是打分. 如果发表评论, 你可以给的分值是-5到+5, 否则, 你只能评-1, +1两种分数. 你的评论可能需要审核.

评价列表(0)