Windows XPの初期設定で、なぜその顔アイコンが出てきたのか。そんな昔話を、Raymond Chenが短く掘り下げています。答えは「かなり雑に見えて、実は筋が通っている」方式でした。しかも、単にランダムに見えるだけでなく、ファイル数が増えたり減ったりする現実の都合まで織り込まれていたのが面白いところです。古いOSの挙動を追う記事ですが、今読んでも「実装はこうあるべきだ」という感覚が残ります。
元記事が扱っているのは、Windows XPで新しいアカウントを作ったときに表示される初期ユーザー画像の選び方です。以前から、XPは %ALLUSERSPROFILE%\Application Data\Microsoft\User Account Pictures\Default Pictures に入っている画像の中から1枚を選んでいた、とChenは説明しています。読者から「そのときのRNG、つまり乱数生成はどうなっていたのか」と質問が寄せられ、それに答える形で仕組みが明かされました。
そこで使われていたのは RtlRandomEx で、初期シードには GetTickCount() の現在値が使われていたそうです。GetTickCount() は起動してからの経過時間を返す関数なので、厳密な意味での高品質な乱数ではありません。それでも、この用途には十分だった、というのが記事のトーンです。
選び方そのものは「one-pass random selection algorithm」、つまり1回の走査で候補を決める方式でした。Chenは、まず全件を数えてから2回目の走査で選ぶやり方より効率がいいと述べています。理由は、ファイルシステムへのアクセス回数を減らせるからです。こうした処理では、計算そのものよりディレクトリ列挙のほうがボトルネックになりやすいので、1回で済むのは理にかなっています。
さらに大事なのは、走査中にディレクトリ内のファイル数が変わっても面倒が少ないことです。2回方式だと、1回目で数えた後に2回目へ行く間にファイルが増減したら、前提が崩れます。1回走査なら、その場で見えているものだけを相手にできる。記事ではこれを、より一般的な reservoir sampling の特別なケースだと位置づけています。ここでは k = 1、つまり1個だけ無作為に選ぶ問題です。
本文には擬似コードも載っています。イテレータを1件ずつ進め、count を増やしながら、各要素について「1 から count の範囲で一様な乱数を引き、その値が count と一致したらその要素を winner にする」というやり方です。これを最後まで続けると、結果的に全要素が同じ確率で選ばれます。記事では、末尾の要素が 1/n の確率で選ばれることを起点に、再帰的に考える説明もしています。最後の1枚を選ぶ確率を先に決め、それを外れたら最初の n-1 枚の中からまた同じ問題を解く、という考え方です。
そして安全策として、コードは100枚で打ち切るようになっていた、とChenは書いています。もし誰かが Default Pictures ディレクトリに100万個ものファイルを置いたら、さすがに困るからです。そこまで想定するのは少し変ですが、実装としてはかなり実務的です。乱数だけでなく、異常な入力や過剰なファイル数まで見ているのが、この話のポイントでした。
この話でまず面白いのは、答えが本当に「random, really」だったことです。ミステリーを期待すると拍子抜けですが、実装としてはむしろ潔い。ユーザー画像の初期値に、深い意味や個人情報の推定を持ち込まない。候補群から1枚を選ぶだけに徹しているから、OSが妙な意図を背負わなくて済む。そこに私は、昔のWindowsらしい実務感を感じます。
ただ、単純なランダム選択ではなく、1回走査のアルゴリズムを採っているのが重要です。ファイル一覧を数えて、次にもう一度探す、という2回方式は分かりやすい反面、ディレクトリ列挙が重い環境では無駄が出ます。しかも、途中でファイルが増減したら選択結果の前提まで揺らぐ。OSのように状態が変わりうる場所では、「きれいな理屈」より「壊れにくい手順」が勝つことがある、という好例だと思います。
reservoir sampling という言葉は、データが巨大すぎて全体を持てないときに出てくる印象が強いですが、ここではたった1枚の画像選びに使われています。この使い方がいい。アルゴリズムは大げさな場面だけのものではなく、日常の細かい処理にもそのまま降りてくる。しかも k = 1 に落とし込むと、かなり素直なコードになるのがわかります。
擬似コードの肝は、「今見えている count 件の中で最後の1件を選ぶ確率を 1/count にする」という発想です。これなら、1件追加されるたびに選択の重みが自然に更新されます。最初から全件数を知る必要がない。順番に見ていくだけで、最後には全員に同じ当選確率が行き渡る。この“後からでも公平になる”感じは、アルゴリズムとしてかなり美しいと思います。
GetTickCount() と RtlRandomEx の組み合わせは、用途をちゃんと見ている乱数の種に GetTickCount() を使うと聞くと、今の感覚では心もとないと思う人が多いはずです。たしかに暗号用途なら論外です。でも、ここで必要なのは、見た目が少し偏りなく散っていればよい程度のランダム性です。どのユーザーにどの顔が出るかを決めるだけなら、強い乱数である必要はありません。用途に対して過不足がない。
この点は、ソフトウェアが「乱数」という言葉をひとまとめにしないほうがいい、という教訓にもつながります。公平な抽選、UIのちょっとしたバリエーション、暗号鍵生成では、求められる質がまったく違う。古いWindowsのコードは、その境界をわりと素直に踏んでいるように見えます。乱数の強さを誇るのではなく、必要十分な方法を選ぶ。その割り切りが、この話ではむしろ好印象でした。
最後に置かれていた「100枚で打ち切る」という安全策も、地味ですが重要です。理屈の上では、ディレクトリにどれだけファイルがあっても1回走査で選べる、で終わりません。現実には、誰かが変なものを置くかもしれないし、壊れた環境では想定外の膨らみ方をするかもしれない。そこで上限を設けておくと、最悪のケースでも作業が暴走しにくい。
この手の上限は、機能を増やすためというより、OSを壊さないために入ることが多いです。ユーザーは気づかない。けれど、こういう安全弁があるからこそ、昔のシステムは案外しぶとく動き続ける。見た目はただの「プロフィール画像選び」でも、裏側にはファイルシステム、乱数、異常系対策がちゃんと詰まっている。小さな機能ほど、実装者の現実感がにじむものだと改めて思いました。
参考: What algorithm did Windows XP use to choose your initial user picture? - The Old New Thing