最近在整理排序优化相关的资料时一个标题吸引了我Dtsort: A decision-tree based stable sort that beats std::stable_sort。这句话对 C 开发者来说相当有冲击力。原因很简单std::stable_sort几乎是稳定排序的“默认答案”稳定、复杂度上限明确、实现经过长期调优。现在突然有人说自己用decision-tree 决策树做稳定排序还能打败标准库实现很多人第一反应是真的假的我倾向于先把问题拆开。不要急着背“决策树排序就是好”或“标准库不可战胜”而是先弄清楚稳定排序的性能成本在哪里、决策树到底改变了哪一步、以及一个“能打的排序”需要在什么数据分布和工程条件下成立。这篇文章就按这个思路来讲。读完你能得到三样东西理解std::stable_sort为什么比std::sort更容易成为性能瓶颈。理解 decision-tree 参与排序时真正改变的算法是哪个环节。一个可运行的“决策树 rank 稳定收集”最小示例以及一套验证排序方案是否真的更快的实验框架。1. 稳定排序为什么值得重新做一遍先看一个实际场景。假设你有一批订单要求先按城市分组组内按时间从早到晚排序。最常见的实现是先按时间排序再按城市执行稳定排序。std::sort不会保证相等城市之间的相对顺序不变所以第二次排序如果还用std::sort第一次排序中“时间有序”的组内关系很可能被打乱。这时候你只有两条路把城市和时间放进同一个比较器一次排序完成代价是每一次比较都更“重”。用稳定排序先按时间排再按城市稳定排。稳定排序的价值就在这里它帮你把多个排序键拆成多阶段处理而不必每次比较都同时比较所有字段。实际业务里很多报表、榜单、分页列表的排序逻辑默认就是要稳定的。稳定排序并不是一个锦上添花的选项而是一个很常见的需求。因此如果有人能设计出一种稳定排序在特定数据分布下明显快于std::stable_sort那么它不只是“又一种排序函数”而是在降低一种真实存在的开发成本。不过也要先说清楚我很反感没有附带 benchmark 口径的“beats”。任何排序库的排名都依赖数据集、对象拷贝成本、比较器开销、缓存行为、内存分配情况。Dtsort 能不能赢必须放在特定条件里验证。本文更值得关注的是它把稳定排序的成本重新拆了一遍让我们有机会思考过去被默认的东西是否合理。2. 稳定排序的成本到底高在哪2.1 “稳定”不是免费的从抽象语义看一个排序算法稳定是指如果两个元素的关键字相等排序后它们的相对顺序与排序前一致。不稳定排序只关注关键字大小不承诺相等元素顺序。这个承诺带来的直接影响是算法不能随便使用快速排序这类原地交换算法。std::stable_sort的标准实现通常基于归并排序思路分裂、递归排序、归并。归并过程中要保证左边组和右边组的关键字相等时左边组的元素仍然先出现。这会产生代价需要额外的临时内存或更复杂的原地归并策略。元素被复制/移动的次数通常比原地快排更多。如果临时内存不足主流实现会退化为一些更精致的原地归并时间复杂度可能从很好的水平退化到更差的状态。C 标准对std::stable_sort复杂度有描述在内存充足的主流实现中比较复杂度可以达到 O(N log N)若不能分配临时内存常见实现可能退化到 O(N log²N) 级别。也就是说稳定排序的最坏表现并不是一句 O(N log N) 就能掩盖的。2.2 每个排序算法都有“隐藏预算”一个排序方案在真实机器上的开销不止是复杂度表达式里的比较次数。现实中至少还要看元素移动的成本。比较器本身的成本。内存访问顺序和缓存局部性。分支预测失败的代价。是否分配临时内存。输入是否有重复键、是否接近有序。std::stable_sort选择归并排序路线本质上是把“稳定”这个约束放进了算法骨架里。优点是稳定性和复杂度都有保障缺点是它对元素的移动往往比std::sort更重尤其是当对象体积大、移动开销高的时候。维度std::sortstd::stable_sort稳定性不保证保证相等元素顺序典型实现内省排序/快速排序归并排序空间占用栈级别 O(log N)通常需要 O(N) 临时空间排序对象轻量值类型、普通排序需要保持多键语义、报告类排序最大痛点相等元素顺序不可控移动/内存分配成本更高这也是为什么 Dtsort 这类项目有存在价值它希望在“稳定”这一点上找到一种不同成本结构的方案。3. 排序性能不是只有复杂度和比较次数在进一步讨论决策树之前还要敲掉一个常见误区排序快慢不完全等于比较次数多少。假设我们要排序一条记录数组每个记录有一个intkey 和一段比较昂贵的 payload。对于机器而言“比较两个 key”可能只是几条指令真正吃掉时间的是3.1 元素移动成本struct HeavyRecord { std::vectordouble data; std::string name; int key; };对HeavyRecord排序时交换两个元素可能要移动几百字节而排序算法通常假设“移动便宜、比较贵”因此会用大量移动来换取少量比较。如果对象不可平凡复制这种移动还会进一步放大。决策树思路有机会降低移动次数吗有机会。如果先用决策树把每个元素归到一个小桶或 rank 区间再在区间内做稳定排列相当于先把范围缩小避免大规模的无意义移动。3.2 分支可预测性排序里大量if (a b)分支预测失败时要停顿流水线。当 key 比较结果接近随机时分支预测器很难准确。反过来如果 key 分布有明显结构那么类似key 128这样的阈值判断往往有很高预测成功率执行起来远不止“少一次比较”那么简单。3.3 缓存与内存顺序线性扫描同一段连续内存通常比随机跳转访问快得多。稳定排序的归并阶段会把元素从一个临时缓冲区写回原数组这个过程虽然是线性的但会多一次额外读写。对超大数组来说内存带宽是真实瓶颈。所以一个优秀的排序方案必须综合考虑以上因素。std::stable_sort在通用场景里足够好不代表没有优化空间。Dtsort 标题里的 decision-tree最有可能优化的正是“减少比较次数 让分支更像查找路径”。4. Dtsort 的决策树到底要解决什么问题4.1 不要误解“用决策树排序”如果只是把任意两个元素的比较画成一棵决策树那并没有新意。算法理论里任何基于比较的排序都可以看成一棵决策树每条从根到叶子的路径对应一组比较结果叶子对应一种输出排列。经典的下界 Ω(N log N)也来自对决策树高度的分析。这说明只靠“把 if-else 写成树”并不能突破比较排序的下界。那 Dtsort 还能怎么做从标题和排序领域的演进方向来看更合理的理解是先用决策树对 key 做一次分类/预测把每个 key 映射到有序的 rank 桶或等价类再通过一个稳定收集阶段得到最终有序序列。换句话说决策树不是在回答“a 是否小于 b”而是在回答“你大概属于哪一个有序区域”。这个过程非常接近最近几年出现的“learned sort”思想对训练样本学习一棵决策树。排序时对每个 key 做一次决策树推理。推理结果作为 key 的 rank 或分桶依据。最后再通过稳定排序/计数排序把同一等价类内的元素按原顺序输出。关键在于第四步。只有第四步“稳定收集”设计合理整个方案才能称为stable sort。4.2 为什么 stable sort 特别适合决策树决策树输出的 rank 本身可以包含重复。例如大量记录的 key 都是 2、5、7那么决策树叶子可能只有三种。传统稳定排序需要在这三个 rank 值之间来回比较、归并而决策树方案可以先按 rank 分桶再在桶内做稳定输出。更强的点是如果桶的数量很小而且每个 key 的 rank 可以在 O(log K) 次比较内确定其中 K 是不同 key 的种数那么单条记录的“判断开销”就和 N 无关。当 N 远大于 K 时这就会比std::stable_sort那种 O(N log N) 的比较路径短得多。一个经典例子是对 1000 万个只取 16 个取值的记录做稳定排序。理论上完全可以用 stable counting sort 线性完成。但如果我们保留通用比较器只用决策树把 key 映射到 16 个 rank再稳定收集效果也更接近线性排序。Dtsort 的核心判断就在于在真实数据中key 并不总像随机数一样均匀且唯一而是经常存在大量重复和结构。既然有重复结构决策树就可以提前把这种结构编码进查询路径里。5. 最小实现决策树 rank 稳定收集的思路拆解下面用一个非常小的 Python 程序演示这个思路。它不是 Dtsort 本身而是把“决策树输出 rank 稳定收集”这条主链路拆给你看。5.1 代码示例稳定排序的常见场景先看 C 里的稳定排序需求场景。// 文件路径stable_scene.cpp #include algorithm #include iostream #include string #include vector struct Record { int group; int seq; }; int main() { std::vectorRecord v{ {2, 0}, {1, 0}, {2, 1}, {1, 1}, }; // 要求按 group 升序group 相同时保持输入顺序。 // group 相同且输入顺序已经有序这是稳定排序的典型语义。 std::stable_sort(v.begin(), v.end(), [](const Record a, const Record b) { return a.group b.group; }); for (const auto r : v) { std::cout r.group : r.seq \n; } return 0; }编译运行后输出1:0 1:1 2:0 2:1如果这里使用std::sort标准库并不保证输出一定是这个结果。很多工单、排序异常问题本质上就是有人把稳定排序换成了不稳定排序导致相等 key 的次序漂移。5.2 Python 最小演示tree rank stable collect接下来实现一个迷你的 stable decision-tree sort。假设 key 的取值只有 0 到 7。我们用一棵完全展开的二叉决策树把 key 映射成 rank。随后建立一个对应 rank 的桶列表按原顺序把元素放入桶内再按 rank 顺序合并。这个流程保证了“关键字少时先出”同时每个桶内部保持原始相对顺序。# 文件路径dtsort_lite.py from typing import List, Tuple def decision_rank(key: int) - int: 固定 key 域为 0..7 的决策树。 把一个 key 映射到它的排序 rank。 这里通过一个完全展开的 if-else 树来表示决策树 真实工程中决策树可以由样本训练得到也可以按 key 分布动态构建。 if key 4: if key 2: return 0 if key 1 else 1 return 2 if key 3 else 3 if key 6: return 4 if key 5 else 5 return 6 if key 7 else 7 def stable_tree_sort(items: List[Tuple[int, str]]) - List[Tuple[int, str]]: rank 桶 稳定收集 1. 先用决策树得到每个 key 的 rank 2. 遍历原始列表保持相对顺序放入桶 3. 按 rank 从小到大拼接得到稳定有序序列。 buckets: List[List[Tuple[int, str]]] [[] for _ in range(8)] for item in items: key, _ item rank decision_rank(key) buckets[rank].append(item) result: List[Tuple[int, str]] [] for bucket in buckets: result.extend(bucket) return result if __name__ __main__: data [ (3, rank3-0), (1, rank1-0), (2, rank2-0), (3, rank3-1), (0, rank0-0), (3, rank3-2), (5, rank5-0), ] output stable_tree_sort(data) print(output) # 快速验证key 本身有序 assert [k for k, _ in output] sorted(k for k, _ in data)5.3 运行结果执行python3 dtsort_lite.py预期输出[(0, rank0-0), (1, rank1-0), (2, rank2-0),
