The attached file is a patch to implement part of the sprand() function in C++.
It covers base uses of sprand() and sprandn(), but it does not cover the
sprand (M, N, D, RC)
invocation since this involves fundamentally different properties.
The implementation makes use of existing octave random generating functions. I also used std::set().
The implementation is aimed mostly at being memory efficient. This is also the justification for writing this function in C++. The current implementation creates several intermediate structures, and can use 45x times the minimum necessary memory. When dealing with large matrices (the whole point of sprand), sometime we cannot even generate the random data. C++ increases the code maintenance cost, but the modifications are well confined. It is also possible to mitigate the memory problem by creating the matrix incrementally (for example separating the construction in 10 blocks). I have this implemented in an .m file, but it is slower than the C++ implementation, and finding a good block size is quite problem dependent.
sprand and sprandn will now call the C++ _sprand_impl_basearg_ for the base case, and _sprand_impl_6arg_.m for the 4 arguments case, this replaces the private _sprand_impl_.m
_sprand_impl_basearg_ manages the input, and the special case of sprand(A) where A is a matrix, otherwise calls octave_rand::sparse_array
octave_rand::sparse_array is implemented using template <typename T> Sparse<T> octave_rand::do_sparse_array_templ
octave_rand::do_sparse_array_templ allocates the necessary memory select a random element x_{i,j} with an uniform distribution over i,j and fills it with the appropriate random value
the remaining modifications take care of the build process (is Sparsef even supposed to exist?).
I have left a bunch of FIXME mostly as request for doubts I have on octave's internal implementation of octave_rand
The main algorithmic flaw I see in the current implementation is that it tries to fill the set 1:n by uniformly sampling from it.
Apart from a possible rounding problem, this is a really crude implementation of sampling without replacement, and can perform quite badly for large n and dense vectors (which is not my use case).
The patch builds and passes tests against rev. 20157 (e410d62ae2c840d1f0d043539818fa9fbf940edf), but was developed looking at rev 20026.
Since this is my first patch, feedback is really appreciated.
