4 ms·
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 cha
by arpadav 9d ago
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
- fschuett 9d 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 9d agolen(pics) either already knows about the length or it needs to count so it’s O(n)
- Anon_troll 9d 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.