Re: D in the TIOBE top

[Martin Nowak]

On Mon, 12 Sep 2011 18:57:16 +0200, bearophile <bearophileh...@lycos.com>  
wrote:

Timon Gehr:
You lose vs haskell because haskell does not recompute the same PowerSet
multiple times.

Are you sure? I have tried with memoization, but now it's slower (about  
5.8 seconds).

Note: to use memoize I have had to add the opCall. Is this really  
necessary for memoization of a struct?


import std.stdio, std.array, std.range, std.functional;

struct PowerSet(T) {
    T[] items;

    static PowerSet opCall(T[] it) {
        PowerSet p;
        p.items = it;
        return p;
    }

    int opApply(int delegate(ref T[]) dg) {
        int result;
        T[] res;
        T[30] buf;

        if (!items.length) {
            result = dg(res);
        } else {
            outer:
            foreach (opt; [items[0..1], []]) {
                buf[0 .. opt.length] = opt[];
                alias memoize!PowerSet mPowerSet;
                foreach (r; mPowerSet(items[1..$])) {
                    buf[opt.length .. opt.length + r.length] = r[];
You are copying recursively here. You should pass a slice to the recursive  
instance.
                    res = buf[0 .. (opt.length + r.length)];
                    result = dg(res);
                    if (result) break outer;
                }
            }
        }

        return result;
    }
}

void main() {
    size_t count;
    foreach (x; PowerSet!int(array(iota(22))))
        count++;
    writeln(count);
}


Bye,
bearophile

Besides this can be wrapped in a random access range,
which takes predictable 65ms * 2 ^ (setSize - 22) for me.
https://gist.github.com/1211961