Il y a quelque temps, Raymond Chen avait indiqué que Windows XP choisissait l'image d'un nouveau compte au hasard parmi les fichiers de %ALLUSERSPROFILE%\Application Data\Microsoft\User Account Pictures\Default Pictures. Des lecteurs voulaient savoir quel générateur aléatoire se cachait derrière, et Chen vient de répondre sur The Old New Thing.

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;
}

Le générateur est RtlRandomEx, amorcé avec la valeur courante de GetTickCount(). Cette graine suffit pour choisir une image par défaut, pas pour un usage lié à la sécurité.

La sélection repose sur un algorithme en un seul passage: le cas particulier du reservoir sampling avec k égal à 1. Le code tient un compteur et remplace le gagnant courant par le n-ième élément avec une probabilité de 1/n. Chen donne deux raisons à ce choix. Cela réduit les appels au système de fichiers par rapport à l'approche naïve qui compte puis choisit, et le système de fichiers est le goulot d'étranglement. L'algorithme reste aussi correct même si des fichiers apparaissent ou disparaissent pendant la boucle.

Une dernière protection: la boucle s'arrête après 100 images échantillonnées. Cela évite un comportement pathologique si quelqu'un dépose un million de fichiers dans Default Pictures.