bugGNU Octave - Bugs: bug #45739, sort 'descend' together with...

 
 

bug #45739: sort 'descend' together with vectors created with the colon operator

Submitter:  Dieter Schmidt <anstreo>
Submitted:  Wed 12 Aug 2015 11:38:11 AM UTC
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  anstreo Open/Closed:  * Closed
Release:  * 4.0.0 Operating System:  * Any
* Mandatory Fields

Add a New Comment (Rich Markup)
   

Comment Type & Canned Response:
       

 

( Jump to the original submission )

Thu 20 Aug 2015 03:24:26 PM UTC, comment #19: 

I think that the minimal changeset necessary to fix the problem is appropriate for the stable branch.  I made that change by altering the sort_internal function for Range objects in Range.cc.  See http://hg.savannah.gnu.org/hgweb/octave/rev/7e9c752138ec.  I also added tests for the correct behavior in range.tst (http://hg.savannah.gnu.org/hgweb/octave/rev/ba032e57fd96).  That is enough to close this bug report.

However, I still believe it would be useful to change the constructors on the development branch to guarantee that the maximum value in the range and the variable rng_limit are synonymous.  From the Octave command line, a range object is created by the colon syntax.  Thereafter, like any other good C++ object, I can only interact with it through other functions but the internal implementation is opaque.  I can query the object for the first [x(1)] or last element [x(end)] or manipulate it with standard arithmetic operators or sort it.  But I can't ask what the original limit used on the command line was.  So for x = 1:2:10 there is no possibility of determining that 10 was used rather than 9.  In C++ there is a way to do that, but I don't think it is a good idea because it breaks the data encapsulation paradigm of object oriented programming.

As an analogy, consider the creation of an unsigned 8-bit integer object.  On the command line I might use x = uint8 (1.5) which produces the uint8 object with a value of 2.  What should x - 0.25 return?  One possibility is that Octave has internal state and remembers the value that the object was invoked with.  In this case, 1.5 - 0.25 is 1.25 and for display purposes this would be shown as 1.  Or, as Octave indeed does, the constructor is a one-way function which takes inputs and creates an object without state.  Thus, uint8 (1.5) - 0.25 is equal to 2.

It will simplify the code if the range constructors are able to create a valid range and do all limit checking just once upon object creation rather than every time the rng_limit is reached.  Maybe this can be a side discussion at OctConf 2015.

Rik <rik5>
Project Administrator
Wed 19 Aug 2015 09:50:23 PM UTC, comment #18: 

I forgot to add that the Manual description of range
could, at least, be improved by adding the text in comment
#15.

Michael Godfrey <godfrey>
Project Member
Wed 19 Aug 2015 09:47:08 PM UTC, comment #17: 

After this discussion it appears that the second patch
(range2.cset) is a good choice, at least for now.
It avoids a potentially hard to track problem and does
not do anything else.

So, if this is submitted this and  #45758 could reasonably
be closed. Right?

Michael Godfrey <godfrey>
Project Member
Wed 19 Aug 2015 06:36:25 PM UTC, comment #16: 

If you choose to cache the limit of the range, then you will probably still want to store the original value in case Octave needs to display the original code.

I prefer the second changeset since it fixes the bug in sort but doesn't change the behavior that the Range::limit function (it still returns the value of the range limit as it was passed to the Range constructor).

John W. Eaton <jwe>
Project Administrator
Fri 14 Aug 2015 11:18:56 AM UTC, comment #15: 

Rik: Did you notice this in:
https://www.gnu.org/software/octave/doc/interpreter/Ranges.html

Note that the upper (or lower, if the increment is negative) bound on the range is not always included in the set of values, and that ranges defined by floating point values can produce surprising results because Octave uses floating point arithmetic to compute the values in the range. If it is important to include the endpoints of a range and the number of elements is known, you should use the linspace function instead (see Special Utility Matrices).

Michael Godfrey <godfrey>
Project Member
Fri 14 Aug 2015 08:55:44 AM UTC, comment #14: 

Lachlan: I did not mean that are never cases where applying
sort to a range would be appropriate. The fact that it took
this long for this bug to be noticed suggests that it tends
only to happen in exceptional cases. In any case it
should work correctly. Rik has written a patch
(two actually) which does this. And, range should
always, I think that everyone agrees, set the upper limit
as the last generated range value, not the last input.

Also, sort does return a range if the input is range.
But, fliplr does not. It does preserve the type in other
cases and I am quite sure that it will be agreed
that this is an error.

Please report any other anomalies in this area. Type range
seems not to be widely used, but it can be very effective.

Michael Godfrey <godfrey>
Project Member
Fri 14 Aug 2015 02:54:10 AM UTC, comment #13: 

Michael, you said that passing a range to sort() isn't sensible as the range is already sorted.  The issue is when a function passes its input variable to sort(), and that input happens to be a range.

I agree that fixing the constructor is the right approach.  If it has side effects, they are likely to be beneficial (i.e., fixing other bugs).

Out of interest, should  fliplr  return a range if the input is a range?  That should make it much faster, as Dieter points out.

Lachlan Andrew <lachlan>
Thu 13 Aug 2015 10:13:49 PM UTC, comment #12: 

May this is useful: the elapsed time with 1)'sort + range' is significat lower than 2) 'sort + matrix' or 3)'fliplr':
1)

>> clear all;tic();b=sort(1:3:1E8-1,'descend');toc()
Elapsed time is 4.70318e-008 seconds.

2)

>> clear all;tic();b=sort([1:3:1E8-1],'descend');toc()
Elapsed time is 0.296795 seconds.

3)

>> clear all;tic();b=fliplr(1:3:1E8-1);toc()
Elapsed time is 0.239199 seconds.

Dieter Schmidt <anstreo>
Thu 13 Aug 2015 08:03:58 PM UTC, comment #11: 

@Michael: sort () preserves the type of the input argument as you would expect.  For a range input, the output is also a range.

octave:2> x = 1:5
x =

   1   2   3   4   5

octave:3> typeinfo (x)
ans = range
octave:4> y = sort (x, 'descend')
y =

   5   4   3   2   1

octave:5> typeinfo (y)
ans = range

Rik <rik5>
Project Administrator
Thu 13 Aug 2015 07:18:57 PM UTC, comment #10: 

Rik: It appears to me that range1.cset is preferred. But,
you know a lot more about this. John's view will be
more important.

With this change, does it make sense that sort should
return a type range if its input is range? This seems
more logical, but are there problems with this?

I have looked at the documentation. It is not as explicit
as would be helpful. The text refers to "variables" where
only the default "double" works. The intxx's and complex do
not work. It would be nice if complex worked, but this can
be managed by using the real and imaginary parts.

Michael Godfrey <godfrey>
Project Member
Thu 13 Aug 2015 06:48:02 PM UTC, comment #9: 

I've added jwe to the CC list for the bug.  This seems important enough that it should be fixed on the stable branch.

I've made draft changesets of two different approaches.  In range1.cset I modified the Range constructors in Range.h.  Instead of storing a range limit which can never be reached, it stores the actual end of range as the range limit.  In the problem example of 1:2:10 it stores a range limit of 9 rather than 10.

The second approach in range2.cset modifies Range::sort_internal in Range.cc.  It takes the same approach in acquiring the true range limit and using it rather than the limit that was entered at the Octave prompt.

I've tested both with 'make check' and either one will work.  I would say that range1.cset which makes changes to the constructors might have a greater possibility of side effects.  But I also think there could be advantages to storing the true limit rather than the entered one.  There are simplifications that could be made in some of the other routines once it is guaranteed that the true limit and rng_limit are synonymous.  The simplifications would definitely go on the default branch.

The second approach is directly geared to solving the problem with sort().

(file #34637, file #34638)

Rik <rik5>
Project Administrator
Thu 13 Aug 2015 10:20:43 AM UTC, comment #8: 

I looked at liboctave/array/Range.cc. The implementation
has substantial subtleties so implementing the change of
the limit value will need some care and testing. It appears
that John is the original author so I will point out this
problem to him.

The alternative of having sort test for a type range argument
is still a possibility.

However, note that passing a range, which must have uniformly
increasing or decreasing increments, to sort is not something
that makes much sense. Sort will either return the original
input of fliplr of the input. Is there any construct such
that passing a type range to sort does something useful?

Michael Godfrey <godfrey>
Project Member
Wed 12 Aug 2015 03:39:07 PM UTC, comment #7: 

Rik,

Good point about fixing it in range.* This should not
have any negative side-effects. But, it also rasies
the question: if sort accepts range, should it return
a sorted range?

Anyhow, some documentation will be needed.

Michael Godfrey <godfrey>
Project Member
Wed 12 Aug 2015 03:26:58 PM UTC, comment #6: 

Ranges are a special Octave feature that are very space efficient.  However, they can be disabled so that a range is stored as a matrix of values just as Matlab does.  Try 'help disable_range' to see the documentation on the function.  For the time being, you might choose to add 'disable_range (true)' to your .octaverc file so that Octave always treats ranges as matrices.

The fix is likely to be in liboctave/array/Range.[h|cc].  Currently, when you create a range with something like 1:3:10, Octave stores the base (1), the limit (10), and the increment (3).  When you ask for the values of a range they are constructed on the fly from these three values.  It seems to me that the easiest thing to do would be to change the constructor for the Range class so the limit was always an actual value within the range itself.

Rik <rik5>
Project Administrator
Wed 12 Aug 2015 02:24:29 PM UTC, comment #5: 

Dieter: First, we are all "just users" so do not
worry about that.

Generally, Octave trys to be Matlab-compatible.
The exceptions are cases where an Octave feature
provides sufficient user benefits (that is for you) to
outweigh the value of compatibility.

In this case, as I said, the obvious choice is to modify
sort to convert a range variable to matrix, and thus
work as expected and provide Matlab compatibility.

Thanks for reporting this bug, and you are welcome to
submit a patch which fixes it. The sort function code
is in libinterp/corefcn/data.cc, so C skills are needed
to correct it.

Michael Godfrey <godfrey>
Project Member
Wed 12 Aug 2015 02:10:20 PM UTC, comment #4: 

@Michael Godfrey:  you are right with the difference between ranges/matrices and you are also right to write the range in []: 

>> sort([1:3:15],'descend')

ans =

   13   10    7    4    1

But the different handling of matrices/ranges by the sort-command is firstly not documented and secondly not very self-explanatory. Therefore something should be changed: doc or code.

I would prefer the solution with fixes in the sort-command, so there is no more difference between matrices and ranges (additionaly with the advantage of matlab-compatibility).

But I'm only a little old nobody ... erm ... user.

Dieter Schmidt <anstreo>
Wed 12 Aug 2015 01:16:43 PM UTC, comment #3: 

a = 1:2:10  is a range,

>> typeinfo(a)

ans = range

>> whos

Variables in the current scope:

   Attr Name        Size                     Bytes  Class
   ==== ====        ====                     =====  =====
        a           1x5                         24  double

It is not a matrix. So, it appears
that sort is converting the range in a way that is
counter intuitive.

Matlab treats a = 1:2:10 as the matrix
a =

     1     3     5     7     9

>> whos

  Name      Size            Bytes  Class     Attributes

  a         1x5                40  double

Matlab does not implement type range. 

So, one solution would  modify sort to convert range to
matrix (a = [a];).

About the priority this needs, I doubt if many users provide
range variables to sort. But, it should be fixed, especially
for matlab compatibility.  

      
Michael Godfrey <godfrey>
Project Member
Wed 12 Aug 2015 12:16:32 PM UTC, comment #2: 

I would mark this as a high priority bug as it can affect loads of important algorithms.

Juan Pablo Carbajal <juanpi>
Project Member
Wed 12 Aug 2015 12:14:56 PM UTC, comment #1: 

Verified in developer branch under Ubuntu as well.

The problem arises when the last element of the array is not part of the array. Example:

> a=1:2:9
a =

   1   3   5   7   9

> sort(a,'descend')
ans =

   9   7   5   3   1

> a=1:2:10
a =

    1    3    5    7    9

> sort(a,'descend')
ans =

   10    8    6    4    2

Juan Pablo Carbajal <juanpi>
Project Member
Wed 12 Aug 2015 11:38:11 AM UTC, original submission:  

--------------------------------------------------
GNU Octave Version: 4.0.0
GNU Octave License: GNU General Public License
Operating System: MINGW32_NT-6.2 Windows 6.2  i686
--------------------------------------------------

I've used for the first time the 'sort descend' mode together with a colon-operator created vector, e.g.

>> a=1:3:15;sort(a,'descend')

So the vector a includes the following values: 
[1    4    7   10   13]
and I would expect with 'sort descend' the following results:
[13   10    7    4    1]

but instead I receive
[15   12    9    6    3]

It seems to be that 'descend' changes the creation of vector 'a' in this way: a=15:-3:1. Should it really work like this? For my understanding of 'sort' the result is not correct because the function 'sort' should only sort the values that are given and should not change the way how the values will be created. How should I sort a=1:3:15 descendig?

If I'm wrong with my understanding of the sort function, then this special feature of 'sort descend' should be mentioned in the documentation at least.   

greetings

Dieter Schmidt <anstreo>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #34637:  range1.cset added by rik5 (1KiB - application/octet-stream)
file #34638:  range2.cset added by rik5 (964B - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by lachlan (Posted a comment)
  • -email is unavailable- added by rik5
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by godfrey (Posted a comment)
  • -email is unavailable- added by juanpi (Posted a comment)
  • -email is unavailable- added by anstreo (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 project members can vote.

     

     

     

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2015-08-20 rik5 StatusConfirmed Fixed
        Open/ClosedOpen Closed
    2015-08-13 rik5 Attached File- Added range1.cset, #34637
        Attached File- Added range2.cset, #34638
        StatusNone Confirmed
        Operating SystemMicrosoft Windows Any
    2015-08-13 rik5 Carbon-Copy- Added jwe

    Back to the top


    Powered by Savane 3.9