尧图网站建设 
ClickHouse 中的 pdqsortPattern-Defeating Quicksort 排序算法原理与集成解析【免费下载链接】ClickHouseClickHouse® is a real-time analytics database management system项目地址: https://gitcode.com/GitHub_Trending/cli/ClickHouse本文以 ClickHouse 仓库中contrib/pdqsort目录下的 pdqsort 官方说明文档 为主体系统讲解 Pattern-Defeating Quicksort模式击败快排这一排序算法的设计目标、三大情形最优/平均/最坏下的核心机制及其数学依据并结合 pdqsort.h 源码与 ClickHouse 中的真实调用点Gini 系数聚合函数等展示这个算法在 ClickHouse 中的落地方式。读完后你既能理解 pdqsort 相比std::sort的改进点也能在自己的代码中正确替换使用它。pdqsort 是什么一句话定位与复杂度指标pdqsortPattern-Defeating Quicksort模式击败快排是 Orson Peters 于 2015 年发布的单头文件排序库如 contrib/pdqsort/readme.md 所述它的目标是同时拿到三样东西随机化快排的快速平均情形堆排序的快速最坏情形保证 O(n log n)对具有特定模式的输入已排序、逆序、大量重复、近乎有序达到线性时间 O(n)。它是 David Musser introsort 的扩展与改进整个代码以 zlib 许可证发布许可证全文见 contrib/pdqsort/license.txt实现本体是单头文件 contrib/pdqsort/pdqsort.h共约 740 行这也是它能被 ClickHouse 以contrib子模块形式直接集成、#include pdqsort.h即可使用的原因。原文档给出的复杂度指标表直接继承自 readme最优平均最坏额外空间稳定确定性nn log nn log nlog n否是确定性Deterministic值得注意与随机快排不同pdqsort 的 pivot 选择是确定性的遇到坏分区时靠确定性打乱元素打破模式而不是随机数因此同一输入总是得到同一排序过程和结果——这对可复现的调试与测试是友好的。用法std::sort 的 Drop-in 替换原文档给出的使用方式非常直接pdqsort是std::sort的直接替代品把std::sort(a, b)改成pdqsort(a, b)即可比较函数语义完全一致非稳定排序。完整的公开 API 见 pdqsort.h 尾部// 基本用法std::sort 的替换 pdqsort(begin, end); pdqsort(begin, end, comp); // 自定义比较函数 // 显式要求无分支branchless分区 pdqsort_branchless(begin, end); pdqsort_branchless(begin, end, comp); // 尝试排序若数据接近有序且代价可控则排完并返回 true // 否则中止并返回 false不会把数据弄乱到不可恢复后继续见下文实现细节 pdqsort_try_sort(begin, end); pdqsort_try_sort_branchless(begin, end);自动委托 branchless 版本的逻辑在 pdqsort 入口函数 中可以看到当满足以下三个条件时pdqsort会自动以 branchless 模式运行编译标准为 C11 及以上__cplusplus 201103L被排序类型是算术类型std::is_arithmetic例如int比较函数未显式给出或就是std::less/std::greater由is_default_compare特征结构判定见 pdqsort.h。这一自动检测正是原文档中如果你使用 C11、被排序类型是算术类型、比较函数是std::less/std::greaterpdqsort 会自动委托给pdqsort_branchless的源码依据。关键调优参数pdqsort.h 中的常数一览原文档只定性描述了算法策略而 pdqsort.h 头部的枚举常量 把这些策略量化成了具体参数理解它们是读懂实现的关键常量值含义insertion_sort_threshold24小于该规模的分区改用插入排序ninther_threshold128大于该规模时 pivot 选择从 median-of-3 升级为 Tukey 九分中值pseudomedian of 9partial_insertion_sort_limit8乐观插入排序允许的最大元素移动次数超过即放弃这是最优情形线性时间的关键block_size64BlockQuicksort 索引缓冲块大小必须是 8 的倍数循环展开且 256unsigned char可存cacheline_size64缓存行大小假设用于缓冲区对齐try_sort_iterations3pdqsort_try_sort允许的重试迭代次数注意一个与原文档Visualization一节相呼应的细节文档中提到演示动画里把插入排序的切换阈值降到了 8 个元素以便观看而生产代码中该阈值是 24——文档的 8 只是可视化的临时调参不要与源码默认值混淆。pivot 选择的对应实现在 pdqsort_loop小于 128 个元素时用sort3取三个位置的中位数median-of-3达到 128 以上时先做 4 组sort3再取伪中位数Tukeys ninther以在长数组上获得更稳的 pivot。最优情形两个机制换来 O(n)原文档The best case一节指出pdqsort 对以下几类输入达到线性时间严格升序/降序、全部元素相等、几乎有序且只有一个元素放错位置。背后是两个独立机制均可在源码中逐行对应。机制一等值元素的智能分区对于大量重复元素的输入pdqsort 采用一个始终把等于 pivot 的元素放进右分区的分区方案。当为某个右分区选择新 pivot 时会把它与前一个分区的最大元素比较若两者相等则可以推导出该分区内不存在小于 pivot 的元素。此时切换策略——改用 partition_left 把等值元素划入左分区且由于左分区整体等于 pivot、天然已有序直接跳过对它的递归。这段判断位于 pdqsort_loop 主循环if (!leftmost !comp(*(begin - 1), *begin)) { begin partition_left(begin, end, comp) 1; continue; }这就是全相等输入能线性完成的原理每一层只处理一个分区。机制二无交换时的乐观插入排序对已排序/近乎有序输入pdqsort 在每次分区后检查本次分区是否发生过交换。分区函数partition_right_branchless会返回一个already_partitioned标志见 实现若第一个待交换的左右指针是同一个元素说明序列本来就分好了。若没做交换且分区相当均衡pdqsort 就乐观地尝试插入排序但用 partial_insertion_sort 严格限制代价——一旦累计移动次数超过partial_insertion_sort_limit8 次立即返回false放弃回到正常快排流程继续if (already_partitioned partial_insertion_sort(begin, pivot_pos, comp) partial_insertion_sort(pivot_pos 1, end, comp)) return;只允许常数次移动正是严格有序/只差一个元素输入能 O(n) 完成、而真正乱序数据不会被拖慢的关键。原文档说检测模式的开销小到落在测量误差之内指的就是这些廉价检查几个比较和一个布尔标志。平均情形median-of-3 BlockQuicksort 的无分支加速在没有模式可探测的数据上pdqsort 本质上是一个用 median-of-3 选 pivot、小数组切换到插入排序的快排。而它在大数组原文档说 1000 个元素以上上对传统快排有显著加速来自 Stefan Edelkamp 与 Armin Weiss 的 BlockQuicksort 技术核心思路是绕过分支预测器——先用一小段block_size 64整个位于 L1 缓存内索引缓冲无分支地记录站错边的元素下标再批量交换。原文档给出的伪代码buffer_num 0; buffer_max_size 64; for (int i 0; i buffer_max_size; i) { // With branch: if (elements[i] pivot) { buffer[buffer_num] i; buffer_num; } // Without: buffer[buffer_num] i; buffer_num (elements[i] pivot); }对照 partition_right_branchless 的实际实现可以看到完全一致的无分支填充技巧并且做了 8 路循环展开for (unsigned char i 0; i block_size;) { offsets_l[num_l] i; num_l !comp(*it, pivot); it; // ... 共 8 行展开每次处理一个元素 }两个工程细节值得注意缓冲区声明为unsigned char offsets_l_storage[block_size cacheline_size]并通过 align_cacheline 按 64 字节对齐避免左右两个索引缓冲共享缓存行造成伪共享批量交换由 swap_offsets 完成在交换数量多的情况下用搬移move链替代逐对iter_swap减少移动次数。但要再次强调原文档给出的前提这套加速只有当比较函数本身是无分支branchless时才有收益——如果比较逻辑内部充满分支省掉分区循环的分支也无济于事。这也是 pdqsort 提供显式pdqsort_branchless入口、并仅在算术类型 默认比较器时自动启用的原因。最坏情形确定性打乱模式 堆排序兜底快排这类基于分区的算法天然害怕模式数据坏 pivot 会让比较几乎不产生进展而真实数据里模式无处不在。传统解法有两条路线——快排随机化 pivot最坏仍可能退化为平方级只是概率极小与 introsort 的确定性路线递归深度过大时切换到 O(n log n) 有保证的堆排序。原文档说明 pdqsort 取混合路线遇到坏分区时确定性地打乱两个分区中固定位置的若干元素以此打破大量模式坏分区次数超过log(n)后整体切换堆排序保证 O(n log n)。源码实现完整对应了这两步pdqsort_loop// 坏分区判定pivot 落点不在 1/8 分位与 7/8 分位之间 bool highly_unbalanced l_size size / 8 || r_size size / 8; if (highly_unbalanced) { // 坏分区预算耗尽切换堆排序保证 O(n log n) if (--bad_allowed 0) { std::make_heap(begin, end, comp); std::sort_heap(begin, end, comp); return; } // 否则在左分区的 0、l/4、pivot-1、pivot-l/4 等固定位置交换元素 // 分区规模超过 ninther_threshold 时再多加 4 个交换点即打乱 4 个元素 ... }其中bad_allowed的初值由 入口函数 传入恰好是log2(end - begin)与原文档坏分区超过 log(n) 次则切换堆排序一致。为什么是 1/812.5%原文档给出了一个漂亮的量化论证完整继承如下快排最坏运行时间的上界可由递推式近似相差常数因子T(n, p) n T(p(n-1), p) T((1-p)(n-1), p)其中n为元素数p为分区后 pivot 所在的百分位。T(n, 1/2)是快排最佳情形。在现代系统上堆排序实测约为快排的 1.82 倍慢原文档的测量结论。因此选取p使得T(n, 1/2) / T(n, p) ≈ 1.9随n增大才能保证只有堆排序真的更快时才会切换过去避免为了安全牺牲速度。p 1/8是该方程的近似解且size / 8在所有平台上都可以用一次位移廉价计算——这正是源码中l_size size / 8的由来。ClickHouse 中 pdqsort 的实际集成ClickHouse 把 pdqsort 放在contrib/pdqsort子模块中并以头文件包含的方式直接集成到业务代码里。仓库中的真实调用点包括Gini 系数聚合函数AggregateFunctionGini.cpp 在计算基尼系数需要先按值排序构造洛伦兹曲线时执行pdqsort(array.begin(), array.end())头部通过#include pdqsort.h引入第 17 行src/Functions/array/arrayNormalizedGini.cpp等数组函数也使用同一模式。这属于典型的算术类型 默认比较器场景会走自动委托的 branchless 路径时序聚合函数AggregateFunctionTimeseriesBase.h 的源码注释明确记录了输出阶段对稀疏桶的两种遍历策略——稠密时全区间扫描哈希表、稀疏时收集后比较排序并说明经基准测试比较排序即 pdqsort优于基数排序因此稀疏路径采用::sortpdqsort。从源码结构看ClickHouse 选择 pdqsort 的典型场景是聚合函数/数组函数内部对数值向量做一次性原地排序单头文件零依赖、确定性、对分析型负载常见的含大量重复值的数值列有等值优化的额外收益这与 pdqsort 的设计目标模式数据上的表现高度吻合。小结pdqsort 用等值智能分区与受控的乐观插入排序两个机制把已排序、逆序、全相等、近乎有序这几类模式输入降到线性时间平均情形是 median-of-3大数组升级为 ninther快排并用BlockQuicksort 的无分支索引缓冲64 元素、L1 缓存内、缓存行对齐在比较函数无分支时显著提升大数组性能最坏情形采用确定性打乱固定位置元素打破模式坏分区超过log2(n)次则整体回退堆排序1/8分位阈值来自T(n,1/2)/T(n,p) ≈ 1.9的量化论证使用上它就是std::sort的直接替换API 见 contrib/pdqsort/pdqsort.hClickHouse 已在 Gini 系数等聚合/数组函数中实际采用。【免费下载链接】ClickHouseClickHouse® is a real-time analytics database management system项目地址: https://gitcode.com/GitHub_Trending/cli/ClickHouse创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 ClickHouse 中的 pdqsort：Pattern-Defeating Quicksort 排序算法原理与集成解析
ClickHouse 中的 pdqsortPattern-Defeating Quicksort 排序算法原理与集成解析【免费下载链接】ClickHouseClickHouse® is a real-time analytics database management system项目地址: https://gitcode.com/GitHub_Trending/cli/ClickHouse本文以 ClickHouse 仓库中contrib/pdqsort目录下的 pdqsort 官方说明文档 为主体系统讲解 Pattern-Defeating Quicksort模式击败快排这一排序算法的设计目标、三大情形最优/平均/最坏下的核心机制及其数学依据并结合 pdqsort.h 源码与 ClickHouse 中的真实调用点Gini 系数聚合函数等展示这个算法在 ClickHouse 中的落地方式。读完后你既能理解 pdqsort 相比std::sort的改进点也能在自己的代码中正确替换使用它。pdqsort 是什么一句话定位与复杂度指标pdqsortPattern-Defeating Quicksort模式击败快排是 Orson Peters 于 2015 年发布的单头文件排序库如 contrib/pdqsort/readme.md 所述它的目标是同时拿到三样东西随机化快排的快速平均情形堆排序的快速最坏情形保证 O(n log n)对具有特定模式的输入已排序、逆序、大量重复、近乎有序达到线性时间 O(n)。它是 David Musser introsort 的扩展与改进整个代码以 zlib 许可证发布许可证全文见 contrib/pdqsort/license.txt实现本体是单头文件 contrib/pdqsort/pdqsort.h共约 740 行这也是它能被 ClickHouse 以contrib子模块形式直接集成、#include pdqsort.h即可使用的原因。原文档给出的复杂度指标表直接继承自 readme最优平均最坏额外空间稳定确定性nn log nn log nlog n否是确定性Deterministic值得注意与随机快排不同pdqsort 的 pivot 选择是确定性的遇到坏分区时靠确定性打乱元素打破模式而不是随机数因此同一输入总是得到同一排序过程和结果——这对可复现的调试与测试是友好的。用法std::sort 的 Drop-in 替换原文档给出的使用方式非常直接pdqsort是std::sort的直接替代品把std::sort(a, b)改成pdqsort(a, b)即可比较函数语义完全一致非稳定排序。完整的公开 API 见 pdqsort.h 尾部// 基本用法std::sort 的替换 pdqsort(begin, end); pdqsort(begin, end, comp); // 自定义比较函数 // 显式要求无分支branchless分区 pdqsort_branchless(begin, end); pdqsort_branchless(begin, end, comp); // 尝试排序若数据接近有序且代价可控则排完并返回 true // 否则中止并返回 false不会把数据弄乱到不可恢复后继续见下文实现细节 pdqsort_try_sort(begin, end); pdqsort_try_sort_branchless(begin, end);自动委托 branchless 版本的逻辑在 pdqsort 入口函数 中可以看到当满足以下三个条件时pdqsort会自动以 branchless 模式运行编译标准为 C11 及以上__cplusplus 201103L被排序类型是算术类型std::is_arithmetic例如int比较函数未显式给出或就是std::less/std::greater由is_default_compare特征结构判定见 pdqsort.h。这一自动检测正是原文档中如果你使用 C11、被排序类型是算术类型、比较函数是std::less/std::greaterpdqsort 会自动委托给pdqsort_branchless的源码依据。关键调优参数pdqsort.h 中的常数一览原文档只定性描述了算法策略而 pdqsort.h 头部的枚举常量 把这些策略量化成了具体参数理解它们是读懂实现的关键常量值含义insertion_sort_threshold24小于该规模的分区改用插入排序ninther_threshold128大于该规模时 pivot 选择从 median-of-3 升级为 Tukey 九分中值pseudomedian of 9partial_insertion_sort_limit8乐观插入排序允许的最大元素移动次数超过即放弃这是最优情形线性时间的关键block_size64BlockQuicksort 索引缓冲块大小必须是 8 的倍数循环展开且 256unsigned char可存cacheline_size64缓存行大小假设用于缓冲区对齐try_sort_iterations3pdqsort_try_sort允许的重试迭代次数注意一个与原文档Visualization一节相呼应的细节文档中提到演示动画里把插入排序的切换阈值降到了 8 个元素以便观看而生产代码中该阈值是 24——文档的 8 只是可视化的临时调参不要与源码默认值混淆。pivot 选择的对应实现在 pdqsort_loop小于 128 个元素时用sort3取三个位置的中位数median-of-3达到 128 以上时先做 4 组sort3再取伪中位数Tukeys ninther以在长数组上获得更稳的 pivot。最优情形两个机制换来 O(n)原文档The best case一节指出pdqsort 对以下几类输入达到线性时间严格升序/降序、全部元素相等、几乎有序且只有一个元素放错位置。背后是两个独立机制均可在源码中逐行对应。机制一等值元素的智能分区对于大量重复元素的输入pdqsort 采用一个始终把等于 pivot 的元素放进右分区的分区方案。当为某个右分区选择新 pivot 时会把它与前一个分区的最大元素比较若两者相等则可以推导出该分区内不存在小于 pivot 的元素。此时切换策略——改用 partition_left 把等值元素划入左分区且由于左分区整体等于 pivot、天然已有序直接跳过对它的递归。这段判断位于 pdqsort_loop 主循环if (!leftmost !comp(*(begin - 1), *begin)) { begin partition_left(begin, end, comp) 1; continue; }这就是全相等输入能线性完成的原理每一层只处理一个分区。机制二无交换时的乐观插入排序对已排序/近乎有序输入pdqsort 在每次分区后检查本次分区是否发生过交换。分区函数partition_right_branchless会返回一个already_partitioned标志见 实现若第一个待交换的左右指针是同一个元素说明序列本来就分好了。若没做交换且分区相当均衡pdqsort 就乐观地尝试插入排序但用 partial_insertion_sort 严格限制代价——一旦累计移动次数超过partial_insertion_sort_limit8 次立即返回false放弃回到正常快排流程继续if (already_partitioned partial_insertion_sort(begin, pivot_pos, comp) partial_insertion_sort(pivot_pos 1, end, comp)) return;只允许常数次移动正是严格有序/只差一个元素输入能 O(n) 完成、而真正乱序数据不会被拖慢的关键。原文档说检测模式的开销小到落在测量误差之内指的就是这些廉价检查几个比较和一个布尔标志。平均情形median-of-3 BlockQuicksort 的无分支加速在没有模式可探测的数据上pdqsort 本质上是一个用 median-of-3 选 pivot、小数组切换到插入排序的快排。而它在大数组原文档说 1000 个元素以上上对传统快排有显著加速来自 Stefan Edelkamp 与 Armin Weiss 的 BlockQuicksort 技术核心思路是绕过分支预测器——先用一小段block_size 64整个位于 L1 缓存内索引缓冲无分支地记录站错边的元素下标再批量交换。原文档给出的伪代码buffer_num 0; buffer_max_size 64; for (int i 0; i buffer_max_size; i) { // With branch: if (elements[i] pivot) { buffer[buffer_num] i; buffer_num; } // Without: buffer[buffer_num] i; buffer_num (elements[i] pivot); }对照 partition_right_branchless 的实际实现可以看到完全一致的无分支填充技巧并且做了 8 路循环展开for (unsigned char i 0; i block_size;) { offsets_l[num_l] i; num_l !comp(*it, pivot); it; // ... 共 8 行展开每次处理一个元素 }两个工程细节值得注意缓冲区声明为unsigned char offsets_l_storage[block_size cacheline_size]并通过 align_cacheline 按 64 字节对齐避免左右两个索引缓冲共享缓存行造成伪共享批量交换由 swap_offsets 完成在交换数量多的情况下用搬移move链替代逐对iter_swap减少移动次数。但要再次强调原文档给出的前提这套加速只有当比较函数本身是无分支branchless时才有收益——如果比较逻辑内部充满分支省掉分区循环的分支也无济于事。这也是 pdqsort 提供显式pdqsort_branchless入口、并仅在算术类型 默认比较器时自动启用的原因。最坏情形确定性打乱模式 堆排序兜底快排这类基于分区的算法天然害怕模式数据坏 pivot 会让比较几乎不产生进展而真实数据里模式无处不在。传统解法有两条路线——快排随机化 pivot最坏仍可能退化为平方级只是概率极小与 introsort 的确定性路线递归深度过大时切换到 O(n log n) 有保证的堆排序。原文档说明 pdqsort 取混合路线遇到坏分区时确定性地打乱两个分区中固定位置的若干元素以此打破大量模式坏分区次数超过log(n)后整体切换堆排序保证 O(n log n)。源码实现完整对应了这两步pdqsort_loop// 坏分区判定pivot 落点不在 1/8 分位与 7/8 分位之间 bool highly_unbalanced l_size size / 8 || r_size size / 8; if (highly_unbalanced) { // 坏分区预算耗尽切换堆排序保证 O(n log n) if (--bad_allowed 0) { std::make_heap(begin, end, comp); std::sort_heap(begin, end, comp); return; } // 否则在左分区的 0、l/4、pivot-1、pivot-l/4 等固定位置交换元素 // 分区规模超过 ninther_threshold 时再多加 4 个交换点即打乱 4 个元素 ... }其中bad_allowed的初值由 入口函数 传入恰好是log2(end - begin)与原文档坏分区超过 log(n) 次则切换堆排序一致。为什么是 1/812.5%原文档给出了一个漂亮的量化论证完整继承如下快排最坏运行时间的上界可由递推式近似相差常数因子T(n, p) n T(p(n-1), p) T((1-p)(n-1), p)其中n为元素数p为分区后 pivot 所在的百分位。T(n, 1/2)是快排最佳情形。在现代系统上堆排序实测约为快排的 1.82 倍慢原文档的测量结论。因此选取p使得T(n, 1/2) / T(n, p) ≈ 1.9随n增大才能保证只有堆排序真的更快时才会切换过去避免为了安全牺牲速度。p 1/8是该方程的近似解且size / 8在所有平台上都可以用一次位移廉价计算——这正是源码中l_size size / 8的由来。ClickHouse 中 pdqsort 的实际集成ClickHouse 把 pdqsort 放在contrib/pdqsort子模块中并以头文件包含的方式直接集成到业务代码里。仓库中的真实调用点包括Gini 系数聚合函数AggregateFunctionGini.cpp 在计算基尼系数需要先按值排序构造洛伦兹曲线时执行pdqsort(array.begin(), array.end())头部通过#include pdqsort.h引入第 17 行src/Functions/array/arrayNormalizedGini.cpp等数组函数也使用同一模式。这属于典型的算术类型 默认比较器场景会走自动委托的 branchless 路径时序聚合函数AggregateFunctionTimeseriesBase.h 的源码注释明确记录了输出阶段对稀疏桶的两种遍历策略——稠密时全区间扫描哈希表、稀疏时收集后比较排序并说明经基准测试比较排序即 pdqsort优于基数排序因此稀疏路径采用::sortpdqsort。从源码结构看ClickHouse 选择 pdqsort 的典型场景是聚合函数/数组函数内部对数值向量做一次性原地排序单头文件零依赖、确定性、对分析型负载常见的含大量重复值的数值列有等值优化的额外收益这与 pdqsort 的设计目标模式数据上的表现高度吻合。小结pdqsort 用等值智能分区与受控的乐观插入排序两个机制把已排序、逆序、全相等、近乎有序这几类模式输入降到线性时间平均情形是 median-of-3大数组升级为 ninther快排并用BlockQuicksort 的无分支索引缓冲64 元素、L1 缓存内、缓存行对齐在比较函数无分支时显著提升大数组性能最坏情形采用确定性打乱固定位置元素打破模式坏分区超过log2(n)次则整体回退堆排序1/8分位阈值来自T(n,1/2)/T(n,p) ≈ 1.9的量化论证使用上它就是std::sort的直接替换API 见 contrib/pdqsort/pdqsort.hClickHouse 已在 Gini 系数等聚合/数组函数中实际采用。【免费下载链接】ClickHouseClickHouse® is a real-time analytics database management system项目地址: https://gitcode.com/GitHub_Trending/cli/ClickHouse创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考