patchGNU Octave - Patches: patch #8669, C++ Implementation of sprand()

 
 

patch #8669: C++ Implementation of sprand()

Submitted by:  Daniele Calandriello <danielec>
Submitted on:  Thu 07 May 2015 12:43:16 PM UTC  
 
Category:  None Priority:  5 - Normal
Status:  In Progress Privacy:  Public
Assigned to:  None Open/Closed:  Open

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Fri 08 May 2015 09:13:26 PM UTC, comment #1:

At a glance, this looks promising. It's regrettable that we lose a big chunk of the m-file implementation, but perhaps it really is impossible to keep it.

Jordi GutiƩrrez Hermoso <jordigh>
Project Administrator
Thu 07 May 2015 12:43:16 PM UTC, original submission:

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.

Daniele Calandriello <danielec>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #33953:  sparse_cc.patch added by danielec (17KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jordigh (Posted a comment)
  • -email is unavailable- added by danielec (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

     

     

    Follow 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-05-08 jordigh StatusNone => In Progress
    2015-05-07 danielec Attached File- => Added sparse_cc.patch, #33953

    Back to the top


    Powered by Savane 3.3