• bearophile <bearophileHUGS lycos.com> Mar 12 2008

bearophile <bearophileHUGS lycos.com> writes:

If the set values are known only a run time then you can use the isIn()
function from my d libs that works with arrays.
And soon you will be able to use the set() constructor too (it builds an AA
inside).

If the set values are known at compile time you may use something like this:


import std.stdio: putr = writefln;

const bool do_speed_tests = true; // Put this to true if you want to run the
speed tests


/***********************************************
Given one or more items, of different types too, it builds a struct at
compile time with the opIn_r() method, that allows to look (with a linear
scan) for an item inside.
*/
_Bunch!(Types) bunch(Types...)(Types items) {
    return _Bunch!(Types)(items);
}

struct _Bunch(Types...) {
    Types items; // tuple

    bool opIn_r(Tx)(Tx x) {
        // no compile-time hashing yet
        foreach (el; items) // this is a static foreach
            static if (is(typeof(el == x)))
                if (el == x)
                    return true;
        return false;
    }
    // toString too can be defined
}

/// To be sure to execute a function at compile time.
template StaticEval(A...) {
    const typeof(A[0]) StaticEval = A[0];
}


static if(do_speed_tests) {
    static import std.c.time; // *****

    /*********************************
    Return the seconds (a double) from the start of the program.
    */
    double clock() {
        auto t = std.c.time.clock();
        if (t == -1)
            return 0.0;
        else
            return t/cast(double)std.c.time.CLOCKS_PER_SEC;
    }

    struct _LSet(T) {
        T[] set;

        bool opIn_r(U)(U u) {
            foreach(v; set)
                if (v == u)
                    return true;
            return false;
        }
    }

    struct LSet {
        static _LSet!(T) opCall(T)(T[] x ...) {
            return _LSet!(T)(x);
        }
    }

    void bunch_benchmark() {
        const uint N = 20_000_000;

        auto t = clock;
        uint result;
        auto b1 = LSet([1U, 2U, 3U, 4U]);
        for (uint i; i < N; ++i)
            result += ((i % 5U) in b1);
        putr(clock - t, " s ", result);

        t = clock;
        result = 0;
        auto b2 = bunch(1U, 2U, 3U, 4U);
        for (uint i; i < N; ++i)
            result += ((i % 5U) in b2);
        putr(clock - t, " s ", result);

        t = clock;
        result = 0;
        for (uint i; i < N; ++i) {
            switch (i % 5U) {
                case 1U, 2U, 3U, 4U:
                    result++;
                    break;
                default:
                    break;
            }
        }

        t = clock;
        result = 0;
        for (uint i; i < N; ++i) {
            uint i5 = i % 5U;
            if (i5 == 1U || i5 == 2U || i5 == 3U || i5 == 4U)
                result++;
        }
        putr(clock - t, " s ", result);

        t = clock;
        result = 0;
        for (uint i; i < N; ++i) {
            switch (i % 5U) {
                case 1U, 2U, 3U, 4U:
                    result++;
                    break;
                default:
                    break;
            }
        }
        putr(clock - t, " s ", result);

        // Timings, N = 20_000_000, -O -release -inline:
        //   3.33 s 16000000 (LSet)
        //   2.23 s 16000000 (bunch)
        //   2.07 s 16000000 (if)
        //   1.82 s 16000000 (switch)
    }
}


void main() {
    // just to be sure it's created at compile time
    auto b = StaticEval!(bunch(2L, 7, 4U, "a"));
    assert(!(3 in b));
    assert(4 in b);
    assert("a" in b);

    static if (do_speed_tests)
        bunch_benchmark();
}

After more improvements, some unit testing, (and a better name) I may even
include this in my libs :-)

Bye,
bearophile