const tweetIDs = {};
while(TWEET_COUNT){
const rnd = Math.random() * MAX_TWEET_ID;
if(!tweetIDs[rnd]){
tweetIDs[rnd] = true;
TWEET_COUNT--;
}
} const tweetIDs = {};
while(TWEET_COUNT){
const rnd = Math.random() * MAX_TWEET_ID;
if(!tweetIDs[rnd]){
tweetIDs[rnd] = true;
TWEET_COUNT--;
}
}* IDs are returned in sorted order
* IDs are generated one after another, ie could be implemented as a generator or coroutine
* No additional space required during the computation
Resulting in a single pass.
I was thinking of ways to solve the problem by eliminating the overhead of checking whether a random number was already drawn, when Vitter's solution was to make the random number generator produce random numbers in a sorted manner, thus eliminating that overhead entirely.
EDIT: Then again... if the algorithm is to be used to shuffle a list, wouldn't returning the selection in a sorted manner defeat the entire purpose? If k = n, output would be input...
If there's a chance to randomize the entire tweet archive, then it's a shuffling algorithm now.
This is key. The author does not explain this well, or at all. If you require the IDs in sorted order, you need this algorithm.
If you don't mind or want them shuffled, use a permutation function.
(the idea of shuffling afterwards is nonsense, if you could do that, you can also check for duplicates when drawing)
This will take longer time at each iteration and when both MAX_TWEET_ID and and TWEET_COUNT is large and close to (or equal to) each other it may take very long to complete.
As k approaches n the expected number of draws needed to get k unique values increases faster than O(k).