Инженер Microsoft Рэймонд Чен рассказал, что Windows XP выбирает начальный аватар пользователя случайным образом из изображений в каталоге %ALLUSERSPROFILE%Application DataMicrosoftUser Account PicturesDefault 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.
Источник: habr.com