While good in theory, it's often really slow in practice as even small sample sets can trash your cache and it still needs a random number for every element.

You can make a better approach using a much longer list, but then the math is far less elegant. EX: Add the first X * N elements to the list. Then remove 1/X of them. Then 1/X of the times add an element to the list until it’s full. Cull 1/X of them and then add new elements (1/X)^2 of the time. Repeat until you run out of elements at which point you cull the list back to X elements.

Downside is your generating ~N log N random numbers so scanning the list and then sorting a random set may be faster.

If you have an approximate number elements AND want a small percentage of them then randomly generate X * N element list which is then culled to an N element list.

Finally, if N happens to be close to the full number of elements you’re better off creating an exclusion list.

PS: Reservoir Sampling is only good if your memory constrained, need a constant time algorithm, and generating random numbers is expensive.