Tag set 的数据结构优化
在最近实现的 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 时，插入操作需要移动的条目也会相对减少。
Comments
Posted by: Cloud | (11) July 30, 2021 12:43 PM
Posted by: Cloud | (10) July 30, 2021 09:57 AM
Posted by: Anonymous | (9) July 29, 2021 11:50 PM
Posted by: Anonymous | (8) July 29, 2021 11:46 PM
Posted by: 菜鸟浮出水 | (7) July 29, 2021 11:16 AM
Posted by: 土豆太大 | (6) July 28, 2021 06:03 PM
Posted by: dwing | (5) July 28, 2021 11:52 AM
Posted by: Cloud | (4) July 28, 2021 10:57 AM
Posted by: fenghou | (3) July 28, 2021 09:07 AM
Posted by: hanxi | (2) July 28, 2021 01:29 AM
Posted by: Luo | (1) July 27, 2021 08:33 PM