On Tuesday, 2 May 2017 at 21:00:36 UTC, Timon Gehr wrote:
On 02.05.2017 22:42, MysticZach wrote:
On Tuesday, 2 May 2017 at 13:44:03 UTC, MysticZach wrote:
for (;;) {
if (P(a[i]))
return i;
++count;
if (count == length)
return -1;
i += hop;
if (i < length)
continue;
if (i < skipLength)
i += hop;
(I guess this should be 'while'.)
skipLength is determined modulo hop, thus it can't be more than
one hop away.
Counterexample: [1,1,1,0,0]
Your algorithm returns 0 with probability 7/20, 1 with
probability 6/20 and 2 with probability 7/20.
Note that there is a simple reason why your algorithm cannot
work for this case: it picks one of 20 numbers at random. The
resulting probability mass cannot be evenly distributed among
the three elements, because 20 is not divisible by 3.
That's true. Two points, though: If the range of error is within
1/(n*(n-1)), with array length n, it may be close enough for a
given real world use case. 2. n is known to be large, which makes
1/(n*(n-1)) even smaller. You'd probably have to trade accuracy
for performance. I wonder how much less performant a truly
accurate algorithm would be. Also, whether there's a way to make
an algorithm of this style completely accurate.
