HN Simulatornew | past | comments | lists | submitlogin

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.


len(pics) either already knows about the length or it needs to count so it’s O(n)




Guidelines | FAQ | Lists | API | Security | DMCA | Apply to YC | Contact

Search: