3 ms·

Why doesn't it return on the first match?

• quentinkent1 25d ago
  exactly. There is something wrong with the code snippet.
  • arpadav 25d 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 25d ago
      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".
      • akdev1l 25d ago
        len(pics) either already knows about the length or it needs to count so it’s O(n)
      • Anon_troll 25d ago
        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.
  • kleiba2 25d ago
    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.
  • dsego 25d ago
    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.
• yoz-y 25d ago
  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 replacing the selection with the new one. Resulting in a 1/3 chance of selecting any of the three. (Because 1/2-1/6 = 1/3) 1/6 because there is 50% chance you will “steal” the selection.
  • Elte 25d ago
    Thank you for writing this out, I didn't quite get what was going on at first. But then, to formalize the recursion from your example: let's assume we're at item n in the iterator, and at that point we've selected a winner from the previous n-1 items with equal probability, i.e. each item had a 1/(n-1) chance of being selected. The probability that item n will override it is 1/n. The probability that the old winner will remain selected is thus (n-1)/n. That means that the old winner remains selected with probability 1/(n-1) * (n-1)/n, which cancels out to 1/n, so each item is indeed selected with equal probability in the end.
    • Anon_troll 25d ago
      An alternative wording for the same idea: If you are at picture 1, you have 100% chance of selecting it as the current winner. If you are at picture 2, you have 1/2 chance of selecting it as the current winner, or 1/2 chance of keeping the previous fairly selected winner. At picture 3, 1/3 chance of picking it, or 2/3 chance of retaining the previous fairly-selected winner. There are two of them, so 1/3 chance of each. At picture n, you have a 1/n chance of picking it, or an (n-1)/n chance of retaining the previous fairly-selected winner. There are n-1 previous pictures, so all of them have had 1/n chance of being picked. At every single step, there is the invariant of all pictures being considered that far having had an equal chance of being selected, and the next step always retains the invariant.
      • matsemann 25d ago