ECS: 稀疏集和排序

对 稀疏集 进行排序是富有挑战的，因为它由两个数组组成 稀疏数组 和 密集数组，当 稀疏集 用作组件池的时候，情况更糟糕，因为这时候还会多出一个 组件数组

一般来说，有三种排序的方案

• 原地排序
  这种方法可以直接利用像 std::sort 这样的算法对密集数组进行排序

  1. 根据目标键值对密集数组排序
  2. 同步更新稀疏数组，反映密集数组中元素位置的变化

  优势：内存开销，小因为它无需额外的数据结构，算法成熟，因为可以直接利用 C++ 标准库的高效排序算法

  缺陷：更新稀疏数组的开销大，密集数组中的每次交换都需要同步更新稀疏数组，并且如果稀疏集合还与其他数组（如组件池）相关联，那么每次交换也需要同步更新这些数组

• 基于 排列 Permutations 排序 这种方法通过生成一个 排列向量 来决定排序后元素的新位置

  1. 创建一个索引向量，指向密集数组中的元素
  2. 根据目标键值对索引向量进行排序
  3. 使用排列向量重新排列密集数组，同时更新稀疏数组

  优势：交换次数少，通过排列向量直接确定最终状态，减少不必要的操作，并且当排序涉及多个关联数组时，可以统一应用排列向量

  缺陷：需要额外存储排列向量，且要多次遍历密集数组和稀疏数组

• 混合方法 混合方法结合了以上两种方法的特点

• 使用 排列向量 确定密集数组中元素的最终顺序

• 不直接应用排列，而是通过增量交换逐步实现排列，确保密集数组和稀疏数组同步

这种方法在性能和内存占用之间找到了平衡，减少了纯原地排序中大量交换的开销，并且不需要像排列方法那样完全物化一个新的排列数组，当然它的实现是最复杂的，需要同时实现排序和受控的交换过程

仅排序稀疏集

如果我们不将稀疏集用作池或类似池的基础，那么它们很容易排序，因为我们只有两个数组（密集数组和稀疏数组），只需对密集数组进行排序，然后根据排序结果更新稀疏数组

std::sort(dense.begin(), dense.end(), compare);
 
for(auto pos = 0; pos < dense.size(); pos++) {
    sparse[dense[pos]] = pos;
}

这种方法适用于，当我们仅有一个密集数组和一个稀疏数组的情况，包括在 密集数组 中将 实体 和 组件 结合在一个对象中，也同样适用

在这种情况下，实现是相对容易的，只需要标准库的 std::sort 和一个简单的循环即可完成，排序的复杂度是 $O(n\log n)$，更新稀疏数组的复杂度是 $O(n)$

显然它无法应对需要排序多个 密集数组 的情况，在更复杂的场景下，密集数组 可能不仅仅是实体数组，还有组件池等也存储为单独的 密集数组，单纯排序一个数组无法解决关联数组同步的问题

在像 EnTT 这样的 ECS 框架中，每个稀疏集通常不仅仅包含实体，还会包含多个组件池。这些组件池通常会以多个密集数组的形式存储，并需要与稀疏数组保持一致。这就导致了基本实现难以直接适用

原地排序 In-place sorting

原地排序是一种内存使用效率极高的排序方式，因为它不需要额外的内存开销，算法通过在容器内直接交换元素的方式完成排序，直到容器完全有序

然而，对于 稀疏集，原地排序稍显棘手

• 无法直接使用标准库
  std::sort 需要两个随机访问迭代器来定义排序范围，并直接在容器内交换元素，但是 稀疏集 由两个或多个数组组成，std::sort 无法处理多个数组的同步操作

• 数组需要同步
  稀疏集的密集数组和稀疏数组需要保持一致，如果还有其他关联的密集数组（例如组件池），这些数组也需要同步更新

• 随机访问迭代器的要求
  标准库要求迭代器返回实际的引用，而不是代理对象，如果稀疏集合使用的是某种代理模式，则标准排序算法无法直接使用

我们别无方法，只能实现自己的排序方法，选择某种排序方法，并在发生交换时执行以下几个步骤

1. 在稀疏数组中交换： 根据密集数组的索引更新稀疏数组
2. 在密集数组中交换： 交换密集数组中的元素
3. 同步其他数组： 如果有多个密集数组，每次交换时也需要同步这些数组

一般来说，自己实现的排序算法很难比标准库更好，所以存在一定风险

排列 Permutations

利用 排列 permutation 对 稀疏集 进行排序是一种非常高效的方法，特别是在内存消耗不是主要限制的情况下，它充分利用了标准库排序算法（如 std::sort）的高性能，同时大幅减少了排序过程中的交换操作次数

为了得到 排列，我们需要创建一个与 稀疏集 的 密集数组 等长的辅助数组 copy，用来保存 密集数组 元素在排序后的目标位置

std::vector<std::size_t> copy(dense.size());
std::iota(copy.begin(), copy.end(), std::size_t{}); // 初始化为 0, 1, 2, ..., N-1

我们用 0 到 N - 1 之间的数字初始化数组，其中 N 是密集数组的大小

然后，使用 密集数组 中的元素对 copy 进行排序

// 使用密集数组中的元素对 copy 进行排序
std::sort(copy.begin(), copy.end(), [this, compare = std::move(compare)](std::size_t lhs, std::size_t rhs) {
    return compare(dense[lhs], dense[rhs]); // 自定义比较函数
});

其中 compare 函数是用户提供的比较函数，copy 数组最初是一个索引数组，表示密集数组中的元素原始位置，排序后，copy 数组定义了元素在排序后的位置映射

• 例如，如果密集数组中的元素 [10, 30, 20] 按升序排序后为 [10, 20, 30]，那么 copy 的内容将是 [0, 2, 1]，表示原始第 0 个元素排在第 0 位，第 2 个元素排在第 1 位，第 1 个元素排在第 2 位

最后，我们需要应用排列数组，具体来说就是遍历排列数组，按照其定义的顺序，将 密集数组 和 稀疏数组 中的元素移动到正确的位置，其核心是 “循环（cycles）检测”，这是通过追踪每个元素到其最终位置的跳转来实现的

for(std::size_t pos = 0, length = copy.size(); pos < length; ++pos) {
    auto curr = pos;
    auto next = copy[curr];
 
    while(curr != next) {
        // 在稀疏数组和密集数组中交换元素
        swap(dense[curr], dense[next]);                       // 密集数组交换
        swap(sparse[dense[curr]], sparse[dense[next]]);       // 稀疏数组同步更新
 
        copy[curr] = curr;  // 标记当前位置已完成
        curr = next;
        next = copy[curr];  // 跳转到下一个位置
    }
}

这里的运行逻辑是

• for 循环遍历每个位置 pos
  如果当前元素已经完成排序（copy[pos] == pos），直接跳过
• 对于每个未完成排序的元素 启动 while 循环追踪排列路径，将路径上的所有元素移到正确位置，直到回到起点位置，完成一个循环

由于每个元素只被移动一次，且 for 循环跳过已经完成的元素，因此不会有重复处理，最后的复杂度是 $O(N + N\log N )$

假设稀疏集合的密集数组为 [A, B, C, D]，目标排序后为 [D, B, A, C]，排列数组 copy 为 [3, 1, 0, 2]，表示

• 原位置 0 (A) → 位置 3
• 原位置 1 (B) → 位置 1
• 原位置 2 (C) → 位置 0
• 原位置 3 (D) → 位置 2

整个过程将如下

1. 从 pos = 0 开始，发现 copy[0] = 3，说明这个位置还没有完成排序
   • 将 A 移到位置 3
   • 从位置 3 取出 D，移到位置 2
   • 从位置 2 取出 C，移到位置 0
   • 闭环完成
2. pos = 1，发现 copy[1] = 1
   • 元素 B 已在正确位置，跳过
3. pos = 2，发现 copy[2] = 0
   • 元素已在正确位置，跳过
4. pos = 3，发现 copy[3] = 2
   • 元素已在正确位置，跳过

最终所有元素到达正确位置，总操作次数等于元素个数 $N$，复杂度为 $O(N)$，这是因为每个元素只被处理一次，while 循环的复杂度不会叠加

混合方法

混合原地排序和排列的思路结合了两种方法的优点

1. 使用原地排序的密集数组减少内存开销
2. 利用排列思想优化关联数组的更新成本

这种方法特别适合稀疏集合的复杂场景，因为它利用了稀疏集合本身的结构特点，将稀疏数组作为标记机制，避免了额外的支持数组，从而实现了更高效的排序

它的核心思路是

1. 排序 密集数组
   直接对 密集数组 进行排序，使用 std::sort 等高效的标准排序算法，排序后的 密集数组 决定了实体的排列顺序
2. 利用 稀疏数组 追踪元素
   稀疏数组 本身可以充当支持数组的角色，用于记录哪些元素已经被处理，不再需要额外的内存分配
3. 更新关联数组 对于 稀疏集 中的其他 密集数组，通过 稀疏数组 索引直接进行调整，每次调整仅限于必要的数组，避免冗余操作

具体实现如下

template<typename Compare>
void sort(Compare compare) {
    // 原地排序密集数组
    std::sort(dense.begin(), dense.end(), std::move(compare));
 
    // 遍历密集数组，更新关联数组
    for (std::size_t pos = 0, end = dense.size(); pos < end; ++pos) {
        auto curr = pos;
        auto next = sparse[dense[curr]];
 
        while (curr != next) {
            // 调整关联数组中的元素
            adjust(dense[curr], dense[next]);
 
            // 更新稀疏数组，标记当前位置已完成
            sparse[dense[curr]] = curr;
 
            // 跳转到下一个元素
            curr = next;
            next = sparse[dense[curr]];
        }
    }
}

其中的 adjust 函数用于更新关联数组中的元素，每次交换时，根据 稀疏数组 的索引对其他 密集数组 进行同步更新

void adjust(Entity lhs, Entity rhs) {
    std::swap(another_dense[sparse[lhs]], another_dense[sparse[rhs]]);
    // 如果有更多的关联数组，可以重复类似的逻辑
    std::swap(yet_another_dense[sparse[lhs]], yet_another_dense[sparse[rhs]]);
}

可以看到在这种情况下，我们不再需要 copy 数组作为辅助，我们直接使用 稀疏数组 来跟踪哪些位置已经是正确的