视窗XP（Windows XP）曾从微软（Microsoft）用户账户图片默认目录随机选初始图片，现有人欲知更多。随机数生成器用RtlRandomEx，以GetTickCount()当前值为初始种子。函数采用单遍随机选择算法，相较先计数再随机选索引的两遍法，减少了文件系统调用，且避免目录文件数变化时的问题。单遍算法是蓄水池采样（reservoir sampling）特例，k为1，可简化定制。

我之前提到过，Windows XP 会从 %ALLUSERSPROFILE%\Application Data\Microsoft\User Account Pictures\Default Pictures 目录中的图片里随机选出你的初始图片。不过人们想知道得更多。

随机数生成器用的是 RtlRandomEx，以 GetTickCount() 的当前值作为初始种子。

这个函数采用单遍随机选择算法。我能立刻想到这么做的两个好处。第一，与那种先数出所有项目、再随机挑一个 1 到 n 之间的序号、然后第二次遍历找出对应项目的朴素两遍算法相比，它更高效，因为减少了文件系统调用次数，而瓶颈正在这里。第二，单遍算法避免了代码运行期间目录中文件数量发生变化时带来的麻烦。

单遍算法是水库采样在 k=1 时的特例。这个特例允许使用一个简单得多的定制算法。

selectRandomFromIterator(iterator)：令 count = 0，winner = null。只要 iterator.moveNext() 返回真，就把 count 加一，如果 uniform_random(min: 1, max: count) 的结果等于 count，就把 winner 设为当前项目。循环结束后返回 winner。

这个算法的思路是：在一个有 n 个项目的集合中，最后一个项目有 1/n 的概率被随机选中；如果它没被选中，就需要从前 n−1 个项目中随机选择，而这个问题可以递归解决。

把递归正向展开，从基础情况开始：如果列表里只有 1 个项目，那么唯一的选择就是它。否则，如果列表有 n 个项目，先从 1 到 n−1 中随机选一个，再以 1/n 的概率切换到第 n 个项目。

最后还有一道安全检查：代码在采样 100 张图片后停止。这样如果有人往 Default Pictures 目录里放了一百万个文件，也不会出现病态行为。

社区围绕 Windows XP 用户图片选择算法的旧文展开讨论：不少人质疑当年实现过于复杂、百张上限偏低，另一部分人则赞赏对隐蔽边界情况的周全考量，并借机感叹现代开发因工期压力丢失了底层效率意识。

认为100张图片上限在当时也偏低

• 有读者指出即便是 XP 时代，限定仅 100 张用户图片也显得没必要地低。（少数人）

认为原算法过于复杂且本可简化

• 部分读者质疑为何不采用基于用户名首字符的简单随机取模，或为何不在首次匹配时直接返回，也奇怪系统为何不提供获取文件数的接口而需遍历。（较多人） > 用用户名首字母做简单随机取模就足够了，何必这么复杂？（@KellyCriterion）

赞赏对微小边界情况的周全考虑

• 不少读者感叹，这种绝大多数用户不会察觉的问题竟被如此细致地处理，显现出看似简单功能背后的特殊情形复杂性。（较多人） > 惊人的是对一个多数用户根本不会注意的问题竟投入如此多的考量。（@Aditya_0315）

感叹现代开发因时间压力丢失了底层效率意识

• 有开发者反思，如今任务繁杂使人不再思考此类算法与资源代价，若时间紧迫会采用粗糙数文件随机选的做法；直到接触系统级语言才惊觉以往字符串与结构分配的巨大浪费。（少数人） > 转向 Zig 后才意识到我们为赶工期随便写代码浪费了多少内存与计算。（@mawadev）

有价值的补充

• 有用户贴出了文中提及的 Windows XP 源码文件 userpict.cpp 的实际链接，供对照阅读。（@EMIRELADERO）
• 有人怀念过去工程师会多花心思避免大规模二次遍历的节约习惯。（@cgio）
• 有读者好奇 Raymond Chen 公开发表这些内部细节是否需要获得授权，并表达对其文章的喜爱。（@lyorig）