Windows XP выбирала вашу аватарку алгоритмом из одного прохода
What algorithm did Windows XP use to choose your initial user picture?
Рэймонд Чен из Microsoft объясняет, как Windows XP случайно выбирала стартовую картинку пользователя из папки Default Pictures. Использовался генератор RtlRandomEx с начальным зерном GetTickCount() и алгоритм выбора за один проход — частный случай reservoir sampling при k=1. Такой подход экономит обращения к файловой системе и устойчив к изменению числа файлов во время работы. Для защиты от патологического поведения выбор останавливается после 100 картинок.
Алгоритм работает так: в коллекции из n элементов последний элемент имеет шанс 1/n быть выбранным случайно. Если он не выбран, нужно случайно выбрать из первых n − 1 элементов, что решается рекурсивно.
- mawadev
Это тот случай, о котором я узнаю только когда читаю подобные блоги. Технически я мог бы решить это так же, но в наши дни у тебя на столе столько задач, что ты вообще не думаешь о проблеме и её последствиях, и эта осознанность/дисциплина тонет в шуме/со временем утрачивается.
Если бы кто-то дал мне на это всего 2 минуты, потому что считает это очень простым (как всегда), я бы просто посчитал количество файлов определённого шаблона в директории и выбрал случайный индекс — очень наивное, быстрое и грязное программирование, без всякой выборки, просто чтобы избежать разговоров о том, почему это занимает так много времени, с людьми, которые не хотят этого слышать.
Это напоминает мне о том, как я много занимался C#, Java, JS, Python в своей жизни, заполняя словари строками и объектами, пока не начал работать с zig и не заметил, насколько дорогими и сложными могут быть строки и выделение памяти под структуры данных. Меня просто поразило, сколько памяти и вычислений мы тратим впустую, когда пытаемся сделать всё как можно быстрее из-за бюджетных/временных ограничений.
- lyorig
Блин, каждый пост Raymond Chen о внутренностях Windows — как маленькое Рождество. Интересно, приходится ли ему спрашивать у кого-то разрешения, прежде чем публиковать эти знания.
- EMIRELADERO
Для тех, кому интересно, вот тот самый код, о котором говорит Chen: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...
- impoppy
>Raymond участвует в эволюции Windows более 30 лет. Он иногда появляется в Twitter-аккаунте Windows Dev Docs, чтобы рассказывать истории, которые не несут никакой полезной информации.
- scrumper
Это забавный пример когнитивного переключения, которое нужно совершить, когда только начинаешь программировать компьютер. Для человека невероятно легко выбрать случайную вещь из кучи: ты протягиваешь руку и хватаешь её, может быть, сначала перемешав их на столе, чтобы изменить порядок. Для компьютера прямой аналогии этому нет. Они просто не могут этого сделать. И человеческий процесс совсем не похож на тот, которому следует компьютер: нам не нужно считать множества и перебирать их, или считать элементы, а затем генерировать случайное число, чтобы выбрать n-й элемент, или рисковать выбрать нулевой элемент.
- cgio
Времена, когда люди тратили лишний цикл мозга, чтобы избежать миллиардов повторных проходов.
- rietta
Обожаю это сдержанное «некоторое время назад» со ссылкой на пост в блоге 2004 года. Raymond занимается этим уже давно :-)
- ape4
Несколько странно, что в файловых системах нет вызова, который сообщал бы, сколько файлов находится в папке.