[Octave-patch-tracker] [patch #8669] C++ Implementation of sprand()

[Daniele Calandriello]

URL:
  <http://savannah.gnu.org/patch/?8669>

                 Summary: C++ Implementation of sprand()
                 Project: GNU Octave
            Submitted by: danielec
            Submitted on: Thu 07 May 2015 12:43:16 PM GMT
                Category: None
                Priority: 5 - Normal
                  Status: None
                 Privacy: Public
             Assigned to: None
        Originator Email: 
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

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 4-5x 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 Sparse-f 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.



    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Thu 07 May 2015 12:43:16 PM GMT  Name: sparse_cc.patch  Size: 17kB   By:
danielec

<http://savannah.gnu.org/patch/download.php?file_id=33953>

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/patch/?8669>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/