[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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
- Re: benchmarks - sort, (continued)
Re: benchmarks - sort, THOMAS Paul Richard, 2004/01/21
RE: benchmarks - sort,
THOMAS Paul Richard <=
Re: benchmarks - sort, Paul Thomas, 2004/01/22