[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