系统内核

nvme-deep-dive

工作组开始制定新的存储协议标准,目标只有一个:释放闪存的真正性能。AHCI(Advanced

四叉树与八叉树深度实战:从空间递归划分的第一性原理、Morton 编码与范围查询,到碰撞检测、GIS 与三维场景管理的工程全解

空间数据无处不在:地图上的点、游戏里的碰撞体、点云中的三维坐标、图像里的像素块、甚至 NeRF/高斯泼溅里需要被快速检索的 3D 高斯。当数据规模从几百涨到几千万,朴素的两两比较(O(n²))会瞬间压垮系统。本文从第一性原理出发,把四叉树(Quadtree)与八叉树(Octree)这两种"把空间递归对半切"的结构讲透,并给出可直接落地的 Python 参考实现、复杂度对比与一份生产级陷阱清单。

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

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