Scratch that; as template parameters they shouldn't hurt performance at all. That's a good idea; the user needs to pass lots of template parameters, but it's easy to create overloads that pass in defaults. Theoretically you should be able to have a version that is introsort, with identical performance. If someone else wants to write it, I'd be willing to maintain it in the Boost.Algorithm.Sorting library (assuming it is accepted); not that I'd try to stop the author from maintaining it if they wanted to. On Sun, May 10, 2009 at 6:54 AM, Steven Ross <spreadsort@gmail.com> wrote:
That looks good to me. Passing all the functors will hurt performance, but probably not horribly so if you make sure to keep the insertion sort threshold; you might even increase the insertion sort threshold a bit. After it's written if it makes a big difference we could add overloads with less functors. The point of this isn't to make a specialized fast sort; it's to make a sort that is as general as possible and is not too much slower than introsort.
Do you want to write it, Edouard?
On Sat, May 9, 2009 at 10:39 PM, Edouard A. <edouard@fausse.info> wrote:
How about this: [...] The calls and overloads for my suggestion would be: flex_sort(first, last) flex_sort(first, last, compare) flex_sort(first, last, compare, swap)
Exactly what I had in mind, except I was more thinking about something like
template < typename Iterator, typename Compare, int SmallThreshold, int DepthFallback, typename MainSort, typename FallbackSort, typename Swapper
void flex_sort(Iterator first, Iterator last, Compare compare)
Mainsort would be something like
Template <typename Iterator, typename Compare, typename Swapper> struct { size_t distance(Iterator first, Iterator last); // finds pivot & partition Iterator split(Iterator first, Iterator last); };
And all MainSort and FallbackSort would share some traits and tell what kind of iterator they need (to have static assertions and stuff, at compile time you would know that you're trying to use a sort algorithm that's inefficient for the iterators you have).
Swapper would be
struct {
Element get_elem(Iterator i); void operator()(Iterator left, Iterator right); };
So basically flex_sort would be something like (typing as I think, not valid C++):
void flex_sort(Iterator first, Iterator last, Compare compare, int depth = 0) { if (depth >= DepthFallBack) { FallbackSort<...>(compare, swapper)(first, last); } else { Iterator pivot = MainSort<...>(compare, swapper).split(first, last);
// pivot => last we didn't split but sort the stuff (means the data was too small to be split) if (pivot != last) { ++depth;
flex_sort(first, pivot, compare, depth); advance(pivot, 1); flex_sort(pivot, last, compare, depth); } } }
For quicksort, split would be:
void MainSort::split(first, last) { Iterator pivot = last;
if (distance(first, last) > threshold) { pivot = find_pivot(first, last);
Iterator start = first; advance(start, 1); pivot = partition (start, last, std::bind2nd(compare, swapper.get_elem(pivot)));
swapper(pivot, first); } else { insert_sort(first, last... ?); }
return pivot; }
What do you think?
--
EA
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost