What algorithm did Windows XP use to choose your initial user picture?

Post by pixl97 » Thu, Sep 10, 2026, 8:56 PM UTC

madibo3156 wrote: post #120

layer8 wrote: post #114

Earlier quoted context omitted.

The problem isn’t counting the files (the algorithm in the article also counts the files), but that if you determine that you want to use the i th file only after counting all files, you have to iterate over the whole directory again (or over expected half of it) to find that file.

The mechanism is interesting, but I'm not fully understanding the importance. We say it was done this way because a user would appreciate the speedup. The difference is one traversal versus expected one and one-half traversals. How slow was this traversal at the time for this difference to be significant?

Post by amag » Thu, Sep 10, 2026, 9:04 PM UTC

nerdo wrote: post #141

There's a better way to do this, you use inverse CDF to avoid all the RNG calls. Generate a random number, then skip items until you reach that number: selectRandomFromIteratorOptimized(iterator) { if (!iterator.moveNext()) { return null; } var winner = iterator.current(); var count = 1; while (true) { var u = random_float_open(0.0, 1.0); var skip = (int)Math.Floor(Math.Log(u) / Math.Log(1.0 - (1.0 / (count + 1))));…

    it is faster than RtlRandom() since it saves one multiplication, one addition and
    one modulus operation. This almost doubles the performance since it halves the number of
    clocks even on a pipelined Integer Unit such as the P6/ia64 processors i.e. ~ 52% perf gain.

Post by majorchord » Thu, Sep 10, 2026, 9:50 PM UTC

Post by majorchord » Thu, Sep 10, 2026, 10:28 PM UTC

tyrust wrote: post #166

majorchord wrote: post #165

Wouldn't it be even more random (and randomly faster) to break out of the while loop when a winner is found? That way you are not always iterating over the entire list. Perhaps a math/statistics expert can tell me why that is a bad idea.

If you break early, then you haven't given items later in the list the chance to be selected. You need to go through the entire list in order for every item to have an equal probability of selection. I didn't get it at first, either, and the Wikipedia article didn't do it for me. This explanation finally got me there: https://florian.github.io/reservoir-sampling/

Post by layer8 » Thu, Sep 10, 2026, 11:11 PM UTC

sltkr wrote: post #155

linepogl wrote: post #136

Earlier quoted context omitted.

Apart from the performance issues, it also prevents a bug. If some files get deleted between the first and the second pass, then you end up with unexpected behaviour and probably a crash.

The current implementation has the same race condition: the sampled file may be deleted by the time SHSetUserPicturePath() is called.