聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

Tag set 的数据结构优化

2021-07-27 12:31 浏览: 5825 次 我要评论(0 条) 字号:

在最近实现的 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 时,插入操作需要移动的条目也会相对减少。



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复