Re: benchmarks - sort

[THOMAS Paul Richard]

For what it is worth ( 0.02 euros?), in the course of educating myself about
the C++ standard library, I did a test of the sorting capability of
multimaps.  It turns out to be a bit off the performance discussion, in that
the timing is EXACTLY the same as that of octave's sort and about a factor
of five slower than Matlab R13 on the same machine (not very surprising,
since the standard library uses exactly the same algorithm as octave!).
However, it is interesting just how concise a routine, exploiting the
standard library can become.  Please find the routine below.

Paul Thomas

 //Test of auto-sorting properties of standard library multi-map
//In input vector x is inserted element by element into a
//multi-map vmap, together with the input index of the element.
//Since multi-map insert sorts according to the value of the first
//element, reading the map pairs back, using the multi-map iterator,
//yields the sorted values and the sorted index.
//
//Paul Thomas                                   17/01/04  

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

DEFUN_DLD (mysort, args, ,
   "mysort. Call using \
   [a,b]=mysort(x)")
{
   typedef multimap<double,double> ddmap;       //<value,index>
   ColumnVector vin(args(0).vector_value());    //turn input into
ColumnVector
   int vinlen=vin.length();                     //number of input elements
   ddmap vmap;                                  //multimap container for x
and its index
   ddmap::iterator pos;                         //iterator for the multimap
   double didx=1;                               //double index
   for (int idx=0;idx<vinlen;idx++)             //let multimap insert sort
by value
   {
      vmap.insert(make_pair(vin(idx),didx++));  //insert value,index
   }
   int idx=0;                                   //output counter
   ColumnVector idxout(vinlen);                 //sorted index
   for (pos=vmap.begin();pos!=vmap.end();pos++,idx++)
   {
      vin(idx)=pos->first;                      //sorted value
      idxout(idx)=pos->second;                  //sorted index
   }
   octave_value_list retval(vin);               //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