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 10:09:11

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