Sparse Set

像是咱 ECS 等都比较喜欢用的一种数据结构, 目的是希望在一个大的整数空间内, 我们有若干数据存活, 希望既可以做到 O(1) 的查找, 插入, 删除, 又可以快速的仅遍历存活元素.

推导

先一点点来看 —— 做到 O(1) 的查找, 插入, 删除, 可能确乎是比较容易想到哈希表, 不过存在的问题是其缓存局部性很烂, 所以在遍历的时候实际上运行效率不如 vector 那一类拥有连续内存空间的数据结构.

不妨开辟一个巨大的数组, [0, MaxIndex), 这样我们依旧可以通过 O(1) 的时间复杂度进行访问, 删除, 插入. 不过此时如果我们需要遍历存活元素就很坏 —— 需要遍历整个大数组才可以, 这样要付出 O(MaxIndex) 的时间复杂度, 尤其在 MaxIndex 大的时候很坏.

那我们不妨仅使用一个 vector 来存储存活对象 —— 这样我们遍历所有的存活元素就是非常快速的 O(N) 即可, 不过这样又无法做到 O(1) 的时间复杂度进行查找删除等操作, 很坏, 它们的时间复杂度会垮到 O(N)

那么我们同时维护这两个数组? 一个超大稀疏的数组和一个紧密的 vector —— 基本上可以解决问题, 唯一的, 删除的时候会挂掉, 我们可以通过稀疏数组知道 exists[i] == true 它存在, 但是无法通过这个 i 来 O(1) 的访问到元素进行删除 —— 仍然需要通过一次 O(N) 的遍历去查找位置. 很坏

所以抛开紧密 vector 来说, 我们真正想要的东西是 —— 「一个可以快速通过 index -> dense index 的数据结构」, 那么也就是说, 第二个sparse 数组不再是 bool 的类型进行存在性判断, 而是一个 index -> dense index 的映射.

上述就是稀疏集的数据结构简易推导.

性质

不妨稍作调整, 整理可得, 对于存在于当前集合中的元素 ——

• dense 数组, 做 dense index -> entity index
• sparse数组, 做 entity index -> dense index

我们找到了一个很巧妙的性质, 两个数组其实是互相“反向”的, 也就是说 dense[sparse[index]] = index

CRUD

先说查找 —— 上文性质中刚提到一个 dense[sparse[index]] = index, 我们可以借助这个性质, 只要这个等式满足, 就可以说这个元素存在 —— 那么很反直觉的, 为什么要做一次反向检查? 直接查 sparse[index] 是否存在不就好了吗? 然而实际上 sparse[index] 不一定会被清理, 先埋个钩子.

接着看删除 —— 哪怕我们现在可以通过 sparse[index] 获得要删除的下标在 dense 数组的位置, 但是众所众知, 对于 vector 的中间元素进行删除依旧是一件很贵的事情.

所以我们假设 —— 集合不要求插入的元素保持插入顺序 —— 比如 {1, 3, 5} 和 {1, 5, 3} 本质上是同一个集合. 既然如此, 我们在删除元素的时候就不需要一定要从中间来挖走一个坑, 而是直接把要删除的元素交换到尾部, 然后再删除不就好了? —— 著名的 swap-and-pop 就这样推导出来 (很久以前在 vector 的删除模块其实好像也说了这)

那么总结一下删除我们要做的事情 ——

• Dense: 把待删除元素和尾部元素交换位置, 然后删掉尾巴
• Sparse: 将 sparse[index] = INVALID_ID (当然不清理也可以), 然后更新现在 Sparse 中被交换的元素位置

sparse[index] 不清理也是一种常见做法 —— 因为我们在判断存在的时候使用了反向检查, 所以过期数值会使得反向检查不通过.

可以参考一下 EnTT, 尝试学习 ing