JuliaStats/StatsBase.jl — pull request #54 by one-more-minute (2014-04-07 10:52:55+00:00)
Title: Add ordered sampling without replacement algorithm

This algorithm was originally accepted and then removed due to performance concerns (#45). Hopefully we can discuss those concerns and consider reinstating it.

I've already outlined the performance characteristics in #45:

> for `k << n`, Fisher-Yates+Sort is indeed faster. However, for (roughly) `k > n/20`, my algorithm becomes better; in fact, for `k > n/10` it's faster than Fisher-Yates *before you even get to the sort*.

> For example, if I want `9e7` samples out of `1e8`, Fisher-Yates+Sort takes 23 seconds versus 1.5 for my code - a *15 times* improvement. And this isn't just limited to large values of `n`; sampling 50 values out of 100 is 2.5 times faster with my code, and remains faster as low as `k = 3` (albeit not by much).

Please try `@time StatsBase.sample(1:10^8, 9*10^7, replace=false, ordered = true)` with and without the change if you're not convinced.