octave-maintainers
[Top][All Lists]

## RE: benchmarks - sort

 From: THOMAS Paul Richard Subject: RE: benchmarks - sort Date: Thu, 22 Jan 2004 10:32:15 -0600

```Dear All,

This is the last that I will write on the subject; honest!

It seems to me that the peformance gains that David has obtained make it
worth incorporating his sort routine into octave rather than octave-forge.
I use sort a lot on large datasets and, as the monkey said, every little bit
helps.

I think that I have taken the standard library sorting routine as far as it
will go in the enclosed.  It sorts a vector of double pointers, using
stable_sort and an appropriate less than operator.  It runs ~1.4 times
faster than octave's sort and my multimap implementation
(this is consistent between 10^6 random elements, ordered descending,
ordered descending with 3 random exchanges).  It is still a consistent
factor 3 slower than Matlab's sort and, obviously, performs nowhere near as
well as David's product.  Nonetheless, I thought that it would be of
academic interest, at least.

Paul Thomas

//Test of stable_sort of standard library with user supplied operator.
//In input vector x is written to a double array vinptr.
//An array of double pointers is formed, vidx, pointing to the elements.
//of vinptr.  This array of pointers is then sorted, using stable_sort
//(retains order of equal value elements).  The column vector of sorted
//values a is obtained from the sorted pointer array and the sorted
//index vector is the pointer array, offset by the first address.
//
//Paul Thomas                                              22/01/04

#include <octave/oct.h>
#include <octave/variables.h>
#include <map>
using namespace std;

bool dptrlt(double *p1, double *p2)             //comparison operator for
sort
{
return *p1<*p2;                              //*double less than
}

DEFUN_DLD (mysort2, args, ,
"mysort2. Call using \
[a,b]=mysort2(x)")
{
ColumnVector vin(args(0).vector_value());    //turn input into
ColumnVector
int vinlen=vin.length();                     //length of data
double *vinptr=vin.fortran_vec();            //pointer to double data in
vin
double *vidx[vinlen];                        //array of pointers to sort

for (int ic=0;ic<vinlen;ic++)
{
vidx[ic]=vinptr+ic;                       //create array of pointers
}

stable_sort(vidx,vidx+vinlen,dptrlt);        //sort using double ptr <

ColumnVector idxout(vinlen);                 //output index array
ColumnVector vout(vinlen);                   //output sorted data
int tmp;
for (int ic=0;ic<vinlen;ic++)
{
tmp=vidx[ic]-vinptr;                      //index is pointer-offset
idxout(ic)=tmp+1;                         //octave_value index
vout(ic)=vin(tmp);                        //octave_value sorted data
}
octave_value_list retval(vout);              //sorted value to output
retval.append(octave_value(idxout));         //sorted index to output
return retval;                               //return
}

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.564 / Virus Database: 356 - Release Date: 19/01/04

```

reply via email to