On Fri, Feb 13, 2009 at 9:37 AM, Bill Baxter <[email protected]> wrote: > On Fri, Feb 13, 2009 at 9:23 AM, Andrei Alexandrescu > <[email protected]> wrote: >> Sean Kelly wrote: > >>> Skip ahead a random number of elements before performing the linear >>> search. >> >> Can you prove this will yield a uniform cover? > > I don't see how it could. If you have a linear search at all, then > empty at the end of a row of filled elements will always have a higher > probability of getting chosen. > > Pure dart throwing would clearly work though. Just keep trying > randomly till you hit an empty. Won't perform very well, though.
If you count the total number of 1's that precede the 0 you've chosen, you can tell how biased the choice was. Say it was k/n when it should have been just 1/m (n the total number, m the 0's remaining). If you know this, you can systematically discard the choice and try again with probability such that the combined probability of both choices comes out to 1/m. So that would be k/n * x = 1/m, thus x = n/(k*m). So you keep the value found by linear probing with probability n/(k*m), otherwise you try again. Nice thing is as m is getting smaller, typical k's are approaching n, and so towards the end you get to keep more and more of your choices. So it fixes the problem with pure dart throwing where it takes a longer and longer time to find the last few empty slots. How's that sound? --bb
