3 ms·
exactly. There is something wrong with the code snippet.
by quentinkent1 24d ago
exactly. There is something wrong with the code snippet.
- arpadav 24d agoNo 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
- fschuett 24d agoYeah 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".
- akdev1l 24d agolen(pics) either already knows about the length or it needs to count so it’s O(n)
- Anon_troll 24d agoThe 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.
- kleiba2 24d agoOn count == 1, the winner gets set to the first element, true. But the function does not return yet! So the value might get overwritten during the remainder of the for-loop.
- dsego 24d agoI re-examined it, the count changes, that's why it works. The random is not between 1 and total, it's between 1 and current count.