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

 
 

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

Submitter:  Daniele Calandriello <danielec>
Submitted:  Thu 07 May 2015 12:43:16 PM UTC
   
 
Category:  Core : new feature Priority:  5 - Normal
Status:  Postponed Privacy:  Public
Assigned to:  None Open/Closed:  Open
* Mandatory Fields

Add a New Comment Rich Markup
   

Sat 18 Jan 2020 10:52:27 AM UTC, comment #2: 

Review for Octave 6.

Unfortunately as expected, this patch does no longer cleanly apply to the development branch.

As Jordi says, it looks promising.  Sorry for all your work not to be applied for almost five years.  Maybe the state "in progress" kept us in a wrong illusion there was progress on this item.

Setting to "postponed", until the patch gets refactored and tested.

Kai Torben Ohlhus <siko1056>
Group Member
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>
Group Member
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 siko1056 (Posted a comment)
  • -email is unavailable- added by jordigh (Posted a comment)
  • -email is unavailable- added by danielec (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-01-18 siko1056 CategoryNone Core : new feature
        StatusIn Progress Postponed
    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.13-f8d8.
    Corresponding source code