[Octave-bug-tracker] [bug #53012] Performance of sort on complex values

[Michael Leitner]

URL:
  <http://savannah.gnu.org/bugs/?53012>

                 Summary: Performance of sort on complex values
                 Project: GNU Octave
            Submitted by: mleitner
            Submitted on: Tue 30 Jan 2018 10:24:11 AM UTC
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Performance
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
         Discussion Lock: Any
                 Release: 4.2.1
        Operating System: Any

    _______________________________________________________

Details:

I am splitting up bug #52919. Now to the performance of sort on complex
values:

Sort is unnecessarily slow on complex values. Consider the following code:


N=1e7;
r=floor(randn(N,1)+1i*randn(N,1))+.5+.5*1i;
tic;[~,j]=sortrows([abs(r) angle(r)]);rs1=r(j);toc
tic;rs2=sort(r);toc
isequal(rs1,rs2)


On my computer, the first line takes 2.3 seconds, while the second line takes
8.0 seconds. The results are equal (apart from subtleties that could be
introduced as mentioned in bug #53011). Probably, this comparatively low
performance is due to sort having to compute two absolute values for each
comparison, of which there are about log(N)*N. Indeed, it seems that it does
not only compute the absolute value, but also the phase angle (?), because
defining 


r=randn(N,1)+1i*randn(N,1);


where all absolute values are different so that no angles would have to be
computed, does not help at all. In contrast, the sortrows-solution computes
only N absolute values and N angles. 

With a bit of m-code reshaping, this could be generalized to work also for
N-dimensional objects with sorting along a chosen dimension (and thus
automatically to an actual sortrows evaluated on complex inputs). Also,
Matlab's new option 'ComparisonMethod','real' could of course cheaply be
emulated by 


sortrows([real(r) imag(r)]);rs1=r(j);


As sort is a built-in function, it is beyond me to make these changes. It
would be probably easy to rename the built-in to __sort__ and pull the
checking for complex inputs (and the input validation) to an m-code wrapper,
but as sort is quite fundamental, it is perhaps worth the while to stay on the
C++ level. 

As I have argued elsewhere, I am not quite convinced that it is a good idea to
sort complex values (or even compare them) at all, because if I want to sort
on the absolute values, I would explicitly do so, but unique also uses sort
and would hence profit from an increased performance, and here it is obviously
meaningful to ask for the unique values of a complex vector. 




    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?53012>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/