www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Comb Sort with ranges

reply bearophile <bearophileHUGS lycos.com> writes:
As exercise to learn D2 ranges usage I've translated to D2 the C++ version of
the Comb sort:
http://en.wikipedia.org/wiki/Comb_sort#C.2B.2B_Implementation

It wasn't easy, but on those tests it works!
Do you see errors or things that can be improved in this D2 code?

I have verified that the program performs the same swaps with the array and the
single linked list (but unittests are missing still).

The combsort_impl inner function is a workaround for the lack of the "old" view
of the input data in D postconditions.

In C++ the gap is of type
std::iterator_traits<ForwardIterator>::difference_type, but in D I have used
just an int, I don't know why they have used that type in C++.

In the C++ code itLeft and itRight are single items, probably single CPU words,
while in D they can be two words or more (for example when data is a dynamic
array). Can this cause some loss of performance compared to the C++ code? (I
have not done benchmarks to compare the performance of the C++ version with the
D version yet).


import std.algorithm: swap, binaryFun, sort;
import std.range: isForwardRange, walkLength, popFrontN, empty, front,
                  popFront, hasSwappableElements, equal;
import std.contracts: enforce;


void combsort(alias less="a < b", Range)(Range data)
    if (isForwardRange!Range && hasSwappableElements!Range) {

        static void combsort_impl(Range data) {
            // From: http://en.wikipedia.org/wiki/Comb_sort
            enum double SHRINK_FACTOR = 1.247330950103979;
            int gap = walkLength(data);
            bool swapped = true;

            while ((gap > 1) || swapped) {
                if (gap > 1)
                    gap /= SHRINK_FACTOR;

                swapped = false;
                auto right = data;
                popFrontN(right, gap);

                for (auto left = data; !right.empty; left.popFront,
right.popFront) {
                    if (binaryFun!(less)(right.front, left.front)) {
                        swap(left.front, right.front);
                        swapped = true;
                    }
                }
            }
        }

        // postcondition verified in debug mode only.
        // Workaround: necessary because D postconditions don't
        // support the "old" (original input data view) yet.
        debug {
            auto data_copy = array(data);
            sort!(less)(data_copy);
            combsort_impl(data);
            enforce(equal(data, data_copy));
        } else {
            combsort_impl(data);
        }
    } // end combsort()


// no way to give a checked name to the unittest yet
unittest { // tests of combsort()
    // TODO
} // end tests of combsort()

//---------------------

// imports local to the main()
// function-local imports not supported yet
import std.stdio: writeln;
import std.range: SListRange, array;
import std.algorithm: isSorted;

void main() {
    int[] a = [10, 1, 5, 3, 7, -1, 5, 21, -3];
    writeln(isSorted(a), " ", a);
    combsort(a);
    writeln(isSorted(a), " ", a);
    writeln();

    auto lst = SListRange!int(10, 1, 5, 3, 7, -1, 5, 21, -3);
    writeln(isSorted(lst), " ", array(lst));
    combsort(lst);
    writeln(isSorted(lst), " ", array(lst));
    writeln();

    /*
    // doesn't work with static arrays
    int[9] b = [10, 1, 5, 3, 7, -1, 5, 21, -3];
    writeln(isSorted(b), " ", b);
    combsort(b);
    writeln(isSorted(b), " ", b);
    writeln();
    */
}

Bye,
bearophile
Apr 20 2010
parent reply Ellery Newcomer <ellery-newcomer utulsa.edu> writes:
this is a bit off topic, but have you noticed that comb sort can 
consistantly beat the pants off phobos' built in sort for data of 
reasonable sizes? Admittedly, I didn't implement it using ranges (It's 
really cool that you can!) and just used arrays.
Apr 20 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Ellery Newcomer:

 this is a bit off topic, but have you noticed that comb sort can 
 consistantly beat the pants off phobos' built in sort for data of 
 reasonable sizes?


In my dlibs1 there is a tuned Quicksort that I have written that is about 3.5
faster than the built-in sort, so I am not surprised. (The built-in sort is not
a template, it used run-time typeinfo to work).



Admittedly, I didn't implement it using ranges (It's really cool that you can!)
and just used arrays.<


I have already found three bugs in that "cool" code, I will try to fix them and
I'll post an updated version.

Bye,
bearophile
Apr 21 2010
parent bearophile <bearophileHUGS lycos.com> writes:
This removes two of the three bugs. But this code doesn't work yet with a class
that implements a collection, because code like:
auto right = data;
copies just the reference to the data object. Suggestions welcome.

I have also seen that some of the functions of std.range don't work with static
arrays, so I've had to roll my own fixed versions, see the isSorted() below.

Bye,
bearophile



import std.algorithm: swap, binaryFun, sort;
import std.range: isForwardRange, walkLength, popFrontN, empty, front,
                  popFront, hasSwappableElements, equal;
import std.contracts: enforce;


void combsort(alias less="a < b", Range)(Range r)
    if (__traits(isStaticArray, Range) || (isForwardRange!Range &&
hasSwappableElements!Range)) {

        static void combsort_impl(Range2)(Range2 data) {
            // From: http://en.wikipedia.org/wiki/Comb_sort
            enum double SHRINK_FACTOR = 1.247330950103979;
            auto gap = walkLength(data);
            bool swapped = true;

            while ((gap > 1) || swapped) {
                if (gap > 1)
                    gap /= SHRINK_FACTOR;

                swapped = false;
                auto right = data;
                popFrontN(right, gap);

                for (auto left = data; !right.empty; left.popFront,
right.popFront) {
                    if (binaryFun!(less)(right.front, left.front)) {
                        swap(left.front, right.front);
                        swapped = true;
                    }
                }
            }
        }

        // postcondition verified in debug mode only.
        // Workaround: necessary because D postconditions don't
        // support the "old" (original input data view) yet.
        debug {
            static if (__traits(isStaticArray, Range)) {
                auto r_copy = array(r[]);
                sort!(less)(r_copy);
                combsort_impl(r[]);
                enforce(equal(r[], r_copy));
            } else {
                auto r_copy = array(r);
                sort!(less)(r_copy);
                combsort_impl(r);
                enforce(equal(r, r_copy));
            }
        } else {
            static if (__traits(isStaticArray, Range))
                combsort_impl(r[]);
            else
                combsort_impl(r);
        }
    } // end combsort()


// no way to give a checked name to the unittest yet
unittest { // tests of combsort()
    // TODO
} // end tests of combsort()


//------------------------------------

// imports local to the main()
// function-local imports not supported yet
import std.stdio: writeln;
import std.range: SListRange, array;
import std.algorithm: isSorted_impl = isSorted;
import std.string: format;

bool isSorted(alias less="a < b", Range)(Range data)
    if (__traits(isStaticArray, Range) || isForwardRange!Range) {
        static if (__traits(isStaticArray, Range))
            return isSorted_impl!(less)(data[]);
        else
            return isSorted_impl!(less)(data);
}

void main() {
    int[] a = [10, 1, 5, 3, 7, -1, 5, 21, -3];
    writeln(isSorted(a), " ", a);
    combsort(a);
    writeln(isSorted(a), " ", a);
    writeln();

    auto lst = SListRange!int(10, 1, 5, 3, 7, -1, 5, 21, -3);
    writeln(isSorted(lst), " ", array(lst));
    combsort(lst);
    writeln(isSorted(lst), " ", array(lst));
    writeln();

    int[9] b = [10, 1, 5, 3, 7, -1, 5, 21, -3];
    writeln(isSorted(b), " ", b);
    combsort(b);
    writeln(isSorted(b), " ", b);
    writeln();
}

Bye,
bearophile
Apr 21 2010