JuliaLang/julia — pull request #6726 by stevengj (2014-05-03 02:35:20+00:00)
Title: faster sprand, new randsubseq (fixes #6714 and #6708)

This patch implements a much faster `sprand` (fixing #6708), by filling in the matrix one column at a time. It also changes the meaning of the specified `density` to something that is (I think) easier to explain: the probability of any element of the matrix being nonzero is (independently) given by `density`.

A subroutine used by both this `sprand` and the previous `sprand` is a function to compute a random subsequence of a given `AbstractArray` (e.g. `1:n`). Since this is generally useful functionality, it seemed sensible to export it as functions `randsubseq(A, p)` and `randsubseq!(S, A, p)`. What these functions do is to create a random (ordered) subsequence of `A` by selecting each element of `A` with independent probability `p`. (This is different from the problem of finding a random subset of a fixed size.)

`randsubseq` is implemented using a new algorithm different from the previous one (which had the same mean but a more complicated, and I think less useful, distribution). The new algorithm is somewhat faster, requires no temporary arrays, and has Θ(`p * length(A)`) complexity, and fixes the statistical bug of #6714; it is inspired by an algorithm by Vitter for a related problem.