Combsort comparison

[Lutger]

bearophile wrote:
...
> 
> I don't know if my D #3 code is the best possible using Ranges, maybe there is
> a way to use them more efficiently, I have just started using D Ranges. In
> this program the left and right "cursors" keep their relative distance, and in
> practice the C++ program shows that two "single" iterators (instead of two
> pairs) can be enough for this program. If you know how to improve the ranges
> usage in D #3 you can tell me.
> 

I would be interested in this too, thanks for posting this. If I understood the 
algorithm right, the basic idea is a sliding window over the underlying 
container. Can this be expressed by a single range that does not offer random 
access at all? Probably not since a range can only shrink.  

Am I right in thinking this algorithm basically requires random access? Both the 
C++ version and the D version will work for ranges that don't do that, but the 
performance difference won't matter anymore because it is likely crap anyway. 

I am curious where exactly the performance difference comes from. A quick 
profile did not help much, everything was inlined!

With this translation exclusively for random access ranges performance is equal 
to your first D version (that uses arrays directly):

void combsort(alias less="a < b", Range)(Range data) 
    if (isRandomAccessRange!Range && hasSwappableElements!Range)
{
    alias binaryFun!less cmp;
    enum double SHRINK_FACTOR = 1.247330950103979;
    
    int gap = data.length;
    bool swaps = true;
    while (gap > 1 || swaps) 
    {
        if (gap > 1)
            gap /= SHRINK_FACTOR;
        swaps = false;
        foreach (i; 0 .. data.length - gap)
        {
            if (cmp(data[i + gap], data[i])) 
            {
                swap(data[i], data[i + gap]);
                swaps = true;
            }
        }
    }
}