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

[Rik]

Update of bug #53012 (project octave):

                  Status:                    None => Confirmed              
                 Release:                   4.2.1 => dev                    

    _______________________________________________________

Follow-up Comment #1:

Confirmed.  This is a pretty classic time/space trade-off.  The current
solution uses 2N blocks of memory ([1] original array, [2] returned sorted
array), but requires on order N log2(N) calculations of abs and a variable
number of angle calculations.  Using something like sortrows would require 4N
blocks of memory ([1] original array, [2] abs (array), [3] angle (array)], [4]
sorted index array) but a guaranteed number of N calculations of abs and
angle.

An additional possibility is to consider a threshold where smaller arrays use
sortrows and larger arrays use the traditional sort routine.  Note that the
threshold could be quite high.  One million complex double values is 16 MB so
the sortrows solution would require 64 MB.  Most PCs have RAM measured in GB
so this wouldn't necessarily be an issue.

I'm attaching an updated test script.


N = 3e6;

r = complex (rand (N,1), rand (N,1));

## Use sortrows, N calculations of abs and angle, but 4*N memory requirements
tic;
[~,j] = sortrows ([abs(r), angle(r)]);
rs1=r(j);
bm1 = toc

## sort, N*log2(N) calculations of abs and possibly angle, 2*N memory
tic;
rs2=sort(r);
bm2 = toc

isequal(rs1,rs2)


which shows sortrows is ~3X faster.


bm1 =  1.1423
bm2 =  3.0540
ans = 1




(file #43111)
    _______________________________________________________

Additional Item Attachment:

File name: bm_complex_sort.m              Size:0 KB


    _______________________________________________________

Reply to this item at:

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

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