The problem of sampling without replacement: given integers n, k such that 0 ≤ k ≤ n, return k distinct nonnegative integers < n, choosing at random such that every possible result is equally likely. One way to get a precise understanding of the problem is to look at the simplest algorithm for solving it, via these Python, C++ or Rust implementations.
This repository surveys algorithms for this problem. It implements twelve of them in Python, C++ and Rust, and benchmarks the C++ and Rust implementations over a wide range of n and k, for both sorted and random order output. The C++ implementations use only what the C++ standard library provides; the Rust ones use Rust's standard library, whose hash tables and sort are much faster.
No algorithm is the best at every n and k, so an implementation might choose between a few. Choosing algorithms gives the best such sets, scored by the worst time per number output in each decade of k. But Cardchoose alone is never more than 9–22 ns per number slower than the best three algorithms together, in any case, and it is the best single algorithm in three of the four cases.
- Guide to algorithms tested
- Benchmark results
- Explorer: pick n and k and compare every algorithm there
- Paper: "Cardchoose: simple, fast sampling without replacement"
- Choosing algorithms
- Pairwise comparisons: ratio of times, difference in time/k
- Making the timings trustworthy
- Running this software
This repository also presents a new algorithm for this purpose, Cardchoose. It is to my knowledge the only algorithm which is both simple and performs within an acceptable distance (in time per output) of all other solutions across the entire parameter space tested. It needs no memory beyond the output vector and runs in O(k log k) time.
Cardchoose in Python:
def sorted_choose(n, k):
"k distinct integers 0 <= x < n, sorted"
t = n - k + 1
d = [None] * k
for i in range(k):
r = random.randrange(t + i)
if r < t:
d[i] = r
else:
d[i] = d[r - t]
d.sort()
for i in range(k):
d[i] += i
return d