Tue 07 Mar 2017 12:14:56 AM UTC, comment #16:
I pushed the change to the development branch here (http://hg.savannah.gnu.org/hgweb/octave/rev/b7da08507fae). I added an input validation test on the input vector v to make sure it is numeric, logical, or char. I also added some more BIST tests. The example in the documentation was now in the wrong sort order so I updated that as well.
Marking as fixed and closing report. Thanks Michael.
|
Mon 06 Mar 2017 08:47:47 AM UTC, comment #15:
Then let's say in the second paragraph of the documentation
Results are returned in inverse lexicographic order. Possible repetitions of entries are neglected, that is, the result has always size @code{factorial (@var{n}) * @var{n}}, where @var{n} is the length of @var{v}. For generating only differing permutations use @code{unique (perms (@var{v}), "rows")(end:-1:1,:)}.
Of course, this is now again a point where it would be more efficient to do this natively in the algorithm as opposed to afterwards. This non-matlab behaviour could be invoked by an additional argument to perms, but I think we wait until somebody really wants this, right?
|
Mon 06 Mar 2017 07:53:19 AM UTC, comment #14:
Matlab gives all the 4! permutations of [true,false,true,false].
|
Sun 05 Mar 2017 11:33:07 PM UTC, comment #13:
Compared to my previous post, I hope to have made the function conform to the coding conventions, I added tests (also to test for the behaviour that was the cause of this bug report), I made a small modification to make it work with strings, and I made it more efficient for small arguments by hardcoding the cases for length(v)<=3.
To address the questions in this thread: Originally, I took the perms.m from Octave 3.6.4 installed at my machine, and as it displayed the bug, I started to work on it. So in my previous post, when I was talking about the "original algorithm", that meant 3.6.4. In this implementation, the resulting permutation of v with length n was computed conceptually recursively, where the permutation of v(2:end) is taken and v(1) inserted first before the first column, then between first and second, and so on. This is effective, particularly if v has a small data type, but I did not quickly find a way to make this display the desired ordering of the output. Therefore, I developed another algorithm, where a permutation of indices is computed, and only at the end v is expanded. Now I see that this idea of permutation of indices (but with the old ordering) was implemented by Jordi in 2012 to make perms work with strings.
In testing this implementation I found out that indexing is much faster when done with standard double matrices than with integer datatypes, which surprised me, as this can only mean that in Octave integer datatypes are first cast to double and then back to integer to give the memory addresses. Therefore, I stayed with doubles. This was what provoked my comment that, should direct integer addressing one day be implemented, one should change the index datatype here, which would make the algorithm more efficient. However, I now see that Arun Giridha in 2013 did change the indexing to uint8 to decrease memory usage (but according to my testing this did incur performance loss). In my implementation, this is not an issue, as I do the conceptually recursive index permutation only up to n-1, and construct the final returned matrix out of v in n steps. For large n, this is both more efficient in terms of time and takes less memory even with double indexing.
So the answers: compared to the current implementation, my implementation should (I hope) be faster, as it uses double indexing, while using less memory (with uint8-indexing the memory usage could be decrease by an insignificant part, but with the above-mentioned hit in performance).
One last point came to me: in the matlab documentation of perms they give the example of [true false true false] as input vector (but they do not give the expected result). Octave says in the documentation "generate all permutations of V", which I would understand to be only six in this case, as "all permutations" to me seems to imply "all different permutations". However, this is at odds with "the result has size factorial (N)...", and with the behaviour of my code (and it seems all octave-perms before). How does matlab do this, and should we make the documentation more precise?
(file #39897)
|
Fri 03 Mar 2017 04:19:02 PM UTC, comment #12:
Only thing left is to clean up the script to follow Octave core coding conventions and then we can commit it to the dev branch.
|
Fri 03 Mar 2017 10:29:14 AM UTC, comment #11:
Thank you everybody for your support!
It's amazing. The function is getting faster, is consuming less working memory, and becoming more compatible. Any wish still left open? ;-)
I have been browsing through the time lapse of the documentation of perms() archived at the "waybackmachine".
Octave bug 30114 is dating back to 2010-06.
There has been no sorting order defined until 2012-12 (=R2012b):
https://web.archive.org/web/20121219081641/http://www.mathworks.com/help/matlab/ref/perms.html
The first occurrence is 2013-03 (=R2013a):
https://web.archive.org/web/20130318033107/http://www.mathworks.com/help/matlab/ref/perms.html
However, according to Mathworks bug 1265636, it has not been working reliably in all cases from R2013a to R2015b.
R2016a is the first version where sorting order is defined + working as expected.
|
Thu 02 Mar 2017 08:26:35 PM UTC, comment #10:
I benchmarked the old and new perms functions. The new function is slightly faster, about 16% improvement at N = 10.
bm_perms.m code
Results
perms : median = .189
perms_new : median = .157
-16.9% improvement
If I switch to using 'uint8' then the median is .187 which basically erases any savings.
So, I think this just needs to be updated to follow Octave coding conventions.
|
Thu 02 Mar 2017 07:27:14 PM UTC, comment #9:
Also, see the bug report #30114 which is the same issue reported 7 years ago. As documented then, there was a reluctance to change the function because there was no stated ordering by Matlab and there was the very real possibility that Matlab would change its ordering in the future. That is confirmed in comment #0 where the behavior changed from R2015B to R2016B. If you must have a specific order for a set of permutations then your scripts should ensure that in some manner.
On the other hand, Octave is always happy to have faster, high-performance code. The calculation in the existing perms.m was specifically done in uint8 to limit memory consumption. How bad is the performance hit that you talk about?
I used an input of 1:10 to both perms.m and perms_new.m and ran both through the debugger to inspect the memory usage.
For perms.m:
Essentially, 40MB worth of intermediate values.
For perms_new.m
The new method only has 28.5MB of intermediate values so it is an improvement on the old script.
The script needs to be updated to follow Octave coding conventions, and I would like an estimate of the performance hit to use uint8 and whether there is a workaround, but otherwise this looks like a good addition to Octave.
|
Thu 02 Mar 2017 03:23:33 PM UTC, comment #8:
Dear Michael,
your perms_new is faster than perms on my 4.0.2
and seems to give the right ordering. Congratulations. Which algorithm did you implement? Can you adapt the syle to http://wiki.octave.org/Octave_style_guide and add proper tests?
|
Thu 02 Mar 2017 10:56:18 AM UTC, comment #7:
See the attached reworked perms.m. In my 3.8.0 it is slightly slower than the original algorithm for large V (that is, length(V)==10), but about equally efficient for length(V)==5. In the used algorithm, the indices are permuted n times, while in the original one the values themselves are permuted. It seems that in Octave this index permutation is most efficient when done in data type double. In principle, here one would need to use only uint8, which would correspond first to much less bits being moved around, and second all casts from double to integer would become unnecessary. Perhaps in later Octave versions integer addressing will become more efficient, then this could be used here.
The new ordering should be correct, I hope.
(file #39878)
|
Thu 02 Mar 2017 10:01:41 AM UTC, comment #6:
Can I work on this?
|
Thu 02 Mar 2017 02:31:58 AM UTC, comment #5:
For performance, I think the internal algorithm in perm.m should just be reworked to generate the index vector in the correct order rather than using the additional sortrows operation.
|
Thu 02 Mar 2017 12:08:09 AM UTC, comment #4:
So this could be solved with a simple change
which seems to work for me but is likely less efficient.
Or by lexicographically sorting the input vector first, which should be more efficient, and figuring out how to adjust the loop index construction logic to ensure that it produces the permutations of v in the right order.
|
Wed 01 Mar 2017 09:01:24 PM UTC, comment #3:
Okay, I've marked the bug as confirmed and changed it's category to "Octave Function". I've change the severity to minor, since there are already workarounds available by using, for example, sortrows.
|
Wed 01 Mar 2017 08:49:40 PM UTC, comment #2:
I have to correct myself. In fact, there are two issues:
- There should be a sort order. The documentation of Matlab says "in reverse lexicographic order".
https://de.mathworks.com/help/matlab/ref/perms.html
In that sense, Octave 4.2.0 is not compatible.
- There is a bug report 1265636 which says that in the releases from R2013a to R2015b, the sort order ist just wrong.
|
Wed 01 Mar 2017 06:35:10 PM UTC, comment #1:
The one-line summary of the function from the documentation for perms is
The fact that the perms documentation doesn't mention any sort of order implies to me that there is no order. It doesn't appear to me that we need to re-iterate that, although if others are confused I suppose we could.
|
Wed 01 Mar 2017 10:28:26 AM UTC, original submission:
It might be worth noting in the documentation that the sort order of perms() is arbitrary. Results may change from version to version, and when switching from Octave to Matlab or Scilab. M-code that is relying on the sort order will give different results.
A defensive programming style would be to write something in the form of "sortrows(perms(xxx), [yyy])"
Example output:
Octave 4.2.0
>> perms(1:3)
ans =
1 2 3
2 1 3
1 3 2
2 3 1
3 1 2
3 2 1
Matlab R2015b
>> perms(1:3)
ans =
3 2 1
3 1 2
2 3 1
2 1 3
1 2 3
1 3 2
Matlab R2016b + R2017a Pr
>> perms(1:3)
ans =
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3
|