Re: [boost] Re: FC++ -- reminder formal review ends today at midnightPST

From: Brian McNamara (lorgon_at_[hidden])
Date: 2004-03-03 08:10:22

On Wed, Mar 03, 2004 at 05:40:20AM +0100, Giovanni Bajo wrote:
> Jared Roberts wrote:
> > To help me evaluate the design, I wrote a few quick client programs to
> > try and get a feel for the 'language'.  The most instructive of these,
> > was a quicksort function, modelled after the example given on the
> > haskell home page ( http://www.haskell.org/aboutHaskell.html ):
> >
> > template<typename ordT>
> > struct quicksort : public c_fun_type<list<ordT>, list<ordT> >
> 
> Cute. Do you have some timings for this? How fast is it?

I did not time Jared's code, but I am sure it will be very slow
(compared to, say, std::sort on a std::vector).  There are lots of
intermediate heap-allocated data structures (lists) being created.
Like any quicksort, it's O(N^2), but the constant-factor costs here are
pretty high.

-- 
-Brian McNamara (lorgon_at_[hidden])