概要

• Windows XPの初期プロフィール画像選択アルゴリズム解説
• RtlRandomExとGetTickCount()による乱数生成
• 一回の走査で効率的に画像を選択
• Reservoir Samplingの特別なケースを利用
• 最大100枚までの画像を対象に安全対策

Windows XP初期プロフィール画像選択アルゴリズム

• Windows XPは、最初のアカウント作成時、 %ALLUSERSPROFILE%\Application Data\Microsoft\User Account Pictures\Default Pictures ディレクトリ内の画像からランダムにプロフィール画像を選択
• 乱数生成には RtlRandomEx 関数を使用し、 GetTickCount() の現在値を初期シードとして採用
• 画像選択には一回の走査で済む ワンパスアルゴリズム を使用
  • ファイル数を先に数えてから選ぶ従来のツーパス方式よりも、ファイルシステムへのアクセス回数が減少
  • 実行中にディレクトリ内のファイル数が変化しても問題が発生しない利点

Reservoir Samplingアルゴリズムの応用

• このワンパスアルゴリズムは、 Reservoir Sampling （k=1の場合）の特別なケース
  • 1つのアイテムしか選ばない場合に最適化されたシンプルな実装
• アルゴリズムの仕組み
  • アイテムn個のうち、最後のアイテムが選ばれる確率は1/n
  • 選ばれなかった場合は、残りn-1個から再帰的に選択
  • 1個だけの場合はそのアイテムを選択
  • n個ある場合は、まずn-1個からランダムに選び、1/nの確率でn番目に切り替え

サンプル実装（擬似コード）

• selectRandomFromIterator(iterator)
  • countを0、winnerをnullで初期化
  • イテレータで各アイテムを走査
    • countをインクリメント
    • 1からcountの範囲で一様乱数を生成し、countと一致すればwinnerを更新
  • winnerを返却

安全対策と制限

• 画像ファイルが非常に多い場合の 異常動作防止 のため、最大100枚までの画像のみを対象
  • ディレクトリに大量のファイルがある場合でもシステム安定性を確保

著者情報

• 著者RaymondはWindowsの進化に30年以上関与
• 2003年から The Old New Thing というWebサイトを運営
  • サイトは人気となり、書籍化も実現（Addison Wesley 2007年）
• 時折Windows Dev Docs Twitterアカウントにも登場し、ユーモア溢れるエピソードを発信