Рэймонд Чен рассказал, какой алгоритм использовала Windows XP для выбора начального аватара пользователя

Инженер Microsoft Рэймонд Чен рассказал , что Windows XP выбирает начальный аватар пользователя случайным образом из изображений в каталоге %ALLUSERSPROFILE%\Application Data\Microsoft\User Account Pictures\Default Pictures. Для генерации случайного числа использовалась функция RtlRandomEx, а стартовым значением (seed) для неё служил текущий результат GetTickCount ().

Функция использует однопроходный алгоритм случайного выбора. Чен называет два преимущества такого решения. Во‑первых, по сравнению с двухпроходным алгоритмом он более эффективен, поскольку требует меньше обращений к файловой системе, что обычно становится узким местом. Двухпроходный алгоритм сначала подсчитывает все элементы, затем случайным образом выбирает число от 1 до n и повторно проходит по списку, чтобы найти элемент с этим индексом.

Во‑вторых, однопроходный алгоритм позволяет избежать сложностей, если количество файлов в каталоге изменяется во время выполнения кода. Однопроходный алгоритм представляет собой частный случай «резервуарной выборки» (reservoir sampling), где k равно 1. Этот частный случай позволяет использовать специально адаптированный алгоритм, который значительно проще.

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

В основе алгоритма лежит наблюдение: в наборе из n элементов последний имеет вероятность 1/n быть выбранным.

Если он не выбран, то необходимо случайным образом выбрать один из первых n — 1 элементов, что можно решить рекурсивно.

Список из одного элемента допускает только выбрать этот элемент. Для списка из n элементов сначала случайным образом выбирается один из первых n — 1, а затем с вероятностью 1/n он заменяется на n‑й элемент.

В качестве дополнительной проверки безопасности код останавливается после обработки 100 изображений. Это позволяет избежать проблем, если кто‑то поместит миллионы файлов в каталог изображений по умолчанию.

В июне этого года Чен рассказал , как команда разработчиков Microsoft обнаружила настолько плохой код эмулятора x86, что исправила его во время эмуляции. Спустя месяц он сообщил , что Windows 95 наугад опознавала исполняемые файлы как установочные, ориентируясь только на их имена. К концу лета Чен поделился историей о том, как на коробке оригинального игрового сборника Microsoft Entertainment Pack появилась наклейка, сообщающая о наличии Tetris.