Windows XP picked your first user picture with a one-pass algorithm
What algorithm did Windows XP use to choose your initial user picture?
Windows XP chose your initial account picture at random from the Default Pictures folder using RtlRandomEx, seeded by GetTickCount(). Raymond Chen explains the one-pass selection algorithm, a special case of reservoir sampling where k=1. It avoids a second pass over the file system and handles directories that change mid-scan, with a safety cap of 100 pictures.
The one-pass algorithm is a special case of reservoir sampling, where k is 1.
- mawadev
That is a case I only become aware of when I read blogs like this. Technically I could solve it the same way, but these days you have so many tasks on your desk, you don't think about the problem and implications at all and that awareness/discipline is drowned in the noise/unlearned over time.
If someone only gave me 2 minutes for this, because they think it is very simple (as always), I'd have done a count of files of a specific pattern in the directory and then picked a random index, very naive and quick and dirty programming, no sampling at all, just to avoid discussions why it takes so long with people who don't want to hear it.
This reminds me of when I did a lot of C#, Java, JS, Python in my life, filling maps of strings and objects until I started with zig and noticed how expensive and complicated strings and data structure allocations can be. It kind of blew my mind how much memory and computation we waste when we try to get stuff done as fast as possible because of budget/time constraints.
- lyorig
Man, every post from Raymond Chen regarding Windows internals is like a little Xmas. I wonder whether he has to ask someone for permission before publishing this knowledge, though.
- EMIRELADERO
For those interested, here's the actual code Chen talks about: https://github.com/tongzx/nt5src/blob/daad8a087a4e75422ec96b...
- impoppy
>Raymond has been involved in the evolution of Windows for more than 30 years. He occasionally appears on the Windows Dev Docs Twitter account to tell stories which convey no useful information.
- scrumper
This is a fun example of the cognitive switch you have to employ when first starting to program a computer. It's extremely easy for a human to pick at random one thing from a pile of things: you reach out your hand and grab it, maybe swirling them around on the table first to shuffle the order. For a computer, there's no direct analogy to that. They just can't do it. And the human process is nothing even slightly like the one the computer follows: we don't have to count the sets and iterate over them, or count the items and then generate a random number to pick the nth item, or risk picking a null item.
- cgio
The times when people spent an extra brain cycle to avoid billions of second passes.
- rietta
I love the understated "some time ago" linking to a 2004 blog post. Raymond has been at this a long time :-)
- ape4
It's somewhat odd that filesystems don't have a call to tell you how many files are in a folder.