== Quote from Andrei Alexandrescu ([email protected])'s article > Bill Baxter wrote: > > On Fri, Feb 13, 2009 at 7:21 AM, Andrei Alexandrescu > > <[email protected]> wrote: > >> Jason House wrote: > >>> Andrei Alexandrescu Wrote: > >>> No. Your wording sounds like you're doing > >>> stuff that's way off, but the resulting math is correct. My > >>> calculation would be based on the average length of a sequence of 1's > >>> (k/(n-k)). That means the work is 1+k/(n-k) = n/(n-k). > >> Well my wording means this: in an array of length n with k "holes" > >> randomly distributed, the probability one slot is a a no-hole is > >> (n-k)/n. What we want is to find the first no-hole starting from a > >> random position in the array. How many steps do we do on average? That > >> is the same as the average number of steps of rolling a fair dice with > >> (n-k) faces until we obtain a particular face. And the average number of > >> steps is IIRC 1/p = n/(n-k). > > > > Except your holes aren't randomly distributed, because you are more > > likely to fill a hole next to an already filled slot. > Oops, that makes me more likely to choose some slots than other. My > algorithm stinks! > Consider the array at the second iteration. There are n-1 zeros and one > 1 in the bitmap. The random number selection selects a number in 0..n > with probability 1/n each. That's already wrong because each element was > supposed to be selected with probability 1/(n-1). That extra mass goes > to the element right after the one selected in the first round. I suck.
Skip ahead a random number of elements before performing the linear search. Sean
