Update down there

Good day, fellow monks.

My question is more of academic interest than practical. Here's a simple task from an old CS collegiate contest: Sums in a Triangle.

It's definitely NOT of the type Perl excels at but still I decided to give it a try. (Actually, my main motivation is that a working Python solution exists!)

My C solution works fast and passed the online judge, it's O(n^2) and very efficient. But the best Perl code I came up with requires at least 6 seconds in the worst case on my fairly powerful Core 2 Duo 2.66Ghz box. It uses the same algorithm I used in C.

If anyone feels like playing with it, I'd be very interested in results.

My C code (before compressing into 256 chars which is not interesting): 

#include <stdio.h>

int data[100][100];

int sumintr(int nr) {
    int r, col;
    for(r = nr - 1 - 1; r >= 0; --r) {
        for(col = 0; col <= r; ++col) {
            data[r][col] += data[r + 1][
              data[r + 1][col] > data[r + 1][col + 1]
                ? col
                : col + 1
              ];
        }
    }

    return data[0][0];
}

int main() {
    int ns, nr, s, r, col;

    scanf("%d\n", &ns);
    for(s = 0; s < ns; ++s) {
        scanf("%d\n", &nr);
        for(r = 0; r < nr; ++r) {
            for(col = 0; col <= r; ++col)
                scanf("%d", &data[r][col]);
        }

        printf("%d\n", sumintr(nr));
    }
}

[download]
My best Perl code (strict was removed):
#!/usr/bin/perl

for (1..<>) {
    @tr =
        map { [split ' ', <>] } 1 .. <>;

    $prev = pop @tr;
    for $cur (reverse @tr) {
        $g = $prev->[0];
        for (0 .. $#$cur) {
            $cur->[$_] += ($f = $g) > ($g = $prev->[$_ + 1])
                ? $f
                : $g;
        }

        $prev = $cur;
    }

    print "$prev->[0]\n";
}

[download]

The worst test case I'm banging my head against: http://dl.dropbox.com/u/360558/input_big.txt.gz (will decompress to 14Mb)

(Probably, my first reaction to such a question would be something like: "Wow, compiled C code is faster than Perl! Thank you, Captain Obvious!" I would definitely not spend several hours examining NYTProf beautiful reports unless I knew that some guy solved it in Python (albeit using a lot of memory, which is, by the way, a good indicator of a different algorithm)).

Update. Big thanks to ikegami and zwon for their suggestions in comments! I just decreased my runtime by almost 30% implementing them! The last version looks like this:

#!/usr/bin/perl

undef $/; @file = split ' ', scalar <>;

for (1 .. shift(@file)) {
    $rows = $file[$cur++];

    @s = (0) x ($rows + 1);
    for (1 .. $rows) {
        ($i, $y) = (0, 0);
        $cur += $_ - 1;

        for ($cur .. $cur + $_ - 1) {
            $x = $y;
            $y = $s[$i];
            $s[$i++] = $file[$_] + ($x > $y ? $x : $y);
        }
    }

    $m = 0;
    $m = $m > $_ ? $m : $_ for @s;
    print "$m\n";

    $cur += $rows;
}

[download]

It does not pass the SPOJ judge yet, although. But the box which will run it in 2 sec should be only twice as fast as my desktop :)

--kap

In reply to Adding a lot of small integers by kappa

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.