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

[Michael Leitner]

Follow-up Comment #2, bug #53012 (project octave):

It's not quite that bad. Remember that this path would only be taken when the
input r is complex, and that abs(r) and arg(r) both are real. Thus, when you
sort a vector of N complex doubles, you have an input of 16* N byte and
generate an output of 16* N byte in the current implementation. Going via
sortrows, you generate in addition to the input 16* N temporary bytes, pass it
to sortrows, which gives you back an index vector of 8* N bytes. At this point
you can clear the temporary [abs(r) arg(r)] and generate the final output of
16* N bytes. So the peak memory consumption relates as 5/4, which is not so
critical, I would say (in fact probably even less, because sort uses
additional state internally, and I would guess this to be of the same
magnitude in both algorithms). 

When you request both sorted array and permutation indices, the memory
consumption is exactly equal, and when you only request the permutation
indices, it will probably be the same (because I would guess that the
traditional sort needs at least the same internal storage as the size of the
input, even when it only needs to compute the indices). 

Have you tested your quoted values of memory requirements, and have I
overlooked something?

    _______________________________________________________

Reply to this item at:

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

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