On 01.05.2017 11:51, Moritz Maxeiner wrote:
On Monday, 1 May 2017 at 04:15:35 UTC, H. S. Teoh wrote:
Given a set A of n elements (let's say it's a random-access range of
size n, where n is relatively large), and a predicate P(x) that
specifies some subset of A of elements that we're interested in, what's
the best algorithm (in terms of big-O time complexity) for selecting a
random element x satisfying P(x), such that elements that satisfy P(x)
have equal probability of being chosen? (Elements that do not satisfy
P(x) are disregarded.)
Which elements of A satisfy P(x) is not known ahead of time, nor is the
relative proportion of elements that satisfy P(x) or not.
Works only with a random access range and I haven't done the full
analysis (and I'm a bit rusty on probability), but my first thought was
random divide and conquer:
ElementType!A* select(A,P)(A r)
{
// Recursion anchor
if (r.length == 1) {
if (P(r[0])) return r[0];
else return null;
// Recurse randomly with p=0.5 into either the left, or right half of r
} else {
ElementType!A* e;
ElementType!A[][2] half;
half[0] = r[0..floor(r.length/2)];
half[1] = r[ceil(r.length/2)..$];
ubyte coinFlip = uniform(0,1) > 0;
This deterministically chooses 0. (uniform is right-exclusive.) I assume
you mean uniform(0,2).
// Recurse in one half and terminate if e is found there
e = select(half[coinFlip]);
if (e) return e;
// Otherwise, recurse into other half
return select(half[1 - coinFlip]);
}
}
As stated above, I haven't done the full analysis, but intuitively
speaking (which can be wrong, of course), the p=0.5 recursion ought
satisfy the condition of elements satisfying P(x) being chosen
uniformly;
Counterexample: [1,0,1,1].
The first element is chosen with probability 1/2, which is not 1/3.
also intuitively, I'd expect the expected runtime for a
uniform distribution of elements satisfying P(x) to be around O(log N).
I don't understand this input model.
Worst-case would be that it has to inspect every element in r once => O(N)
