bugGNU Octave - Bugs: bug #54144, Why can't issorted() work on...

 
 

bug #54144: Why can't issorted() work on sparse matrices?

Submitter:  Dan Sebald <sebald>
Submitted:  Mon 18 Jun 2018 07:49:25 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Feature Request
Status:  Confirmed Assigned to:  None
Originator Name:  Open/Closed:  * Open
Release:  * dev Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Tue 19 Jun 2018 01:33:14 AM UTC, comment #2: 

One thing that appears to be missing is support in liboctave/array/Sparse.h for issorted.  Only Array.h and Range.h have the issorted routine.  It could be that issorted has not been implemented for sparse matrices in liboctave.  sort() for Sparse matrices is declared in Sparse.h and this is valid


sort (sparse (magic (5)))



Rik <rik5>
Group administrator
Mon 18 Jun 2018 11:04:47 PM UTC, comment #1: 

Actually, sorting on sparse matrices might work, while bug #54143 is covering up this fact:


octave:15> X = sparse ([1 1], [3 4], [4 3], 1, 8)
X =

Compressed Column Sparse (rows = 1, cols = 8, nnz = 2 [25%])

  (1, 3) ->  4
  (1, 4) ->  3

octave:16> full(X)
ans =

   0   0   4   3   0   0   0   0

octave:17> sort(X)
ans =

Compressed Column Sparse (rows = 1, cols = 8, nnz = 2 [25%])

  (1, 7) ->  3
  (1, 8) ->  4

octave:18> full(sort(X))
ans =

   0   0   0   0   0   0   3   4

octave:21> issorted(X)
ans = 0
octave:22> issorted(sort(X))
ans = 1


If that is the case, then the attached changeset is all that is needed.

There is another use of the phrase "support sparse" in this file:


diff --git a/libinterp/corefcn/data.cc b/libinterp/corefcn/data.cc
--- a/libinterp/corefcn/data.cc
+++ b/libinterp/corefcn/data.cc
@@ -6702,8 +6702,6 @@ ordered lists.
 // Sort the rows of the matrix @var{a} according to the order
 // specified by @var{mode}, which can either be 'ascend' or 'descend'
 // and return the index vector corresponding to the sort order.
-//
-// This function does not yet support sparse matrices.

 // FIXME: Is this function used anymore?  12/14/2015
 DEFUN (__sort_rows_idx__, args, ,


I was going to remove that, but in this case that statement still holds.  Furthermore, there is a FIXME question about whether this routine is even used anymore, so maybe investigating and removing that routine is the better route.  It appears that the script file sortrows() uses the above routine, and for the sparse case it implements a row-by-row sort via a script sort_rows_idx_generic().  Apparently, the sorting method of the sort_rows_idx_generic() accepts sparse matrices.  For sparse matrices, the generic script-based sort probably doesn't have the cost that full matrices do.  I wonder if the better solution here is to move what is in sortrows.m into the built-in routine _sort_rows_idx_ and call that routine "sortrows".

(file #44394)

Dan Sebald <sebald>
Mon 18 Jun 2018 07:49:25 PM UTC, original submission:  

The issorted() documentation states


     This function does not support sparse matrices.


yet sort() works on sparse matrices:


octave:10> I = [1 1 2]; J = [1 1 2]; SV = [3 4 5];
octave:11> X = sparse (I, J, SV, 3, 4, "unique")
X =

Compressed Column Sparse (rows = 3, cols = 4, nnz = 2 [17%])

  (1, 1) ->  4
  (2, 2) ->  5

octave:12> sort(X)
ans =

Compressed Column Sparse (rows = 3, cols = 4, nnz = 2 [17%])

  (3, 1) ->  4
  (3, 2) ->  5

octave:13> issorted(sort(X))
error: issorted: needs a vector


As with the previous bug report, issorted() should be able to work on anything that the sort() routine produces.

Dan Sebald <sebald>

 

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

Attach Files:
   
   
Comment:
   

Attached Files

 

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 sebald (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 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-06-19 rik5 StatusNone Confirmed
    2018-06-18 sebald Attached File- Added octave-issorted_doc-djs2018jun18.patch, #44394

    Back to the top

    Powered by Savane 3.14-3b9d.
    Corresponding source code