4
$\begingroup$

Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so.

I have quite a large bitmap (~100 Million bits) (e.g. 100100101001010001001...010010). The bitmap is just an example, it doesn't have to start with 1 or end with 0.

Now, I need to choose randomly any 0-bit from the bitmap and retrieve it's position. Memory is not an issue in my case, I can maintain a few copies of the bitmap, if necessary. But the acceptable complexity of the algorithm would be linear or O(n lnn) in the worst case. Couldn't you advice a direction to move to? I'll appreciate any advices or refernces to some related resources.

$\endgroup$
4
  • 2
    $\begingroup$ Practically speaking, bitmaps usually contain a decent fraction of zeroes, and so the trivial randomized algorithm works in $O(1)$ random accesses. Should your algorithm work in the worst case? Is random access for free? Do you care about time, space or both? Please state your exercise in full. $\endgroup$ Oct 29, 2015 at 12:32
  • $\begingroup$ @YuvalFilmus Should your algorithm work in the worst case? Yes. Is random access for free? Yes. almost for free, it's very inexpensive in my case. Do you care about time, space or both? About time. $\endgroup$
    – St.Antario
    Oct 29, 2015 at 12:41
  • $\begingroup$ @YuvalFilmus bitmaps usually contain a decent fraction of zeroes, and so the trivial randomized algorithm works in O(1) random accesses. What do you mean trivial randomizer? Couldn't you expland a bit or give a refernce? $\endgroup$
    – St.Antario
    Oct 29, 2015 at 12:42
  • 2
    $\begingroup$ Buzzword: rejection sampling. $\endgroup$
    – Raphael
    Oct 29, 2015 at 17:40

1 Answer 1

9
$\begingroup$

There is a simple $O(n)$ algorithm using the technique of reservoir sampling. Keep a currently selected element $x$ (initially, none). Go over all bits in the file in order. When seeing the $m$th zero, put it in $x$ with probability $1/m$. You can show (exercise) that the final contents of $x$ is a uniformly random zero from the file.

If you are allowed preprocessing, you can store the locations of all zeroes in a new file, and then choose a uniformly random zero in $O(1)$ by choosing a uniformly random position in the list.

Practically speaking, we expect bitmaps to contain a decent fraction of zeroes – say at least 1%. This suggests querying uniformly random locations in the file until you reach a zero. The expected runtime of this algorithm is at most 100 random queries.

$\endgroup$
2
  • $\begingroup$ The question may sound dumbly, but there's no constant time algorith for such bitmaps even if the random has a constant-time complexity, isn't? $\endgroup$
    – St.Antario
    Oct 30, 2015 at 6:29
  • $\begingroup$ @St.Antario It depends on the model and the assumptions. $\endgroup$ Oct 30, 2015 at 8:00

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.