bugGNU Octave - Bugs: bug #65176, unique.m - Enable third output...

 
 

bug #65176: unique.m - Enable third output with option 'stable'

Submitter:  Robert Jenssen <morgawr>
Submitted:  Wed 17 Jan 2024 01:13:59 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Feature Request
Status:  Ready For Test Assigned to:  None
Originator Name:  Robert Jenssen Open/Closed:  * Open
Release:  * 8.4.0 Operating System:  * Any
Fixed Release:  None Planned Release:  10.1.0 (current default)
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sat 24 Feb 2024 11:57:17 PM UTC, comment #16: 

pushed cleaned up patch to default branch as
https://hg.savannah.gnu.org/hgweb/octave/rev/49dec190c4da

I left in the commented example with various indices detailed, as it does get a little obscure figuring out what something like p(i) = p(j(k(l))) means.

thanks for getting this up and running. marking as ready for test. this should be part of Octave 10.

Nicholas Jankowski <nrjank>
Group Member
Sat 24 Feb 2024 02:12:37 PM UTC, comment #15: 

Figured it out. Just had to do the same kind of index position assignment done with k. About 50% faster than the 2d expansion. Will post and push later today.

Anonymous
Fri 23 Feb 2024 07:22:56 PM UTC, comment #14: 

new patch removes all calls to sort after the initial one for y. reordered 2nd and 3rd output calculations to utilize i output to simplify calculating j without redundancy. This still has the find(u(s) == l(j)') 2d expansion which i have noted with a FIXME does cause a memory usage increase (largest internal variable goes from n to m x n where m is the number of unique elements in x) which could be an issue for large data sets, in addition to using the two-output form of find which imposes a ~10-25% slowdown on larger data.

But, this seems to be at a pretty good state.  I'll maybe take a bit more time to see if there's a better final replacement to that 2d expansion, otherwise I'll push it to default for test.

(file #55736)

Nicholas Jankowski <nrjank>
Group Member
Thu 22 Feb 2024 12:35:16 AM UTC, comment #13: 

ok. figured out how to avoid the sort for k. I realized k is just a mapping of sorted x, or x(i) back to x, such that x(i)(k) = x.  that can be gotten from k and i with:


k = i #cheap way to initialize k to the right size
k(i) = 1:n;

 I'm pretty sure there's something similar that can be done to remove the need to sort for s, but don't have that yet.

Nicholas Jankowski <nrjank>
Group Member
Wed 21 Feb 2024 11:18:40 AM UTC, comment #12: 

Try to make the example in the comments clearer.

(file #55730)

Robert Jenssen <morgawr>
Wed 21 Feb 2024 08:28:32 AM UTC, comment #11: 

Excellent! That works and it is now just five lines. Thanks but put your name on the patch.

(file #55729)

Robert Jenssen <morgawr>
Wed 21 Feb 2024 06:15:09 AM UTC, comment #10: 

just remembered find has a 2 output argument version that will give the row for find (u(s) == l(j).'), which is what the next two lines were accomplishing. Will try that later.  Something like



[~, j] = sort (i);
[j,~] = find (u(s) == l(j).'));


And we haven't set any high bars for being lists as a contributor. But that's fine. Would you also prefer not to be named as the patch author on the commit message?

Nicholas Jankowski <nrjank>
Group Member
Wed 21 Feb 2024 12:57:50 AM UTC, comment #9: 

Thanks for cleaning it up. Much better without for-loops. I'd suggest removing the commented for-loop for l but adding a comment to the code for j that refers to the example. See attachment.

This needs to reverse three mappings:
  input->sorted->unique->stable
It was always going to be a bit obscure.

Immediately after I hit "Submit" I realised that I hadn't fixed the white space completely. Oops.

Thanks for the offer, but I don't think this is sufficient to be called a "contributor" so I'd prefer to remain a lurker.

(file #55728)

Robert Jenssen <morgawr>
Tue 20 Feb 2024 11:04:16 PM UTC, comment #8: 

(typo in the comparison code, the second set did use "a = randi(...")

Nicholas Jankowski <nrjank>
Group Member
Tue 20 Feb 2024 11:03:19 PM UTC, comment #7: 

no problem with the timing. you've seen how long some bugs sit :)

i did a look through the patch. it seems to work fairly well. A few issues - octave tends to perform poorly with for loops.  It's not that noticeable with small inputs, but for larger arrays/loops it can get significant.

I attached a revised patch where I was able to replace your loops with some vectorized equivalents.  Still passes all the tests. 
see a quite timing comparison on the two:


## small input borrowed from a BIST, not too much different
A = [4,5,6; 1,2,3; 4,5,6];

#loops
tic; for idx = 1:10000, [y,i,j] = unique(A,"rows","stable");endfor,toc
Elapsed time is 1.78322 seconds.

#vectorized
tic; for idx = 1:10000, [y,i,j] = unique(A,"rows","stable");endfor,toc
Elapsed time is 1.59985 seconds.

## bigger array
A = randi([1 10], 1000, 3);

#loops
> tic; for idx = 1:100, [y,i,j] = unique(a,"rows","stable");endfor,toc
Elapsed time is 1.523 seconds.

#vectorized
tic; for idx = 1:100, [y,i,j] = unique(a,"rows","stable");endfor,toc
Elapsed time is 0.121731 seconds.


I also cleaned up some of the formatting (mostly whitespace around functions and operators - see the style guide link below.), separated two added tests and added a <bug#> tag to them so the test suite can trace them back if a regression ever occurs.


I'm still wondering if that could get streamlined a bit more.  There are a few calls to sort that I think might be redundant with the multi-level mapping, and my find(u(s)==j') to project into dim2 followed by cleanup math is a bit of a hack that might not be necessary with the right mapping.   I left the old code in as comments for now as a reminder, but they should get trimmed before being finished. let me know what you think.

also, assuming we push this for octave 10 in the near future, would you like to be in the contributor list (assuming your name as shown here and with email from your savannah profile?)

(file #55727)

Nicholas Jankowski <nrjank>
Group Member
Tue 20 Feb 2024 02:30:58 AM UTC, comment #6: 

See attached patch.

(file #55720)

Robert Jenssen <morgawr>
Sun 18 Feb 2024 03:31:45 PM UTC, comment #5: 

Apologies for the slow response. Your examples with arrays are easy to fix with numel() instead of length(). I am looking at "rows".

Robert Jenssen <morgawr>
Wed 17 Jan 2024 04:00:32 PM UTC, comment #4: 

ok, thanks again for the contribution. Had a chance to test it out and compare with matlab output.  it seems to work perfectly for vector inputs, but has issues with array inputs and generates errors when the 'rows' option is used. 

Also, please have a look at the style guideline for m-files (whitespace being the only real item of note)
https://wiki.octave.org/Octave_style_guide

Here are a few tests that can be added to the file that the patch should try to address:


%!test <65176>
%! a = [3 2 1 2; 2 1 2 1];
%! [o1, o2, o3] = unique (a);
%! assert ({o1, o2, o3}, {[1;2;3], [4;2;1], [3;2;2;1;1;2;2;1]});
%! [o1, o2, o3] = unique (a, "stable");
%! assert ({o1, o2, o3}, {[3;2;1], [1;2;4], [1;2;2;3;3;2;2;3]});

%!test <65176>
%! a = [3 2 1 2; 2 1 2 1];
%! [o1, o2, o3] = unique (a(1,:), "rows");
%! assert ({o1, o2, o3}, {a(1,:), 1, 1});
%! [o1, o2, o3] = unique (a(1,:), "rows", "stable");
%! assert ({o1, o2, o3}, {a(1,:), 1, 1});
%! [o1, o2, o3] = unique (a, "rows");
%! assert ({o1, o2, o3}, {[a(2,:); a(1,:)], [2;1], [2;1]});
%! [o1, o2, o3] = unique (a, "rows", "stable");
%! assert ({o1, o2, o3}, {a, [1;2], [1;2]});
%! [o1, o2, o3] = unique ([a;a], "rows");
%! assert ({o1, o2, o3}, {[a(2,:); a(1,:)], [2;1], [2;1;2;1]});
%! [o1, o2, o3] = unique ([a;a], "rows", "stable");
%! assert ({o1, o2, o3}, {a, [1;2], [1;2;1;2]});


Also, a complete patch should include a note in the /etc/NEWS.10.md file, probably under the matlab compatibility section, and a commit message according to https://wiki.octave.org/Commit_message_guidelines

I've updated the status to In Progress, let us know if this is something you'll have a chance to help address.

Nicholas Jankowski <nrjank>
Group Member
Wed 17 Jan 2024 02:54:40 PM UTC, comment #3: 

ok, thanks for the explanation. updating the bug details. will give it a look.

Nicholas Jankowski <nrjank>
Group Member
Wed 17 Jan 2024 01:55:24 PM UTC, comment #2: 

Manual tells

"""
The third output, j, has not been implemented yet when the sort order is "stable".
"""

Robert patch fix that.

Anonymous
Wed 17 Jan 2024 01:19:02 PM UTC, comment #1: 

It was my understanding that the current version of unique did have an option for up to three outputs.  Can you explain more about what yours does differently?

See https://docs.octave.org/latest/Sets.html

Nicholas Jankowski <nrjank>
Group Member
Wed 17 Jan 2024 01:13:59 PM UTC, original submission:  

The attached patch adds a third output argument to unique.m

Robert Jenssen <morgawr>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #55740:  unique_stable_bug65176_v9.diff added by nrjank (8KiB - application/octet-stream)
file #55736:  unique_stable_bug65176_v8.patch added by nrjank (8KiB - application/octet-stream)
file #55730:  unique_stable_bug65176_v6.patch added by morgawr (6KiB - text/x-patch - Improve the comments)
file #55729:  unique_stable_bug65176_v5.patch added by morgawr (6KiB - text/x-patch - Add nrjank's improvement)
file #55728:  unique_stable_bug65176_v4.patch added by morgawr (6KiB - text/x-patch - Minor edit of for loop comments)
file #55727:  unique_stable_bug65176_v3.patch added by nrjank (7KiB - application/octet-stream - vectorized code with draft commit message)
file #55720:  unique.m.patch added by morgawr (6KiB - text/x-patch - Patch to add third output argument to unique.m for stable sorted output)
file #55582:  unique.m.patch added by morgawr (2KiB - text/x-patch - This patch adds a third output argument to unique. m)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jwe (Updated the item)
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by morgawr (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 17 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2024-02-24 nrjank StatusPatch Submitted Ready For Test
    2024-02-23 nrjank StatusIn Progress Patch Submitted
    2024-02-23 nrjank Attached File- Added unique_stable_bug65176_v9.diff, #55740
    2024-02-23 nrjank Attached File- Added unique_stable_bug65176_v8.patch, #55736
    2024-02-21 morgawr Attached File- Added unique_stable_bug65176_v6.patch, #55730
    2024-02-21 morgawr Attached File- Added unique_stable_bug65176_v5.patch, #55729
    2024-02-21 morgawr Attached File- Added unique_stable_bug65176_v4.patch, #55728
    2024-02-20 nrjank Attached File- Added unique_stable_bug65176_v3.patch, #55727
    2024-02-20 morgawr Attached File- Added unique.m.patch, #55720
    2024-01-17 nrjank StatusPatch Submitted In Progress
    2024-01-17 jwe Item GroupMatlab Compatibility Feature Request
    2024-01-17 nrjank StatusNeed Info Patch Submitted
        Operating SystemGNU/Linux Any
        Planned ReleaseNone 10.1.0 (current default)
        SummaryAdd third output to unique.m unique.m - Enable third output with option 'stable'
    2024-01-17 nrjank StatusNone Need Info
    2024-01-17 morgawr Attached File- Added unique.m.patch, #55582

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code