DPaste - Paste #2887 - pastebin, online compiler and collaboration tool dedicated to D Programming Language

Code

module sortingnetworks;

import std.algorithm, std.array,std.conv, std.datetime,std.functional;
import std.random, std.range, std.stdio, std.typetuple;

int ceilLog2(int n)
{
    int i;
    if ((n & (n-1)) == 0) i = -1;
    while (n > 0) { ++i; n/= 2;}
    return i;
}

/**
 * Given a length n, returns an array of indices pairs
 * corresponding to a sorting network for length n.
 * Looks a bit like C code, isn't it?
 */
int[2][] sortingNetwork(int n)
{
    int[2][] network;
    auto t = ceilLog2(n);
    auto p = 1 << (t-1);
    while (p > 0)
    {
        auto q = 1 << (t-1);
        auto r = 0;
        auto d = p;
        while (d > 0)
        {
            foreach(int i; 0..n-d)
                if (r == (i & p)) network ~= [i, i+d];
            d = q-p;
            q /= 2;
            r = p;
        }
        p /= 2;
    }
    return network;
}

string buildSortingCode(size_t l)()
{
    enum network = sortingNetwork(l);
    string result;
    foreach(elem; network) result ~= 
        "t1 = input["~to!string(elem[0])~"];
         t2 = input["~to!string(elem[1])~"];
         if (!binaryFun!pred(t1, t2))
         { 
             auto temp = t2;
             input["~to!string(elem[1])~"] = t1;
             input["~to!string(elem[0])~"] = temp;
         }\n";
    return result;
}

template networkSort(size_t l)
{
    mixin(
    "void networkSort(alias pred = \"a < b\", R)(ref R input)
     if (isRandomAccessRange!R)
     { 
        //enforce(input.length >= " ~to!string(l) ~ ");
        ElementType!R t1, t2;" ~ buildSortingCode!(l)()
~ "\n}");
}

template StaticIota(int max) if (max > 0)
{
    static if (max == 1)
        alias TypeTuple!(1) StaticIota;
    else
        alias TypeTuple!(StaticIota!(max-1), max) StaticIota;
}

void main()
{
    void compareSorts(int size)()
    {
        alias networkSort!size nws;

void basis()
        {
            int[] input = iota(0,size).array;
            randomShuffle(input);
        }

void stdalgo()
        {
            int[] input = iota(0,size).array;
            randomShuffle(input);
            sort(input);
        }

void network()
        {
            int[] input = iota(0,size).array;
            randomShuffle(input);
            nws(input);
        }

auto b = benchmark!(stdalgo, network, basis)(100_000);
        float sortTime = b[0].to!("msecs", float);
        float networkTime =  b[1].to!("msecs", float);
        float referenceTime =  b[2].to!("msecs", float);

networkTime -= referenceTime;
        sortTime -= referenceTime;

writefln("Size %s, network: %2.2f, std.algorithm.sort: %2.2f, ratio network/std.algo: %2.2f"
                , size, networkTime, sortTime, networkTime/sortTime);
    }

foreach(size; StaticIota!(32))
        compareSorts!(size)();
}

Paste info

Author: Guest

Views: 116

Private: no

Expires: Never

Uploaded: 17.10.12 20:52

Votes: 0

Compilation

Compiler: DMD 2.060

Pointer size: m64

Code

Paste info

Compilation

Actions

Confirm

Confirm