bugGNU Octave - Bugs: bug #45497, missing function: repelem

 
 

bug #45497: missing function: repelem

Submitter:  Nicholas Jankowski <nrjank>
Submitted:  Wed 08 Jul 2015 03:33:00 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Feature Request
Status:  Fixed Assigned to:  None
Originator Name:  Nick Jankowski 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

Fri 11 Aug 2017 05:27:24 PM UTC, comment #29: 

I pushed the changeset here:

http://hg.savannah.gnu.org/hgweb/octave/rev/c3043aaad700

Thanks to everyone who contributed.  Sorry for the long delay in adding this to Octave.

John W. Eaton <jwe>
Group administrator
Tue 31 Jan 2017 01:46:17 PM UTC, comment #28: 

Octave had repelems before Matlab had repelem. Then Matlab included a syntax incompatible repelem in 2014 or 2015. I don't recall the exact difference but my best understanding was that repelemms was limited to vectors while repelem was generalized to do run length decoding for n-dimensional arrays. At least that's what I needed it for when I found it was missing.  I believe the new repelem can do what repelems does, but not vice versa.

Nicholas Jankowski <nrjank>
Group Member
Tue 31 Jan 2017 12:21:22 PM UTC, comment #27: 

Nicholas, I don't see repelem in dev, but there is repelems.  What's the difference?  Does Matlab have both?  If not, which does it have?

John W. Eaton <jwe>
Group administrator
Wed 25 Jan 2017 06:58:25 PM UTC, comment #26: 

I have checked the patch. It didn't work cleanly because NEWS file
has been change.

It passes all (57) tests. I checked also some corner cases,
and it worked fine.
Changing status to "Patch reviewed".

Maintainers: I recommend to push this patch.

Avinoam Kalma <avinoam>
Group Member
Fri 16 Dec 2016 06:15:07 PM UTC, comment #25: 

i see repelem didn't make 4.2.0 but is now pushed to the dev branch. at this point is there anything else to do, can the bug be closed or is the convention to leave the bug open until it gets to pushed to a release?

Nicholas Jankowski <nrjank>
Group Member
Mon 29 Aug 2016 06:52:44 PM UTC, comment #24: 

This bug good to go for 4.2? the tests you added in #23 cover everything I can think of for now.

Nicholas Jankowski <nrjank>
Group Member
Sun 17 Jul 2016 03:56:24 AM UTC, comment #23: 

yes, Matlab 2016a output gives the answers in the tests you added, and the Octave repelem passes those tests.

Also, I did notice that repmat is called a couple times in some of the tests to specify the desired result.  That feels a tiny bit circular.

Nicholas Jankowski <nrjank>
Group Member
Mon 04 Jul 2016 10:12:16 AM UTC, comment #22: 

Good point, Nicholas.  The version of Matlab I have doesn't have repelem, so I can't check the tests.

I've added some possible tests to the changeset.  I didn't check whether Octave passes them yet -- first let's see if they are the answers that Matlab gives.  Are you able to check that?

(file #37701)

Lachlan Andrew <lachlan>
Fri 01 Jul 2016 04:56:19 PM UTC, comment #21: 

I saw Bug 46385 was proposing to use this function as a fix for repmap with struct arrays.  I realized I didn't add any tests for things other than numeric arrays. I guess we should add some tests for structs and cells and verify matlab compatibility.


https://savannah.gnu.org/bugs/?46385

Nicholas Jankowski <nrjank>
Group Member
Wed 29 Jun 2016 09:38:16 AM UTC, comment #20: 

I've tidied the patch a little, to make it conform to Octave coding standards, and rephrased the documentation.

For future reference, many of the changes were as follows:

An entire-line commnt is introduced by ##, not #
! instead of ~
' instead of "
; at the end of "assert" and "error" lines.  Parsing the file with "warning on Octave:missing-semicolon"  should give no warnings.
Lines shouldn't be longer than 76 characters
error() throws an exception, so code after it won't be reached -- I removed the "print_usage" statements.

(file #37619)

Lachlan Andrew <lachlan>
Sun 13 Dec 2015 09:50:35 PM UTC, comment #19: 

another revision. removed the function class type from the docstrings following the Octave Code Sprint activity.

(file #35734)

Nicholas Jankowski <nrjank>
Group Member
Sat 12 Dec 2015 08:09:58 PM UTC, comment #18: 

revised patch attached with print_usage() and coding style improvements.

(file #35717)

Nicholas Jankowski <nrjank>
Group Member
Sat 28 Nov 2015 04:23:34 AM UTC, comment #17: 

Patch attached including all the suggestions made in comment #14.



(file #35583)

Nicholas Jankowski <nrjank>
Group Member
Tue 24 Nov 2015 05:12:03 PM UTC, comment #16: 

Leave the deprecation of repelems as a separate issue. It is of course connected to this one, but there's no point worrying about it just yet. Once we have repelem implemented, commited and ready for 4.2, we can see about what to do with repelems.

Carnë Draug <carandraug>
Group Member
Tue 24 Nov 2015 04:07:58 PM UTC, comment #15: 

ok, thanks for the detailed info. will get working on that. 

Also, as Carne mentioned in Comment #6, would there be any immediate need to decide on deprecating repelems? Should that be part of this effort as well or left for a future decision?

https://savannah.gnu.org/bugs/?45497#comment6

Nicholas Jankowski <nrjank>
Group Member
Tue 24 Nov 2015 03:51:39 PM UTC, comment #14: 

You can either post the m-file, as you've already done, or provide a patch against the development sources adding the file.

I would recommend the scripts/general directory, simply because that's where repmat.m lives. You would also want to add the name of the m-file to scripts/general/module.mk. And for bonus points, include it in the NEWS file, as well as the user manual by adding "@DOCSTRING(repelem)" to one of the doc/interpreter/*.txi files (maybe matrix.txi, again because that is where repelems and repmat are mentioned).

Mike Miller <mtmiller>
Group Member
Thu 29 Oct 2015 05:30:55 PM UTC, comment #13: 

Revisiting this after the summer. Markus had gone through and I believe brought the code up into compliance with the general coding guidelines.  As this is a standalone, new m-file rather than a replacement/bugfix, is the normal routine to prepare a patch? that would require knowing where in the filetree the new file should reside, which I currently don't. Feel free to prod me to the next step...

latest attached file is still most recent version

Nicholas Jankowski <nrjank>
Group Member
Sun 26 Jul 2015 11:17:34 PM UTC, comment #12: 

mild changes as per suggestions on IRC. numel instead of length, and a typo on an isvector error-check.  revision attached, or latest from github:
https://github.com/repelem/repelem/blob/master/repelem.m

(file #34531)

Nicholas Jankowski <nrjank>
Group Member
Tue 21 Jul 2015 03:42:43 PM UTC, comment #11: 

ok... we have what we think is a complete implementation.  repelem.m is now attached to this report. Help text added, passes output & error tests which I believe hit all of the likely possibilities. Haven't found any inconsistencies with ML 2015a.



(file #34481)

Nicholas Jankowski <nrjank>
Group Member
Sat 11 Jul 2015 05:12:17 PM UTC, comment #10: 

With "creepy" I mean, maybe one of you can improve/simplify it. I guess my thoughts were to complicated.

Markus Bergholz <markuman>
Sat 11 Jul 2015 04:58:17 PM UTC, comment #9: 

We made it (on github). https://github.com/repelem/repelem/blob/master/repelem.m

There is a easy part (nargin == 2), and a creepy part (nargin > 2).

I've tested various combinations I can think of at the end of the file.

(file #34425)

Markus Bergholz <markuman>
Thu 09 Jul 2015 04:55:08 PM UTC, comment #8: 
  • I've merged the changes from Nick into my function
  • add support for nargin > 2


http://fossil.osuv.de/MissingFunctions/index.fs/artifact/da40fc176deec3f9

This repelem() is still missing support for column/row repeats for nxn arrays.


>> repelem ([1 2; 0 -1],[1 2], 3)

ans =

     1     1     1     2     2     2
     0     0     0    -1    -1    -1
     0     0     0    -1    -1    -1



I've take a look at repelems too. It only supports 2 inputs, while the seconds one has to be a 2xn matrix.

Markus Bergholz <markuman>
Thu 09 Jul 2015 04:05:42 PM UTC, comment #7: 

regarding the second bit of code from comment 2:

As that is someone else's code, and not GPL'd, is there a preferred method/language to use if I request the author grant permission for us to include his algorithm under GPL?

The m-file sample on his website does say:
"This is a collection of m-files that I have made and found useful. Since there is no need to re-invent the wheel, please feel free to download them and use them as much as you like."

and the m-file contains an author notice but no other copyright statement.

at the front of the PDF describing the code it says
Copyright © 2000–2003 Peter J. Acklam. All rights reserved.
Any material in this document may be reproduced or duplicated for personal or educational use.


??

Nicholas Jankowski <nrjank>
Group Member
Thu 09 Jul 2015 09:16:30 AM UTC, comment #6: 

This is a duplicate of bug #44509 which asks to change repelems to match Matlab API.

The usual Octave plan for things such as this is discussion. Usually is to deprecate the non-compatible version to keep namespace clean. We don't need multiple functions that do the same with slightly differences interfaces.

Carnë Draug <carandraug>
Group Member
Thu 09 Jul 2015 06:15:53 AM UTC, comment #5: 

through the benefits of a fortunate typo,  I just realized that Octave has a function

repelems

with similar purpose to repelem.  But ML does not have a repelems function, and the syntax is quite different.

Assuming we tidy up a compatible repelem, what's the usual Octave plan for something like repelems? leave it? deprecate it?

Nicholas Jankowski <nrjank>
Group Member
Thu 09 Jul 2015 06:02:35 AM UTC, comment #4: 

yes, understand. I've played with it a bit this evening. attached a modified version.

I dropped in my non-repmat versions for scalar v, as they were nice one-line replacements. Also changed some of the length checking to 'isscalar' 'isrow' 'isvector', etc, for same performance reasons.

I noticed the multi-dimensional array part might throw some problems. Tested a bit on ML.  for a nD array (anything bigger than a row or column vector), number of input arguments must = n+1.  each one can either be a scalar or a vector specifying reps in that direction. seems to work for arbitrary n. 

currently a scalar v but array element gets past the first if-else set, so I added a catch there.

The else-if for the vector element and vector v would give true on an array with the first range having the same length() (say a 2x2 A with a 2x1 v), but would give a blank output. added an isvector() there to prevent that so it should pass to the next conditional for arrays.

1 or two other comments addded. will peek at it a bit more tomorrow.

(file #34400)

Nicholas Jankowski <nrjank>
Group Member
Thu 09 Jul 2015 04:41:01 AM UTC, comment #3: 

Well, make it work, make it fast. In this order ;)

Currently my repelem support the first 3 exampes of Matlab repelem documentation. The 4th example is missing.

You can try to improve performance and do  test repelem.

Markus Bergholz <markuman>
Wed 08 Jul 2015 09:09:38 PM UTC, comment #2: 

Looks good. A couple comments. I noticed you're using repmat even for the simpler cases. Just went through a run length decoding exercise and what I first found was discussion about using indexing tricks to avoid calling repmat, can make a big performance improvement.

E.g., the following two lines produce the same output:


>> v = 2;
>> element = [1 2 3 4 5 6];
>> repmat (element, 2, 1)(:)'
ans =

   1   1   2   2   3   3   4   4   5   5   6   6

>> element(ones(2,1),:)(:)'
ans =

   1   1   2   2   3   3   4   4   5   5   6   6


Additionally, doing a quick and (very) dirty timing test:

>> tic;for ii = 1:10000,repmat (element, v, 1)(:)';,endfor;toc

Elapsed time is 3.182 seconds.

>> tic;for ii = 1:10000,element(ones(v,1),:)(:)';,endfor;toc

Elapsed time is 0.207 seconds.
-verbatim-

For v being a vector, I came upon the following :

Matlab array manipulation tips and tricks
http://home.online.no/~pjacklam/matlab/doc/index.html

In chapter 15.5.2 it had a section on run length encoding & decoding with 3 different scripts. while the author says the 1st one should be the slowest, my timing of the three with octave (it was a touch more involved that the timing test above) showed it to be the fastest.  with your variable naming the code would be (haven't checked for accuracy with your code):

ii = cumsum(v);
jj = zeros(1, ii(end));
jj(ii(1:end-1)+1) = 1;
jj(1) = 1;
ret = element(cumsum(jj));


I've been toying with using the (ones()) indexing with multidimensional arrays, and it works well. If I get a chance I'll look at what you have and what repelem needs to cover.

Nicholas Jankowski <nrjank>
Group Member
Wed 08 Jul 2015 08:28:18 PM UTC, comment #1: 

I've got a draft of repelem for GNU Octave: http://fossil.osuv.de/MissingFunctions/index.fs/artifact/1ee5235fef5e7e97


Not everything is already implemented yet. But feel free to try and give a feedback what's working and what not.

Markus Bergholz <markuman>
Wed 08 Jul 2015 03:33:00 PM UTC, original submission:  

Just noticed ML 2015a implemented what appears to be a multidimensional 'run time decoding' function repelem. 

running repelem doesn't produce the warning:
"Please read `http://www.octave.org/missing.html' to learn how you can contribute missing functionality."

suggest it get added to whatever list sets that off.

Nicholas Jankowski <nrjank>
Group Member

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #37701:  bug_45497_repelem.v1.cset added by lachlan (18KiB - text/x-diff)
file #37619:  bug_45497_repelem.cset added by lachlan (17KiB - text/x-diff)
file #35734:  add_repelem_v3.diff added by nrjank (17KiB - application/octet-stream - even newer patch for implementing repelem.m, (comment 19))
file #35717:  add_repelem_v2.diff added by nrjank (17KiB - application/octet-stream - new patch file for implementing repelem.m)
file #35583:  add_repelem.diff added by nrjank (17KiB - application/octet-stream - Patch file for implementing repelem.m)
file #34531:  repelem.m added by nrjank (14KiB - application/octet-stream)
file #34481:  repelem.m added by nrjank (14KiB - application/octet-stream - "final" version of repelem.m)
file #34425:  repelem.m added by markuman (5KiB - text/x-objcsrc)
file #34400:  repelem.m added by nrjank (3KiB - text/x-objcsrc)

 

Depends on the following items: None found

Digest:
   bug dependencies.

 

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

    Date Changed by Updated Field Previous Value => Replaced by
    2017-08-11 jwe StatusPatch Reviewed Fixed
        Open/ClosedOpen Closed
    2017-01-25 avinoam StatusPatch Submitted Patch Reviewed
    2016-07-04 lachlan Attached File- Added bug_45497_repelem.v1.cset, #37701
    2016-06-29 lachlan Attached File- Added bug_45497_repelem.cset, #37619
        Release4.0.0 dev
        Operating SystemMicrosoft Windows Any
    2015-12-13 nrjank Attached File- Added add_repelem_v3.diff, #35734
    2015-12-12 nrjank Attached File- Added add_repelem_v2.diff, #35717
    2015-11-28 nrjank Attached File- Added add_repelem.diff, #35583
    2015-11-24 mtmiller StatusNone Patch Submitted
    2015-07-26 nrjank Attached File- Added repelem.m, #34531
    2015-07-21 nrjank Attached File- Added repelem.m, #34481
    2015-07-11 markuman Attached File- Added repelem.m, #34425
    2015-07-09 carandraug Dependencies- bugs #44509 is dependent
    2015-07-09 nrjank Attached File- Added repelem.m, #34400

    Back to the top

    Powered by Savane 3.13-758e.
    Corresponding source code