[OT] Algorithm question
MysticZach via Digitalmars-d
digitalmars-d at puremagic.com
Tue May 2 16:09:54 PDT 2017
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.
More information about the Digitalmars-d
mailing list