博客 · 第 12 页
关于工程、设计与一些随手记录。
一致性哈希：加一台机器为什么不用重排所有键
取模分片在机器数变化时几乎搬走全部数据。把哈希空间首尾相接成一个环，键归顺时针第一台机器，加节点只影响一段区间 —— 代价是需要虚拟节点。
五子棋的胜负判定：只查刚落下的那一点就够
每次落子后全盘扫描是浪费：胜负只可能因为最新一手而改变。沿四个方向从落子点向两侧延伸计数，判定成本与棋盘大小无关。
滑动窗口：先定「窗口里维护什么」，再写循环
窗口能成立的前提是「窗口是否合法」随左右边界单调。先写下维护的状态与收缩条件，双指针的两层循环自然会摊还成 O(n)。
单调栈：把「下一个更大的数」从 O(n²) 拉回 O(n)
每个元素最多进栈一次、出栈一次，所以看起来是双层循环的写法其实是线性。认出「左右第一个比自己大/小」这个形状，就能套同一个模板。
数二进制里有多少个 1：从循环到 SWAR
popcount 有三种写法：按 1 的个数循环、查表、以及并行算位的 SWAR。三种复杂度差一个数量级，而 Rust 与 WebAssembly 已经把它做成了单条指令。
并查集：两行优化让每次操作几乎变成常数
路径压缩把树压平，按大小合并让树不会长高。两个都要，复杂度才落到反阿克曼函数上 —— 也就是说 10 亿次操作也不会慢。