RE: benchmarks - sort

[THOMAS Paul Richard]

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