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 dont 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk