[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Octave-bug-tracker] [bug #53012] Performance of sort on complex values
From: |
Michael Leitner |
Subject: |
[Octave-bug-tracker] [bug #53012] Performance of sort on complex values |
Date: |
Tue, 30 Jan 2018 05:24:12 -0500 (EST) |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0 |
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/
- [Octave-bug-tracker] [bug #53012] Performance of sort on complex values,
Michael Leitner <=