There are n items (n is known and > 1,000,000,000).
I want to randomly ‘mark’ x% of n-items in stream.
(n and x are known)
Items are in stream ,one directional (you can’t go back) processed item goes to output stream. Items should be picked randomly as well, meaning I can’t take the first %x of items in stream.
complexity should be <= O(n).
My question:
Will it be correct to “test” each item independently?
Meaning, take item from stream -> x% to mark it…
Take next item…
2
Lets say you have n items and know you want to mark m items, m<=n (according to the % value). Now you mark the items one-by-one, starting with a random probability of m/n for marking the first item. But instead of keeping that probability fixed, after each step you adapt the actual probability to what is needed now!
So when after k steps you have marked l items, you will have to process (n-k) remaining items, and you want to have (m-l) of them marked. So choose the probability of the next item as (m-l)/(n-k).
As you see, the more l approaches m, the smaller the probability of marking will become. When l is equal to m, the probability is 0. On the other hand, when the number of remaining items reaches the number of remaining items to marked, the probability will become 1. Finally, you will end up with exactly m marked items.
It should be obvious that the run time is O(n), since each element is processed once, and the only thing you have to keep track is the both numbers (m-l) and (n-k).
4
It will be asymptotically correct, i.e. it will provably tend to approach the specification as time goes on. However, for an unspecified amount of time, it will deviate from the specification, possibly quite severely (and possibly much more than it would have to, given that you can’t partially mark an item).
Whether that is good enough for your use case is a question that only you can answer. If you do have to approximate the specified percentage as closely as possible, then your suggestions is not good enough, and you’ll have to maintain additional counters as well. (However, that shouldn’t take you out of the realm of linear-time solutions.)
1
If you simply mark x% by probability independent for each item you might not end up for a fixed n with exactly x% of the n items.
I recommend something like this:
n is known, so you can calculate how many items you have to mark markSize=n*x/100.
Now take the first markSize items from the stream and while reading the rest of the stream replace them randomly by the related probability.
The simplified example, if you want to mark one out of a stream of n:
- take the first one as mark-candidate
- read the second one from the stream and replace your old mark-candidate by it with a probability of 1/2
- read the third one from the stream and replace your old mark-candidate by it with a probability of 1/3
- and so on
(In this case you do not even need to know n up front.)
This idea can be generalized for any number of items to mark from a stream. Since you only read the stream once, the time complexity is O(n).
3
It should work acceptably in your use case. The general rule is that the distribution of the number of marked items across many sample will have mean e (where e is n times x%) and standard deviation sqrt(e). This means you have 99.7% chance that the number of marked items will fall between e-3sqrt(e) and e+3sqrt(e). Let’s say n=1,000,000,000 and x=1%. Then e=10,000,000 and sqrt(e) is roughly 3,000. You can have 99.7% certainty that the number of marked items will fall between 9,994,000 and 10,006,000. That’s probably good enough for your purposes. As x becomes very small, though, the accuracy decreases.