To count number of quadruplets with sum = 0

bearophileHUGS at lycos.com bearophileHUGS at lycos.com
Sat Mar 17 22:15:15 CET 2007


Mark Dufour:
> FWIW, the original program can also be compiled with Shed Skin (http://
> mark.dufour.googlepages.com), an experimental (static-)Python-to-C++
> compiler, resulting in a speedup of about 8 times for a single test
> with 500 tuples.

If we want to play, then this is a literal translation to D (I am not
much good in D yet, so maybe there are ways to improve this code a
bit), as you can see D syntax isn't that bad (I think sometimes D
copies some Python syntax):


// Compile with:   dmd -O -release solver.d
import std.stdio, std.stream, std.string;

void main() {
    size_t sch;
    size_t[size_t] h;
    size_t[] q,w,e,r;

    int nrow = -1;
    auto datafile = new File("m4000.txt", FileMode.In);
    foreach(char[] row; datafile) {
        if (nrow == -1) {
            q.length = row.atoi();
            w.length = row.atoi();
            e.length = row.atoi();
            r.length = row.atoi();
        } else {
            char[][] srow = row.split();
            q[nrow] = srow[0].atoi();
            w[nrow] = srow[1].atoi();
            e[nrow] = srow[2].atoi();
            r[nrow] = srow[3].atoi();
        }
        nrow++;
    }

    foreach (x; q)
        foreach (y; w)
            h[x+y]++;

    foreach (x; e)
        foreach (y; r) {
            size_t* pointer = -x-y in h;
            if (pointer)
                sch += *pointer;
            // simpler but slower:
            // if (-x-y in h)
            //     sch += h[-x-y];
    }

    writefln(sch);
}


On my PC with the 1000 lines file this is about 2.2 times faster than
my  Psyco version and about 4.6 times faster than the same code
without Psyco.

Bye,
bearophile




More information about the Python-list mailing list