bugGNU Octave - Bugs: bug #45461, [octave forge] (statistics)...

 
 

bug #45461: [octave forge] (statistics) binornd inefficient, patch attached

Submitter:  None
Submitted:  Thu 02 Jul 2015 11:55:19 AM UTC
   
 
Category:  Octave Package Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  Michael Leitner Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * dev
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Mon 29 Nov 2021 08:55:25 PM UTC, comment #3: 
Nir Krakauer <nir_krakauer>
Thu 25 Nov 2021 09:58:46 AM UTC, comment #2: 

Nice that this old patch gets attention!

I still have no mercurial, thus here is the necessary change in verbatim:


      L = sum (k(:));
      ind = repelems ((1 : L), [(1 : L); n(k)(:)'])';
      p_ext = p(k)(ind)(:);
      rnd(k) = accumarray (ind, rand (sum(n(k)(:)), 1) < p_ext);


has to be the content of the if...endif block that makes up the main part of the patch. I took also the opportunity to tidy up the code by using accumarray -- this should make it more performant, I hope, and also more readable.

Michael Leitner <mleitner>
Wed 24 Nov 2021 06:51:30 PM UTC, comment #1: 

the attached patch is a diff patch, not a mercurial patch.  attached is a mercurial patch against the latest tip to make evaluation easier.

note i didn't check the function, but at a minimum 'test binornd' fails do to an output dimension mismatch (1x2 vs 2x1). So something is different that will need to be fixed before it can be pushed.

(file #52340)

Nicholas Jankowski <nrjank>
Group Member
Thu 02 Jul 2015 11:55:19 AM UTC, original submission:  

The present implementation of binornd is very inefficient. For non-scalar N it computes max(N(:))*numel(N) random values (and uses memory on the same order of magnitude). The attached patch uses only sum(N(:)) random values. Of course, the algorithm is still inefficient (one could work via the cdf), but for a range of use cases it is perfectly usable in contrast to the old implementation.

Demonstration:

N=ones(10000,1);N(1)=10000;
tic;binornd(N,.5);toc


takes 2.4 s for the old and 0.008 s for the new one.

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #52340:  octave-statistics-binornd-bug45461.patch added by nrjank (1KiB - application/octet-stream)
file #34360:  patch added by None (1KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by nir_krakauer (Posted a comment)
  • -email is unavailable- added by mleitner (Posted a comment)
  • -email is unavailable- added by nrjank (Updated the item)
  • -email is unavailable- added by None (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 group members can vote.

     

    Follow 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2021-12-16 nrjank StatusPatch Submitted Fixed
        Open/ClosedOpen Closed
    2021-11-24 nrjank Attached File- Added octave-statistics-binornd-bug45461.patch, #52340
    2019-06-08 rik5 Carbon-CopyRemoved 72865 -
    2019-06-08 rik5 StatusNone Patch Submitted
    2019-06-08 rik5 Carbon-CopyRemoved 72865 -
    2019-06-08 rik5 CategoryOctave Function Octave Package
        Summarybinornd inefficient, patch attached [octave forge] (statistics) binornd inefficient, patch attached
    2015-07-02 None Attached File- Added patch, #34360

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code