Sorry, I deleted this comment immediately after posting but you managed to respond to it too quickly, it originally said:
>Having a large input set of known size (and your result set is not large) is not a time when you would want to use reservoir sampling. Such a problem can be solved in O(k) where k is the size of the result set, while reservoir sampling is O(n) where n is the size of the input set.
>Having a large input set of known size (and your result set is not large) is not a time when you would want to use reservoir sampling. Such a problem can be solved in O(k) where k is the size of the result set, while reservoir sampling is O(n) where n is the size of the input set.
and I have responded here: https://news.ycombinator.com/item?id=9158903