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.
What algorithm did Windows XP use to choose your initial user picture?
91–100 of 165 posts
Re: What algorithm did Windows XP use to choose your initial user picture?
#92Re: What algorithm did Windows XP use to choose your initial user picture?
#93Earlier quoted context omitted.
exactly. There is something wrong with the code snippet.
No there is not. First element is defacto winner, but you still have to loop through the rest with 1/n chance of being selected to fully give each element a chance of winner selection
Yeah I think the "wrong feeling" is just that this could, in theory, be O(1) with something like:
pics[Math.random() * len(pics)]
Re: What algorithm did Windows XP use to choose your initial user picture?
#94But the naive way of doing this also wouldn't really require two passes, right? It would just require more memory because you would first save all file names in an array (stopping at 100), then pick a random one in constant time.
Re: What algorithm did Windows XP use to choose your initial user picture?
#95Why doesn't it return on the first match?
Because it would always return the first match in that case. You still need to see all of the items once. Imagine you have 2 items. First one has 100% chance to be selected. So it does. Then the second has 50% chance to be selected. If it isn’t you effectively chosen the first one and have 50/50 chance to return either. Now you add a third item. There is 50/50 chance of having either selected. And 1/3 chance of repla…
Oh, I understand, should've examined more carefully, the count starts at 0 and increments, so random is not from the total but from the elements counted so far.
Re: What algorithm did Windows XP use to choose your initial user picture?
#96Re: What algorithm did Windows XP use to choose your initial user picture?
#97A mentally simpler, though slightly biased algorithm is for each item, randomly generate a uint64 (arbitrary bit size) and switch to the new item if and only if the number generated is greater than or equal to all previously seen numbers. The end result is equivalent to randomly generating a number for each item and picking the item with the largest associated number.
Re: What algorithm did Windows XP use to choose your initial user picture?
#98Honestly, I don't understand Microsoft. These guys solve the most mundane problems with most elegant solutions and with sound edge-case handling scenarios, then they destroy all the effort with subpar programming where it matters and with user hostile behavior where they can't botch it.
> // Assume everything in the dir is a vaild image file Yep.. And image files were, and continue to be, a huge exploit attack vector
We had bigger problems back then, and the function ran considerably rarely when compared the other parts of the OS, so it was a valid assumption at that age.
However, I still remember Wine laughing at Windows for WMF exploit and end up being affected from the same exploit. Now, that was a good laugh.
Re: What algorithm did Windows XP use to choose your initial user picture?
#99Earlier quoted context omitted.
No there is not. First element is defacto winner, but you still have to loop through the rest with 1/n chance of being selected to fully give each element a chance of winner selection
Yeah I think the "wrong feeling" is just that this could, in theory, be O(1) with something like: pics[Math.random() * len(pics)] ... assuming that random() gives you a number from 0..1 - but that's why it feels "wrong".
len(pics) either already knows about the length or it needs to count so it’s O(n)
Re: What algorithm did Windows XP use to choose your initial user picture?
#100Earlier quoted context omitted.
No there is not. First element is defacto winner, but you still have to loop through the rest with 1/n chance of being selected to fully give each element a chance of winner selection
Yeah I think the "wrong feeling" is just that this could, in theory, be O(1) with something like: pics[Math.random() * len(pics)] ... assuming that random() gives you a number from 0..1 - but that's why it feels "wrong".
The len(pics) can be O(n), especially if iterators are used like here. Also, an O(1) lookup would require a previous O(n) pass over the data anyway.
The picture selection algorithm's kind of single-pass iterator usage might have been more performant back in the XP days, as it avoids possibly expensive operations.
Modern CPU/other optimizations might make a multi-pass approach more performant due to better memory locality or other factors.