从这里开始

第一次访问时先按主题切入,比直接沿着时间线翻文章更快。

热门专题

把已经形成系列阅读闭环的主题集中在首页,减少在 400 多篇文章里盲找的成本。

最新文章

按最近更新时间排序;如果你想系统性阅读一个主题,优先回到上面的专题入口。

BWT 与 FM-index:从 bzip2 到基因组比对

BWT 只是可逆排列,LF 映射让它能还原文本、用 rank 查询计数子串。本文用对拍过的 C 实现推演逆变换、backward search 与采样 SA 定位,并对照 bzip2 1.0.8、BWA 0.7.18 源码说明工程取舍。

LZ77、LZ78 与 LZW:字典从哪里来,最长匹配怎么找

从 1977、1978 年两篇原始论文出发,讲清滑动窗口与短语表两种字典、LZSS 与 LZW 的改动;用可解码验证的固定码 DEFLATE 输出实测哈希链与二叉树匹配查找器、贪心/lazy/最优解析:二叉树每位置 22 个候选即得最长匹配,最优解析比贪心小 12.7%。

zstd 的格式与实现:序列、FSE 表、字典与长距离匹配

按 RFC 8878 与 zstd 1.5.7 源码拆开帧、块、字面量段和序列段,讲清 FSE 表怎么建、怎么传、编码器怎么选模式;用逐比特记账的解码器实测:偏移额外比特占 39–44%,FSE 离逐块经验熵不到 1%,字典与长距离匹配的收益取决于数据和编码器的启发式。

算法工程索引

汇总本站算法工程相关文章,覆盖排序、哈希、树、字符串、近似数据结构、SIMD、随机化与编译器相关算法。

RCU:宽限期的保证、读侧的三种实现与代价的去向

从宽限期保证的形式陈述出发,对照 liburcu 0.15.7 与 Linux v6.12 源码,说明读侧省掉的 StoreLoad 栅栏由谁补上、'读侧零开销'在哪些配置下成立;实测读侧开销、宽限期延迟、membarrier IPI 转嫁给读者的代价和一个缺栅栏的变异体。

无锁栈:Treiber 栈、ABA、指数退避与消除退避

Treiber 栈只靠一次 CAS,却要分别处理 ABA、内存回收和争用三件事。本文用确定性复现、守恒测试和 sanitizer 区分前两者,在 4 个逻辑 CPU 上实测指数退避与消除数组,并对照 Linux llist、Windows SList、Boost.Lockfree 的取舍。