Efficient Random Sampling -- Parallel, Vectorized, Cache-Efficient, and Online

Peter Sanders, Sebastian Lamm, Lorenz Hübschle-Schneider +2

We consider the problem of sampling $n$ numbers from the range $\{1,\dots ,N\}$ without replacement on modern architectures. The main result is a simple divide-and-conquer scheme t…