主题： algorithms

• 用图遍历确定依赖顺序：BFS、DFS 与拓扑排序

  将依赖建模为有向图，用广度优先或深度优先遍历找到变更影响的所有项，再用 Kahn 算法或 DFS 后序遍历生成构建或迁移顺序，并显式报告环，而不是隐藏它；graphlib 和 tsort 提供这种排序。

  methodology · zh · reviewed · 知识截至 2026-09-16

• 哈希表实践：冲突、负载因子与带种子的哈希

  只有键均匀分布在桶中，哈希表的平均性能才快；冲突、触发重哈希的负载因子，以及用于抵御哈希洪泛的进程级哈希种子，决定了实际行为。不要持久化哈希值，也不要依赖迭代顺序。

  article · zh · reviewed · 知识截至 2026-09-16

• 逐步理解动态规划：推导编辑距离

  动态规划将带有重叠子问题的递归定义转为多项式算法：定义状态，写出递推关系和边界情况，采用记忆化或填表，再压缩内存。本文以两个字符串之间的编辑距离为例，给出完整推导。

  methodology · zh · reviewed · 知识截至 2026-09-16

• Recursion versus iteration: stack depth, limits and when to convert

  Recursion mirrors tree-shaped problems but spends one stack frame per level; the stack is bounded by the interpreter's recursion limit or the thread's stack size, so recursion over input-controlled depth is a crash waiting to happen. Convert to an explicit stack or loop when depth grows with input size.

  article · en · reviewed · 知识截至 2026-09-16

• 蓄水池抽样：从未知长度的数据流中均匀取样

  无需知道流的长度即可保留 k 项：先用前 k 项填满蓄水池，随后对第 i 项以 k/i 的概率替换一个随机槽位。只需一次遍历和 O(k) 内存，每项最终入选的概率恰为 k/n，简短的连乘消去推导即可证明。

  methodology · zh · reviewed · 知识截至 2026-09-16

• 用于前缀查找的字典树：自动补全与最长前缀匹配

  字典树为每个公共前缀保存一个节点，因此查找成本取决于键长，与键数无关；同一前缀的所有键组成一个子树，一次遍历即可找到查询的最长已存储前缀。可用于自动补全和路由，但应先与有序数组比较。

  article · zh · reviewed · 知识截至 2026-09-16

• 二分查找陷阱：中点溢出与边界差一错误

  二分查找很短，却出了名地容易写错：(low + high) / 2 会使固定位宽整数溢出，包含与不包含的边界容易混用，重复项又引出应返回哪个索引的问题。应使用库函数，或采用半开区间的单调谓词形式，并测试边界。

  article · zh · reviewed · 知识截至 2026-09-16

• Reasoning about complexity before optimising

  Asymptotic complexity predicts how run time grows with input size; recognising quadratic loops, repeated linear searches and unbounded recursion in code review prevents most performance incidents before profiling is needed.

  methodology · en · reviewed · 知识截至 2026-09-15

• Token bucket, leaky bucket and sliding window: how rate-limiter algorithms differ

  Fixed windows are cheap but let twice the limit through at a boundary; sliding logs are exact but store every timestamp; sliding-window counters approximate in constant memory; token buckets allow bursts up to the bucket size at a fixed refill rate; leaky buckets smooth output by delaying. nginx and Envoy document the last two.

  article · en · reviewed · 知识截至 2026-09-16

• 布隆过滤器：没有假阴性的概率集合成员检测

  布隆过滤器使用小型位数组和 k 个哈希函数，回答“确定不在集合中”或“可能在集合中”。假阳性率可调，不会出现假阴性，也不支持删除。用它跳过不存在键的查找，并始终向权威数据源核验阳性结果。

  article · zh · reviewed · 知识截至 2026-09-16

• A* heuristics: preserve the meaning of movement cost

  Choose a lower-bound heuristic for the actual movement graph, handle improved routes correctly, and verify path quality against an uninformed search.

  article · en · unreviewed · 知识截至 2026-10-11

• Use a token bucket for tool calls

  Implement bounded bursts with an explicit token refill equation, atomic consumption and a separate limit on in-flight requests.

  methodology · en · reviewed · 知识截至 2026-09-21

• 排序稳定性：它保证什么，何时重要

  稳定排序会保留比较结果相等的元素在输入中的先后顺序。Python 保证这一点，ECMAScript 自2019年起将其列为要求，Go 和 GNU sort 则提供可选的稳定排序；它决定了多关键字排序、可排序表格和分页查询能否保持可预测的行为。

  article · zh · reviewed · 知识截至 2026-09-16

机器可读： JSON