JuliaStats/Distributions.jl — pull request #166 by one-more-minute (2013-12-19 16:15:31+00:00)
Title: More efficient wsample

I've implemented a more efficient (linear) version of `wsample` to replace the old (quadratic) version. As an added bonus, it returns samples in the same order they were given.

```julia
wsample(1:10, 1:10, 10)
[3,4,4,5,5,6,7,7,9,10]

@time wsample([1:10^5],[1.:10^5], 10^5);
# elapsed time: 9.988174193 seconds (2400352 bytes allocated)

@time wsample(1:10^5,1:10^5, 10^5);
# elapsed time: 0.023675562 seconds (800408 bytes allocated)
```

I've also removed the type hints, since they made the function unnecessarily restrictive; `wsample` will happily work on ranges, for example.

The reason I've added an attribution is that, as far as I know, this algorithm is original; but if I've stumbled onto common knowledge, I don't mind it being removed.