Re: [boost] [iterator] std::sort on zip_iterator (repost)

Subject: Re: [boost] [iterator] std::sort on zip_iterator (repost)
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-05-10 09:54:02

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_at_[hidden]> 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
>