Hacker News Reader

Comment by quentinkent1 | Hacker News Reader

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)]

... 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)

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.

On 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.

I 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.

Reply on news.ycombinator.com