bugGNU Octave - Bugs: bug #60364, New option "unique" for...

 
 

bug #60364: New option "unique" for perms

Submitter:  None
Submitted:  Sat 10 Apr 2021 01:20:25 AM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Fixed Assigned to:  None
Originator Name:  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
   

Jump to the original submission

Tue 05 Jul 2022 03:58:13 PM UTC, comment #12: 

I made small changes to more closely follow Octave coding conventions (http://hg.savannah.gnu.org/hgweb/octave/rev/46e15523ca06).

Marking bug as Fixed and closing report.

Rik <rik5>
Group administrator
Mon 20 Jun 2022 09:30:42 PM UTC, comment #11: 

Thanks. I've pushed your technique here: https://hg.savannah.gnu.org/hgweb/octave/rev/05729b0e39e4

Reopening and marking as Ready For Test.

Arun Giridhar <arungiridhar>
Group Member
Mon 20 Jun 2022 07:02:47 PM UTC, comment #10: 

It seems that between the ancient octave version I used to write and test this and the current one, the third output of unique() became a column vector, where before it was a row vector. So just change the offending line to


h = accumarray (j, 1)';


and it should be fine.

Michael Leitner <mleitner>
Mon 20 Jun 2022 06:18:29 PM UTC, comment #9: 

@mleitner: I'm getting an error. Could you look into it pls?


octave:1> v = "aaaabbbbcccc"; tic; p = perms_m (v, "unique"); toc
error: transpose not defined for N-D objects
error: called from
    perms_m at line 146 column 8


That's this line:

      h=accumarray(j',1)';


Independently of that fix, I am attaching an updated version of your code. Please review. The changes are: replacing generic `end` with `endif`; spacing like the other Octave m-files; replacing the variable `i` with `ii`; replacing the multiple calls to `size` with variables; replacing `size(x,1)` and `size(x,2)` with the faster `rows(x)` and `columns(x)`.

(file #53327)

Arun Giridhar <arungiridhar>
Group Member
Mon 20 Jun 2022 07:10:45 AM UTC, comment #8: 

With a one-line change (a sortrows() on the index array) the tests pass. It does take a bit of efficiency, but it is still much faster than Arun's implementation, also much faster than unique(perms(v),"rows"), and it has the advantage that the restriction of reverse lexicographic ordering holding only when "unique" is not given is not needed any more. Also, when the input vector has no repetitions, specifying "unique" or not gives the same result (only takes longer). For efficiency, I reintroduced the old code for the non-unique case.

(file #53323)

Michael Leitner <mleitner>
Sun 29 May 2022 11:43:32 PM UTC, comment #7: 

@mleitner: I'm perfectly OK with my technique being replaced by a faster algorithm but it does need to pass the BISTs. If the only thing failing the BISTs is the order of the output, the BIST in question can be edited to match the sequence, or the BIST can use sortrows if needed. Could you work that in and also recover the performance of the plain perms without the call to unique?

Arun Giridhar <arungiridhar>
Group Member
Sun 29 May 2022 05:43:58 PM UTC, comment #6: 

Sorry for the belated response, but please consider the attached proposal: it is a reworking also of the non-unique part of perms, so that the two options use the same code path. It is a bit less time-efficient than the old version of the non-unique case (some 10% at large problems, up to somewhat like a factor two for smaller ones), but much more efficient for the unique case (up to a factor 20 for large problems -- on my less powerful computer, the case reported below is 6 seconds in the trivial unique(perms(v),"rows") implementation, 0.19 seconds in the new implementation of Arun , and 0.014 seconds in mine). I did not analyse the old code in detail, but it could be that my implementation is more efficient in terms of memory.

As it is, it does not pass the BISTs, but as I see it, this is only because of the ordering of the returned permutations. I think that it should be possible to give the reversed lexicographic ordering that is currently promised, and as it is the same code path, the same should hold for the unique case (where Arun's implementation makes no promises). But apart from that, it should be correct, as far as I have tried. If you are interested, I could try to fix the ordering.

Of course, you could leave the old non-unique case untouched and use my implementation for the unique case, which should give the best performance overall. But I would judge the simplification of having a common code path to be worth the loss in performance.

(file #53258)

Michael Leitner <mleitner>
Sun 29 May 2022 01:31:17 AM UTC, comment #5: 

I reviewed and made some changes to follow Octave coding conventions and checked in the result here: https://hg.savannah.gnu.org/hgweb/octave/rev/b949f8a631e2.

Marking as Fixed and closing report.

Rik <rik5>
Group administrator
Wed 25 May 2022 10:04:34 PM UTC, comment #4: 

Turned it into a full changeset and pushed here: https://hg.savannah.gnu.org/hgweb/octave/rev/f03e1eebf46d

Marking as Ready For Test.

Arun Giridhar <arungiridhar>
Group Member
Wed 25 May 2022 02:11:46 AM UTC, comment #3: 

It didn't look like anyone was working on this, and I had a similar problem myself, so I went ahead and implemented it using a very different technique. It uses much less memory than unique (perms (...), "rows"), and for certain inputs it is actually faster. E.g. for v = [1  1  1  1  2  2  2  3  3  3], unique(perms(v),"rows")) takes 0.670 seconds while perms (v, "unique") takes only 0.037 seconds.

Patch attached with some BISTs. Passes make check.

I am also retitling this report.

(file #53253)

Arun Giridhar <arungiridhar>
Group Member
Sat 10 Apr 2021 07:47:18 AM UTC, comment #2: 

Sorry, I made a mistake: when you expand the multiset permutation at step i, you first have to pre-allocate the new multiset permutation, set every entry to i, and then overwrite the entries at nchoosek(1:sum(n(1:i)),sum(n(1:i-1))) by the entries of the multiset permutation from the previous step.

Example: assume we want the permutations of [1 1 1 2 2 3 3 3 3], that is, n=[3 2 4]. Then at the second step we have a ten-row incoming permutation (bincoeff(n(1)+n(2),n(2))=10). After this step, each of these rows will have become bincoeff(n(1)+n(2)+n(3),n(3))=126 rows. So for each incoming row j conceptually you have to preallocate an index matrix out=3*ones(126,9), and then say


out((1:126)'+(nchoosek(1:sum(n(1:i)),sum(n(1:i-1)))-1)*126)=in(j,:)(ones(126,1),:);


And for this to be performant, you should not treat each row on its own, but all at the same time by index arithmetic, which I do not have time to work out at the moment.

Michael Leitner <mleitner>
Sat 10 Apr 2021 07:20:44 AM UTC, comment #1: 

Good idea, but, first, I doubt that the octave maintainers will be willing to introduce a new function into the main namespace. What seems more likely is if you propose to add a flag "unique" to perms(), which would then have the behaviour you propose -- at the moment, neither octave nor Matlab for that matter recognize flags to perms(), so that should be no problem. And I can even imagine that, if octave should introduce that, Matlab would follow, because: in the strict mathematical sense, a permutation is not a reordering of a specific (multi-)set, but a specific mapping of positions -- that is, it is not yet applied. Thus, an example of a permutation of order 3 would be "swap the second and third element and leave the first fixed", written as (1)(32). Only if you write perms(1:n) for a given n you really get permutations in the mathematical sense. 

What octave actually computes are multiset permutations applied to a specific multiset, but without dropping equivalent multiset permutations. I agree that offhand I do not see a situation where I would want those. What you propose are multiset permutations in the strict sense. Note that this is also what Wolfram alpha (and thus presumably Mathematica compute): if you enter Permutations[{1, 2, 2}], you get a three-, not six-element list of permutations. So I agree that your contribution is helpful.

As to the performance: I think that you can get close to the performance of perms (that means, in practical time you can generate permutations that fill memory) if you do the following: first, compute only the multiset permutations, not the application to a specific multiset. Thus, compute indices, and you have to use here only uint8 (saving memory), because you will never have more than 256 distinct elements in the multiset (because of memory). Then, do it iteratively: say that n(i) is the frequency that element i (sorted) appears in the multiset. You first compute the multiset permutations of the sub-multiset consisting only of this first element. This is of course ones(n(1),1). Then you iteratively compute the multiset permutations of the sub-multiset consisting of the first i unique elements from those consisting of the first i-1. You can do so by index arithmetics and cumsum(nchoosek(1:1+sum(n(1:i-1)),n(i)),2), which gives you the positions where you expand the input multiset permutation and put entry i. And of course you do that by a single assignment on the matrix of permutation vectors. This should need only a single for loop (over the unique entries in your input multiset), and in addition the for loop in nchoosek(). I think that this should be performant. And at the end of course you use your multiset permutation as input into the unique values of your input multiset.


Michael Leitner <mleitner>
Sat 10 Apr 2021 01:20:25 AM UTC, original submission:  

Calling

unique (perms (foo), "rows")

takes at least as much memory as N! and likely more when doing the sorting and unique operation. This is inconvenient for long vectors with many repeated elements where the small final result is prevented by the calculation of a large intermediate.

Here is a proposed function uniqueperms() to address that behavior. Feedback requested please.

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #53327:  perms_edited.m added by arungiridhar (7KiB - text/x-objcsrc)
file #53323:  perms_m.m added by mleitner (7KiB - text/x-matlab)
file #53258:  perms_m.m added by mleitner (7KiB - text/x-matlab)
file #53253:  perms.patch added by arungiridhar (5KiB - text/x-patch)
file #51222:  uniqueperms.m added by None (3KiB - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by arungiridhar (Updated the item)
  • -email is unavailable- added by mleitner (Posted a comment)
  •  

    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 14 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-07-05 rik5 StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2022-06-20 arungiridhar StatusFixed Ready For Test
        Open/ClosedClosed Open
    2022-06-20 arungiridhar Attached File- Added perms_edited.m, #53327
    2022-06-20 mleitner Attached File- Added perms_m.m, #53323
    2022-05-29 mleitner Attached File- Added perms_m.m, #53258
    2022-05-29 rik5 StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2022-05-25 arungiridhar StatusPatch Submitted Ready For Test
    2022-05-25 arungiridhar Attached File- Added perms.patch, #53253
        StatusNone Patch Submitted
        SummaryTakes too much memory to call unique(perms(...)), so here's a new function uniqueperms New option "unique" for perms
    2021-04-10 None Attached File- Added uniqueperms.m, #51222

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code