云风的 BLOG

老方法的问题是：这个方法高效的前提是，大部分 Entity 一旦创建，之后就不再需要对业务层暴露引用。如果我们对每个 Entity 都预留一个引用，它就没太大意义作为一个可选部件存在。

但这样，我们就需要在一开始就觉得要还是不要这个引用，实际开发中，非常难把握。

另外，从一个组件快速找到兄弟组件，时间复杂度其实是 O(log N) 的。因为同类组件之间是以有序 id 进行排列，用二分法查找。但 luaecs 对循序遍历做了特别优化，这样，在 select 循环中，兄弟组件的查找可以接近 O(1) 的复杂度。

从引用找到 Entity 其它组件的过程却是个随机访问的过程，不能被同样的策略优化。从引用定位到用来拣选的 Tag 的过程优化到 O(1) 复杂度意义不大。

和老方案不同，新方案是非侵入式的，不修改任何 luaecs world 已有的数据结构。新的方案更像是内存数据库模型。我们可以挑选一个特定的组件作为 key ，为它额外建一个索引结构体。这个结构体完全是一个 cache 。也就是说，当我们对 ECS 的 world 做持久化时，完全可以扔掉这些 index cache 。同时，你也可以对多个 key 建立不同的索引 。

可做索引的 key 必须是整数类型。索引结构就是一个 hash 表。用户需要引用一个 Entity 时，可以给 Entity 添加一个唯一 id 的组件，并记录下 id 。需要解引用时，用 id 去查询 hash 表，构建出访问 Entity 用的迭代器。

在第一次引用时，使用 O(n) 的遍历算法找到对应的 Entity ，并记录下位置。之后，不必再重复构造这个迭代器。Cache 的大小是固定的，发生 hash 碰撞时，老的记录会被覆盖掉。由于现在 luaecs 中的数据会因为删除 Entity 而发生移动，所以每次获取迭代器都会做二次校验，如果之前的记录已经失效，则会重新矫正。

这个方案中相关的优化基于以下几点：

我们可以自由的为所有的 Entity 保留引用，只需要记录下任意 id 即可。但是，我认为，解引用的频次是非常低的。只有少部分情况才需要通过之前保留的引用找到特定 Entity 。高频操作依旧推荐在 select 循环中完成：即，批量处理对象和对象之间的关系。

如果一个引用被经常使用，那么让它的解引用过程足够快；如果引用只是备用，那么可以接受更低的效率。相比 Enitty 的总数量而言，常用的 Entity 之间的关系对的数据是比较少的。

如果一个 Entity 被创建出来后需要保留其引用，那么首次解引用的时机会非常早（创建出来后和解引用之间只会创建少量 Entity）。也就是说，如果你保留了一个引用，你越久不使用它，就越不太可能用它。

关于最后一点，我针对的是我在我们项目的实际用法：解引用大多发生在一批 Entity 批量创建的过程中。

实现上做了一个简单的优化：通过 id 遍历查找 Entity 时，是按创建次序的逆序进行的。虽然算法是 O(n) 的，但是会更快的找到。同时、当 Entity 的数据因为有其它 Entity 被删除而移动时，虽然原来的迭代器会失效，但寻找新的位置只需要从原来的位置向前找即可。因为，移动总是向前的。