numpy/numpy — pull request #5158 by staticd-growthecommons (2014-10-07 09:56:07+00:00)
Title: More efficient algorithm for unweighted random choice without replacement

1) The present algorithm applies a Knuth shuffle to the entire population and then truncates it to the requested size. This can be more efficiently achieved by not shuffling those elements that are not seen by the end user. Especially relevant when choosing small samples from a large population.

2) The present shuffling code is very general purpose. As what is being shuffled is an array of indices, specifying the type in the cython code gives significant speed benefits.

input size| output size| original | new
------- | ---------- | ------------ |-----
10 | 1 | 25.3 µs | 24.6 µs
10 | 3 | 25.5 µs | 24.7 µs
10 | 10 | 25.5 µs | 25 µs
100 | 10 | 40.6 µs | 25.2 µs
100 | 30 | 40.7 µs | 26 µs
100 | 100 | 40.8 µs | 28.2 µs
1000 | 100 | 190 µs | 29.7 µs
1000 | 300 | 192 µs | 35.7 µs
1000 | 1000 | 192 µs | 58.9 µs
10000 | 1000 | 1.68 ms | 76.4 µs
10000 | 3000 | 1.69 ms | 140 µs
10000 | 10000 | 1.71 ms | 363 µs