Re: [boost] [library submission] smoothsort

Subject: Re: [boost] [library submission] smoothsort
From: Edouard A. (edouard_at_[hidden])
Date: 2008-12-14 12:53:27

Sorry for the double post, but good news everyone:

I just did compilation with profiling. Smoothsort is twice faster than
std::sort on sorted input, up to 5 times slower on random input. 

My benchmark output, on a vector of size 1,000,000 :

        std::sort running time: 0.171 s
        std::sort running time (sorted): 0.082 s
        Smoothsort running time: 0.6 s
        Smoothsort running time (sorted): 0.035 s

Now I must figure out why without profiling I don’t have good performances.
Maybe there's some built-in optimization in MS' compiler when it encounters
its own std::sort? 

-- 
Edouard
> -----Original Message-----
> From: boost-bounces_at_[hidden] [mailto:boost-
> bounces_at_[hidden]] On Behalf Of Christopher Jefferson
> Sent: dimanche 14 décembre 2008 16:06
> To: boost_at_[hidden]
> Subject: Re: [boost] [library submission] smoothsort
> 
> I would certainly be interested in such a library.
> 
> Have you benchmarked it against std::sort in any compilers?
> 
> Chris
> 
> On 14 Dec 2008, at 14:18, Edouard A. wrote:
> 
> > Hello,
> >
> >
> >
> > I just finished a C++ implementation of the smoothsort algorithm (a
> > derivative of the heapsort algorithm by Dijkstra that, in his words,
> > "is of
> > order N log N in the worst case, but of order N in the best case,
> > with a
> > smooth transition between the two").
> >
> >
> >
> > When sorting nearly sorted containers smoothsort achieves excellent
> > performances. If you keep sorting the same container, smoothsort may
> > be the
> > right algorithm for you.
> >
> >
> >
> > This implementation works on all sortable containers, with best
> > performances
> > on containers supporting random access iterators (in other words,
> > smoothsorting a std::list is quite slow). It only requires  the "<"
> > operator
> > between two elements and the user can supply the function with a
> > binary
> > predicate.
> >
> >
> >
> > To my knowledge, there is no equivalent public C++ implementation.
> >
> >
> >
> > I was wondering if this was interesting enough to be included in the
> > boost
> > library.
> >
> >
> >
> > Kind regards.
> >
> >
> >
> > --
> >
> >
> >
> > Edouard Alligand
> >
> > _______________________________________________
> > Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
> 
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost