[Octave-bug-tracker] [bug #63992] nchoosek has suboptimal performance

[Hendrik K]

URL:
  <https://savannah.gnu.org/bugs/?63992>

                 Summary: nchoosek has suboptimal performance
                   Group: GNU Octave
               Submitter: koerhen
               Submitted: Mon 03 Apr 2023 11:35:12 AM UTC
                Category: Performance
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: dev
         Discussion Lock: Any
        Operating System: GNU/Linux
           Fixed Release: None
         Planned Release: None


    _______________________________________________________

Follow-up Comments:


-------------------------------------------------------
Date: Mon 03 Apr 2023 11:35:12 AM UTC By: Hendrik K <koerhen>
The current nchoosek implementation is performing sub optimally despite using
a reasonably complex partial vectorization logic.

Using c++ brings the following benefits
- Straightforward algorithm to determine n over k numerically
- Usage of an elegant and fast algorithm to create n over k combinations of
elements relying on the standard std library function std:permutation
(permutations of a set of position logical values allows deriving the
combinations).

The achieved performance gains are material:
- calculating n over k is about five times faster
- creating all combinations of a set of items is about twice as fast.

tic; for i=1:25; a = nchoosek(50,i); endfor; toc;
tic; for i=1:10; a = nchoosek(1:25,i); endfor; toc;



A patch is attached passing all existing BISTs.

Personal note:
I think that in general, native octave language code for octave functions
should only be replaced by C++ code if
a) the C++ code is straightforward, therefore the effort in C++ is limited
(e.g. nchoosek.cc reuses the straightforward design pattern of the perms.cc)
and
b) if it brings material benefits.






    _______________________________________________________
File Attachments:


-------------------------------------------------------
Date: Mon 03 Apr 2023 11:35:12 AM UTC  Name: nchoosek_v0  Size: 24KiB   By:
koerhen

<http://savannah.gnu.org/bugs/download.php?file_id=54553>

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?63992>

_______________________________________________
Message sent via Savannah
https://savannah.gnu.org/