Re:Latacora: Security Programs For Startups
by teraflop on Friday September 23, 2016 @06:50PM
(#12568495)
This implicitly assumes that Array.sort is stable: that is, if the comparison function returns 0 then sorting leaves the array elements in their original relative positions. That's not guaranteed by the JavaScript specification, see e.g. https://bugs.chromium.org/p/v8/issues/detail?id=90
It just so happens that in V8, the built-in sort uses an unstable quicksort for large arrays but a stable insertion sort for small ones, so the rest of your analysis is correct.
Re:Latacora: Security Programs For Startups
by ShaneWilton on Friday September 23, 2016 @05:49PM
(#12568225)
The output of Math.random also doesn't seem to be very uniform. With the original code, I'm consistently seeing Erin appear first 60% of the time, and Thomas first 30% of the time. Jeremy is left with 10%.
Even after changing the code to multiply by 99 instead of 100, the results don't change very much at all.
Re:Latacora: Security Programs For Startups
by RKoutnik on Friday September 23, 2016 @05:51PM
(#12568232)
Interesting, running just the number generation under node v6.5.0 gives:
{ '0': 340364, '1': 330093, '-1': 329543 }
So we see a slight bias for zero (elements are equal) there. ~Lemme try it in Chrome and get back to you.~AHA, repro'd in Chrome latest: http://jsbin.com/cefuqi/edit?js,console
Also repros in node. Fascinating. There goes my afternoon...
Re:Latacora: Security Programs For Startups
by thethirdone on Friday September 23, 2016 @06:47PM
(#12568489)
The problem is in the sort function. It expects the comparison to be deterministic and thus does not give the fully randomized list.
Instead giving each name a distinct value (between 0 and 1) and sort based on those values.
Re:Latacora: Security Programs For Startups
by ShaneWilton on Friday September 23, 2016 @05:58PM
(#12568270)
Ha, I was starting to think I was crazy.
If the function returns > 0, the first param should be sorted to a higher index than the second.
If the function returns < 0, the first param should be sorted to a lower index than the second.
If the function returns exactly zero, the parameters are left as they are.
So what we've got is a 1/3 of Erin 'winning', 1/3 of Thomas 'winning' and a 1/3 chance of a tie which leaves Erin ahead. So she's got a 2/3 chance of being first.
Additionally (but not in any consequential fashion), generating a random number between 1 and 100 (inclusive) gives you 100 possibilities (duh). With three outcomes:
The first option has slightly more chance to be picked. If Erin wanted to be fair(er), she'd multiply by 99.Here's a Python solution showing it's not just JS:
link: http://paste.ubuntu.com/23222240/
results:
(with apologies to ShaneWilton, I've completely rewritten this comment so the following comments are out of date)