[Octave-bug-tracker] [bug #63962] perms - Performance - Usage of native C++ algorithm helpful

[Hendrik K]

Follow-up Comment #16, bug #63962 (project octave):

Attached is the patch created in my octave build directory. It works and
passes all tests for perms when executing make check. 
I hope everything is ok: it is my first patch using mercurial and for
octave....
 

The patch already caters for identical unique and non-unique reverse
lexicographic ordering
(https://hg.savannah.gnu.org/hgweb/octave/rev/29e0d557a3be) including the
documentation changes.

Also it supports "unique" for cell arrays in perms as discussed in this post
and in https://savannah.gnu.org/bugs/?63965. 
"unique" works for cell arrays containing all basic numerical types and
strings albeit not for nested data containers where existing octave equality
is not supported throwing an error like "error: binary operator '==' not
implemented for 'cell' by 'cell' operations".
 
In theory the method "is_equal" for the generic data container octave_value
could be extended to cover recursively nested data container and then the
perms.cc code would work out of the box. But Octave is a math language, so
supporting such a construct seems for me of a little value as it is not in
scope of the normal use cases and a normal user.

Note that this "unique" support for cells is not a regression compared to
current perms, so keeping it makes sense I think. But it can be deactivated by
simply removing the parameter unique_v when calling GetPermsNoSort in the c++
code as well as removing the asserts covering this if decided as such.

In any case the implementation is fast enough requiring n * (n-1) / 2 mutual
comparisons. I tested it with 170 identical values (it would be pure madness
in reality giving so many values to perms) and it takes less than 5ms on my
machine.   
As we are speaking about permutations, n=171 factorial(171) would blow the
system even with doubles... 


https://savannah.gnu.org/bugs/?63965 continues to track the cell array
discussion.



   

@Arun-
thanks for your great support.

(file #54536)

    _______________________________________________________

Additional Item Attachment:

File name: patch_63962                    Size:21 KB
    <https://file.savannah.gnu.org/file/patch_63962?file_id=54536>



    _______________________________________________________

Reply to this item at:

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

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