Vor einiger Zeit erwähnte Raymond Chen, dass Windows XP das Bild eines neuen Kontos zufällig aus den Dateien in %ALLUSERSPROFILE%\Application Data\Microsoft\User Account Pictures\Default Pictures wählte. Leser wollten wissen, welcher Zufallszahlengenerator dahintersteckt, und Chen hat die Antwort nun auf The Old New Thing geliefert.

selectRandomFromIterator(iterator)
{
  var count = 0;
  var winner = null;
  while (iterator.moveNext()) {
    ++count;
    if (uniform_random(min: 1, max: count) == count) {
      winner = iterator.current();
    }
  }
  return winner;
}

Der Generator ist RtlRandomEx, mit dem aktuellen Wert von GetTickCount() als Seed. Dieser Seed reicht für die Wahl eines Standardbilds, nicht für sicherheitsrelevante Zwecke.

Die Auswahl selbst nutzt einen One-Pass-Algorithmus: den Spezialfall von Reservoir Sampling mit k gleich 1. Der Code zählt mit und ersetzt den bisherigen Gewinner beim n-ten Element mit Wahrscheinlichkeit 1/n. Chen nennt zwei Gründe für dieses Design. Es verursacht weniger Dateisystemaufrufe als der naive Ansatz des Zählens und anschließenden Auswählens, was zählt, weil das Dateisystem der Flaschenhals ist. Zudem bleibt der Algorithmus korrekt, selbst wenn Dateien im Verzeichnis während des Laufs auftauchen oder verschwinden.

Eine letzte Absicherung: Die Schleife stoppt nach 100 Bildern. So wird pathologisches Verhalten vermieden, falls jemand eine Million Dateien in Default Pictures ablegt.