4

Given an unknown length list, return a random item in it by scanning it only 1 time.

My idea:

A similar algorithm is Reservoir Sampling (posted by others). But, it is too complicated because it needs to run rand() and keep k nodes each iteration.

Is there a better solution? O(n) time and O(1) space?

8
  • Do you mean O(n), do you really mean "at most one scan of the entire list"? These are not the same thing... Jan 1, 2012 at 19:39
  • Only 1 time scan. the algorithm complexity cannot be worse than O(n). Jan 1, 2012 at 19:41
  • 2
    In your case, k=1, so I'm not sure what the problem with reservoir sampling is. Jan 1, 2012 at 19:43
  • In reservoir sampling, k is independent from n. Simply set k = 1 and that complication vanishes. You won't avoid running rand on each iteration. Jan 1, 2012 at 19:46
  • @Potatoswatter: What happens if you use the same value of rand for every iteration? Jan 1, 2012 at 19:50

4 Answers 4

5

Why are you against reservoir sampling? You happen to be doing it with k = 1. There are minor optimizations (e.g. you don't need to select 1 out of the k, since k = 1) but it's the right approach. You could try to optimize by keeping processing a fixed window at a time, do the math to figure out with equal probability if you should choose any of the items in your window instead of the one you have, etc. to minimize rand() calls at the expensive of a more complicated algorithm, but you're going to wind up back at reservoir sampling more or less anyhow.

0
3

You use reservoir sampling.

This is not too complicated nor expensive; it is the minimal approach given the constraints that you have (selecting an element from a stream).

It works just fine if you want a random sample size of 1 and if all the elements have the same weight.

When you've simplified the code with a k of 1 and no explicit weighting, its still reservoir sampling.

Not all pseudo random number generators run at the same speed; pick a fast one.


Comments ask what would happen if you re-used the same random number rather than generating a new random number each step:

The Wikipedia link given shows the equivalence to the Yates-Fisher/Knuth shuffle. If you asked what would picking the same random number each step of the shuffle would be, you'd be barking.

2
  • What happens if you only call rand once, and use that value for all iterations? Jan 1, 2012 at 19:58
  • @OliCharlesworth I put that in the answer since you keep asking ;)
    – Will
    Jan 2, 2012 at 7:24
1

See the Perl cookbook for the algorithm, which you'll easily adapt to C++.

Basically, scan the list once, and for each entry with index i you read, keep it if a random number between 0 and i+1 is less than 1.

The result is the last entry kept.

1
0

Solution in C (implementation of reservoir sampling with k=1): You may want to use "unsigned long long" for count.

unsigned int chosen, num, count;
count = 1;
get_number(&chosen);
while (get_number(&num)) {
    count++;
    if (rand() % n == 0) chosen = num; 
}

Keeping k nodes per iteration is easy, when k=1.
It does run rand() each time, which is somewhat heavy. You may get reasonable results with a much simpler pseudo-random function. But this would make the code more complicated, not more simple.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.