算法与计算机科学brooker.co.za编辑精选
两次随机选择的威力
The power of two random choices
2020 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇文章介绍负载均衡中的经典结论：与其随机分配任务，不如每次随机选两个候选服务器，把任务交给当前负载较低的那个。这个简单改动能把最忙节点的负载从随机分配时的 Θ(log n) 降到 Θ(log log n)，在分布式系统和缓存等场景中有实际价值。
为什么经久不衰：它用一个极简的概率技巧带来数量级的负载改善，今天在分布式系统设计中仍常被引用。
HN 评论精选
用 n 球 n 箱模型解释：随机选两个并投给较空者，最大负载从 Θ(log n) 降到 Θ(log log n)。
两随机选择的力量背后的数学驱动力，是关于 'n 个球放入 n 个箱子' 随机实验的一个非常惊人的事实。如果球独立均匀随机地投掷，最满的箱子会有 Θ(log n) 个球（几乎必然）。如果你改为每个球均匀独立随机选两个箱子，并把球投入目前球较少的那个，那么最满的箱子会有 Θ(log log n) 个球，也就是渐近意义下巨大的改进。
atq2119查看英文原文
The underlying mathematical driver of the power of two random choices is a pretty amazing fact about the "n balls into n bins" random experiment. If the balls are thrown independently and uniformly at random, the most loaded bin will have theta(log n) balls in it (almost certainly). If you instead pick two bins uniformly and independently at random for each ball and throw the ball into the bin which has fewer balls in it so far, then the most loaded bin will have theta(loglog n) balls in it, i.e a massive asymptotic improvement.
指出在选项存在持续差异时，该策略效果会打折扣。
我在一个模拟中发现效果不那么好：当两个选项之间存在轻微但持续的性能差异时，结果并不理想（链接是一篇关于‘靠谱健康检查’的更大研究的一部分）。
phyzome查看英文原文
I found less-than-great results in a simulation where there's a slight persistent difference between two of the options: https://www.brainonfire.net/blog/2019/07/21/load-balancing-beyond-healthchecks/ (as part of a larger study on healthchecks that Don't Suck).
联想到现实选择：先比较两个候选再决定可能同样有效。
这总是让我想到一个最有意思的问题：它是否意味着你在做选择前应该总是先试两个医生/牙医/心理治疗师等等。看起来在‘现实生活中’它可能同样强大。
zellyn查看英文原文
The most interesting question this has always raised for me is whether it implies you should always try two doctors/dentists/therapists/etc. before making a choice. Seems like it would be just as powerful “in real life“.
指出该技巧也用于缓存淘汰策略的讨论。
这项技术最近还被用在并讨论于另一个地方：缓存中的 LRU vs. Random（2014，danluu.com）[HN 链接]。
ckcheng查看英文原文
Another place this technique was used and discussed recently: Caches: LRU vs. Random (2014) (danluu.com) https://news.ycombinator.com/item?id=39093109
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选