Hace tiempo Raymond Chen mencionó que Windows XP elegía la imagen de una cuenta nueva al azar entre los archivos de %ALLUSERSPROFILE%\Application Data\Microsoft\User Account Pictures\Default Pictures. Los lectores querían saber qué generador aleatorio había detrás, y Chen acaba de responder en 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;
}

El generador es RtlRandomEx, con semilla en el valor actual de GetTickCount(). Esa semilla basta para elegir una imagen predeterminada, no para un uso relacionado con la seguridad.

La selección usa un algoritmo de una sola pasada: el caso especial del reservoir sampling con k igual a 1. El código lleva un contador y sustituye al ganador actual por el elemento n con probabilidad 1/n. Chen da dos razones para este diseño. Hace menos llamadas al sistema de archivos que el enfoque ingenuo de contar y luego elegir, lo cual importa porque el sistema de archivos es el cuello de botella. El algoritmo también sigue siendo correcto aunque los archivos aparezcan o desaparezcan del directorio mientras el bucle se ejecuta.

Una última protección: el bucle se detiene tras muestrear 100 imágenes. Así se evita un comportamiento patológico si alguien coloca un millón de archivos en Default Pictures.