3 ms·
The algorithm described in the article has other desirable properties: * IDs are returned in sorted order * IDs are generated one after another, ie could be i
by coleifer 7y ago
The algorithm described in the article has other desirable properties:
* 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.
- klingonopera 7y agoNicely said. 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...
- tiborsaas 7y agoIt would. The original problem is to draw a subset of tweets. If there's a chance to randomize the entire tweet archive, then it's a shuffling algorithm now.
- tripzilch 7y ago> * IDs are returned in sorted order 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)