Linux内核

快速排序与归并排序深度实战:从分区第一性原理、三路切分与内省排序,到外排序、稳定性与 AI 数据管线的工程全解

排序是计算机科学里被讲述最多、也最容易被"以为已经懂了"的算法。绝大多数工程师能默写 Lomuto 分区,却说不清 Hoare 分区少了多少次交换;能背出快排平均 O(n log n),却在面对"为什么 `std::sort` 既快又不会被恶意输入打爆"时哑口无言;会在内存里排 10 万元素,却在外排序喂不动 2 TB 训练样本时束手无策。

基数树(Radix Tree / Patricia Trie)深度实战:从路径压缩、二进制切分到 Linux 页缓存 xarray 与路由最长前缀匹配的工程全解

在「字典树(Trie / 前缀树)深度实战」一文中,我们拆解了 Trie 如何用「字符沿边展开」把前缀共享做到极致,却也暴露了一个结构性代价:当插入大量长键且共享前缀稀疏时,Trie 会膨胀出无数只含单个子节点的「瘦链」节点,内存与指针开销被白白浪费。基数树(Radix Tree,又名 Patricia Trie、压缩前缀树)正是为消灭这些瘦链而生的——它通过**路径压缩(path compres…

KD 树(KD-Tree)深度实战:从多维空间划分的第一性原理、交替轴 median 切分与回溯剪枝,到向量检索 KNN、射线追踪与维度灾难的工程全解

> 当你需要在百万个点里找到离某个查询最近的那一个时,"遍历一遍"会变成百万次距离计算;而 KD 树把这件事压到了接近 O(log n)。但它在高维空间会悄悄退化成暴力扫描——这篇文章从第一性原理讲清它为什么有效、为什么失效,以及工程上如何与 HNSW/IVF/LSH 协同。

线段树与树状数组深度实战:从区间查询的第一性原理、lazy 标记到滑动窗口指标、订单簿与延迟直方图聚合的工程全解

区间,是几乎所有"可观测"系统的隐形骨架:实时大盘的滚动求和、限流器的滑动窗口计数、行情系统的档位聚合与 VWAP、推理服务的延迟直方图与分位告警、合并排序的归并段、文本与 DNA 的 LCP 数组……这些场景的共同点是——**数据在持续被单点更新,而你又必须随时回答"某一段区间的聚合值(和 / 最大 / 最小 / 计数)是多少"**。当你发现自己在用 `sum(arr[l:r+1])` 反复遍历…

字典树(Trie / 前缀树)深度实战:从字符沿边展开、压缩与双数组到 IP 路由与敏感词过滤的工程全解

前缀,是几乎所有"检索"类系统的隐形骨架:自动补全、搜索建议、T9 输入法、IP 路由的最长前缀匹配(LPM)、敏感词过滤、拼写纠错、词典树、前缀计数与排名……这些场景的共同点是——**查询的不是整条键,而是"以某串为前缀的所有键"**。当你发现自己在用 `startswith` 遍历百万字符串时,就该请出字典树了。

并查集深度实战:从等价划分、路径压缩到按秩合并与可撤销/持久化的工程全解

系统拆解并查集(Disjoint Set Union)的第一性原理:用有根森林表示等价类划分,find/union 如何把"是否连通"转化为"根是否相同"。从朴素实现的 O(n) 退化陷阱出发,推导两大核心优化——路径压缩(迭代版,规避 Python 递归爆栈)与按秩/按大小合并——二者叠加把摊还复杂度钉死在反阿克曼函数 α(n)(物理可观测尺度内 α(n)≤4,近似常数)。进而展开变体谱系:加权/种类并查集、可撤销并查集(仅按大小合并+栈回滚,禁用路径压缩)、持久化并查集、DSU on tree、离线动态连通性、网格并查集。给出 Kruskal MST/连通分量/图像分割/等式约束/类型合一 等应用对照表、12 项生产陷阱清单(递归压缩爆栈、索引混淆、可撤销误用压缩等)与可复现 Python 工具箱。与本站 布隆过滤器/Count-Min Sketch/HyperLogLog/布谷鸟哈希 共同构成"概率与高性能数据结构工程"系列,前者提供确定性精确的等价类划分,后者提供概率近似的集合成员/频率/基数估计,工程栈中互补共存。