排序

排序，对于某些子系统非常重要。排序图元渲染的调用，不透明对象从前向后渲染，对 GPU 性能有巨大影响，值得一做。同样，alpha 混合对象从后往前渲染，也有必要排序。按响度和采样位置排序音频通道，也能作为很好的优先级指标。

无论要对什么排序，都要先确认排序的对象，因为通常排序是一项高内存负载的任务。

真的必要吗？

有些算法看似需要数据有序，实则不用；有些则需要数据有序，但又看不太出来。做出任何错误举措前，最好先确认是否真的有必要。

游戏中，排序的常见用途之一是在渲染管线中。有些引擎程序员提议，将所有渲染调用按一个若干比特的键排序，该键是由深度、网格、材质、着色器、其他标志等（如是否 alpha 混合）组合而成。这样一来，渲染器就能在运行时调整排序，最大限度利用带宽。在排序渲染列表时，可以用常规排序算法来处理。但实际上，并不用排序 alpha 混合对象与不透明对象。所以很多情况下，可以直接采取第一步，将列表放入两个独立的桶中，总体上省掉一些工作。另外，排序算法也要谨慎选择。对于不透明物体，最重要的通常是：先按纹理排序，再按深度排序。但是，随着同一像素被多次覆盖，进而破坏填充率，情况可能会依破环程度而改变。如果是纹理上传的重要程度高于过度绘制 (overdraw)，那么对调用做基数排序或许会比较好。而对于 alpha 混合，只需要按深度排序，所以只要适用当前情况即可。另外，还要注意数据排序的准确程度。有些排序是稳定的，有些不稳定。不稳定的排序通常会快一些。对于模拟的范围，快速排序或合并排序通常缓慢但准确。如果是 $n$ 很大的离散区间，基数排序就难以超越。如果知道数值范围，那计数排序是一种非常快速的 two-pass 排序，如，按材质、着色器、其他输入缓冲索引等排序。

排序时，也要注意那些只能在某个范围进行部分排序的算法。如果只需要一个 $m$ 长的数组中最低（或最高）的 $n$ 个元素，可以用不同类型的算法找到第 $n$ 个元素作为枢轴，然后排序所有小于（或大于）它的元素。一些选择算法会带来数据的额外特征。比如，快速选择算法中，根据排序标准，第 $n$ 个元素会保留在第 $n$ 个位置。选择完成后，两边的所有元素在其子范围内都保持未排序状态，但根据其相对枢轴的方位，一定小于或大于枢轴。

假设有一组常规范围的元素，需要以两种不同的方式排序。可以用专门的比较函数一次性排序，也可以分层级排序。若整个范围的元素的任意子集的顺序不太重要，也能加以利用。此处仍用渲染队列举例。如果把排序分成不同的子排序，就有可能剖析排序的每个部分，或许就能发现有用的点。

当然也不需要自己实现算法。这里提出的大多数想法，STL 都已经实现过了，直接使用即可。例如，可以用 std::partial_sort 寻找和排序前 $n$ 个元素，用std::nth_element 寻找第 $n$ 个值，就跟排序了的容器一样。用 std::partition 和 std::stable_partition 根据某些准则，能有效地对某个范围的元素排序，并可以分成两个子范围。

了解这些算法的标准也很重要，因为像 erase/remove 这些简单操作，也可能会因为不自知的用法将整个数据打乱重排，因为它们会维持数据的有序状态。如果要给自己的工具集里添加新算法，那最好也实现自己版本的 remove，不去保证有序状态。代码 就是这样一个例子。

插入排序与并行归并排序

根据排序的目的，修改时也能执行排序。如果排序针对需要优先级的 AI 函数，那可以用插入排序，因为基础启发式的，通常会有完全正交的输入。如果输入是相关的，那么插入后再整表排序能保证有序，但基本没必要全排。

如果确实需要完整地排序，最好尝试倾向于并行的算法。归并排序和快速排序在某种程度上是串行的，它们开始和结束工作都位于单线程上，但也有些变体在多线程中工作良好。对于小数据集，有一些特殊的排序网络技术，可以比好的算法更快，只因为它们更适用于硬件。

针对平台排序

时刻记住，在面向数据开发中，必须先从数据中寻找信息，再决定怎样写代码。数据是什么样的？在渲染中，有大量数据，有不同的维度可用于排序。如果渲染器是按照网格、材质排序，以减少顶点和纹理上传，那数据看起来就是：有些渲染调用共享纹理数据，还有一些共享顶点数据。通过计算上传纹理、网格的时间；各自又需要上传多少额外信息；然后计算场景的总时间；就能知道先排序哪边了。不过大多数情况下，分析报告是唯一能够确定的方式。如果希望能快速剖析并获取反馈，或者游戏中有相当多的资源要剖析，以至于没有方案适合所有的情况，最后不得不允许运行时做调整。那最好有些灵活的排序标准，有时候甚至是必须的。好在它只是需要一点设置成本，就可以与任何不灵活的排序技术一样快。

基数排序是最快的串行排序。如果能做到，在第一轮中为不同值的数据生成一个起点列表，然后在第二轮中用这些数据执行操作，基数排序是相当快的。排序器可以根据译表将内容放入容器中，其中译表是一个为给定数据值返回偏移量的表。如果从一个已知的小的数值空间建列表，那基数排序可以非常快速地在第一轮就给出粗略的结果。之所以是串行，是因为它必须修改正在读取的表，以便更新下一个元素的偏移量，这些元素会被放进同一个桶里。如果有多个线程，让它们各自承担一部分工作，就会发现它们的吞吐量是非线性增长的，它们会争相在同一块内存上读写，而我们并不希望在排序算法中用上原子更新。

通过让每个排序器忽略它读到的超出其工作集的值，能让这个过程的最后阶段变为并行。也就意味着为了填充自己地桶，每个 worker 都会读完整个值集。但由于必须在不同线程上向临近的内存写入，仍有小概率出现非线性的性能问题。在 worker 收集元素的过程中，它可能正在为序列中的下一个基数生成计数，只需在下一轮之前求和，就能减轻每个 worker 在整个集合上迭代的成本。

如果数据相对复杂，无法使用基数排序，那可以考虑归并排序和快速排序，但如果在编译期就知道可排序缓冲区的长度，那就还有其他替代方案，如排序网络。归并排序本身不是并发的算法，但很多前期归并能够并行，只有最后是串行的。通过快速预解析要归并的数据，就能用两个线程而非一个，从两端开始直至最终完成（需确保合并的数据不会耗尽）。尽管快速排序也不是并发算法，但每个子阶段都可以并行。它们本质上是串行的，但可以变成部分可并行的算法，延迟为 $O(\log{n})$。

n 足够小时，原地冒泡排序通常也不错。它简单到很难写错，而且由于需要交换的数量很少，优化排序的功夫可以用在其他地方。重写这类简单的代码时，还有一种说法，内联实现能小到整个数据和算法都可以放进缓存。这么小的 n，冒泡排序的低效带来的负面影响微乎其微，因此基本没人会反对。某些情况下，减少指令本身或许要比操作效率更重要，因为指令被逐出缓存的开销，可能比优化算法省下的还多。跟以前一样，测一下就知道了。

如果读者已经接触过面向数据开发，一定处理过排序有 n 个元素的表的变换。用到的算法不一定要优于冒泡排序，但是注意，用更好的算法并不需要额外的开发时间，因为数据已经是正确的格式了。面向数据的开发自然会引导我们复用好的算法。

寻找正确的算法时，学到的东西远比课程作业中所介绍的更多，我们能探究到更深奥的形式。对于排序，有时想要一个总是在相同时间内排序的算法，这样的话，标准的快速排序、基数排序、冒泡排序等都无法胜任。归并排序通常性能很不错，但为了确保时间真正稳定，可能还需借助于排序网络。

排序网络是以静态的方式实现。它们有输入数据，并在输出最终结果之前，对输入数据的数值对执行交换函数（必要的话）。最简单的排序网络是两个输入。

A[r] & [r] [dr] & [r] & A'
B[r] & [r] [ur] & [r] & B'

如果输入的值符合次序，则排序交叉什么都不做；如果不符合，那么排序交叉就互换数值；这样就能实现无分支写入。

a' <= MAX(a, b)
b' <= MIN(a, b)

<>

这种操作在各类硬件上都很快。对于不同平台和数据类型，MAX 和 MIN 函数需要不同的实现，但通常来讲，无分支的代码比有分支的快一些。当前大多数编译器中，如果可以，MAX 和 MIN 函数都会被提升为内部函数(intrinsic)，但我们可能需要微调一下数据，使其值成为键的一部分，所以它会与键一起排序。

引入更多元素：

A[r] & [r] [ddr] & [r] [dr] & [r] & [r] & A'
B[r] & [r] [ddr] & [r] [ur] & [r] [dr]& [r] & B'
C[r] & [r] [uur] & [r] [dr] & [r] [ur] & [r] & C'
D[r] & [r] [uur] & [r] [ur] & [r] & [r] & D'

可以看到，这里的关键路径并不长（共只有三个阶段），第一阶段：并发排序 A/C 和 B/D 对。第二阶段：排序 A/B 和 C/D 对。最后：排序 B/C 对。这些都是无分支函数，因此在整个数据处理序列里，性能有规律可循。有了这样一个有规律的性能曲线，就可以在排序时长易变的地方应用它，如对渲染的子模块执行即时(just-in-time)排序。如果对可渲染数据用了基数排序，就可以在任何最终需要有序的地方使用网络排序，因为可以保证时间稳定。

a’ <= MAX(a,c)
b’ <= MIN(b,d)
c’ <= MAX(a,c)
d’ <= MIN(b,d)
a’’ <= MAX(a’,b’)
b’’ <= MIN(a’,b’)
c’’ <= MAX(c’,d’)
d’’ <= MIN(c’,d’)
b’’’ <= MIN(b’’,c’’)
c’’’ <= MAX(b’’,c’’)

<>

排序网络有点像是低阶断言(predication)，是处理条件计算的无分支形式。因为这里用到的是min / max函数，而非条件交换。所以涉及到单个元素的实际排序时，同样具备优势。鉴于排序网络在某些实现上比基数排序更快，因此，对于某些类型的计算，低阶断言，甚至是长链的低阶断言，都要比像借由分支节省处理时间的代码快。正是这样一个例子存在于 Pitfalls of Object Oriented Programming [#!AlbrechtTony!#]的介绍中，结论是惰性求值比通过它尝试避免的工作开销更大。还没有确凿的证据，但我相信很多 AI 代码也能从中受益，因为即便不确定是否需要，收集信息也很明智，收集可能比确定不用收集要快。例如，确认某人是否在玩家视野中，或够近，或很小，不管是不是每一个 AI 都需要这样的信息，我们为所有 AI 执行该检查。