OT:

Cumulative sums are fun. Here's its application (sum "-1" and "1"s, but with "saturation": don't fall below zero) for another task, PWC 346-1 "Longest Parenthesis". There are at least half a dozen identical (i.e. verbatim) Perl solutions, doesn't matter if it's because task is trivial, or "AI" was involved, or subroutine was copied. In fact, that Perl solution is significantly faster for medium and long inputs than a few others based on nested loops or regular expressions. Below is my translation of it to C. (I'm not fluent in C, can it be written better? Hopefully, I haven't put it in much disadvantage because of that.)

Surprisingly, my "cumulative sum" solution is faster, though it involves second sweep over input and seemingly more arithmetic. For shorter, 1000 random strings 1000 chars long:

v5.42.0 / MSWin32-x64-multi-thread / 13.2.0
     Rate  pwc  sum
pwc 199/s   -- -46%
sum 365/s  84%   --

[download]

And for set of 100 of longer strings (100_000 length):

      Rate  pwc  sum
pwc 21.4/s   -- -56%
sum 48.2/s 125%   --

[download]

Why C and, hence, OT? I had Perl prototype, somewhat faster than mentioned Perl PWC solution; then did PDL prototype (~ 10x .. 20x faster, of course), but had to write a small PP fragment for it; and thought why not do it in C completely then, anyway. Had no intention to translate PWC Perl to C for competition; but found C++ solution in GH PWC directory. Something to compile to machine code, hurray. Well, for a single 1e6 chars long string it took twenty seconds, no joking. (C functions, below, are in milliseconds).

Perl code for the results above:

use strict;
use warnings;
use feature 'say';
use Config;
use Benchmark 'cmpthese';

say "$^V / $Config{ archname } / $Config{ gccversion }";

my $L = 1e5;
my $s = '(' x $L;
my @samples;

for ( 0 ... 99 ) {
    my $s1 = $s;
    for ( 0 .. $L - 1 ) {
        substr $s1, $_, 1, ')' if int rand 2
    }
    push @samples, $s1;
    die unless longest_p_pwc( $s1 ) ==
               longest_p_sum( $s1 )
}

cmpthese -3, {
    pwc => sub { longest_p_pwc( $_ ) for @samples },
    sum => sub { longest_p_sum( $_ ) for @samples },
};

sub valid_longest_parenthesis {
    my $s       = shift;
    my @stack   = (-1);
    my $max_len = 0;

    for my $i (0 .. length($s) - 1) {
        if (substr($s, $i, 1) eq "(") {
            push @stack, $i;
        } else {
            pop @stack;
            if (@stack) {
                $max_len = $max_len > ($i - $stack[-1])
                          ? $max_len : ($i - $stack[-1]);
            } else {
                push @stack, $i;  # New starting point
            }
        }
    }

    return $max_len;
}

use Inline C => << 'END_OF_C';

int longest_p_pwc( SV* str ) {
    STRLEN len;
    char* buf = SvPVbyte( str, len );
    
    int* stack = malloc( len * sizeof( int ));
    int stack_i = 0;
    stack[ 0 ] = -1;

    int max = 0;
    for ( int i = 0; i < len; i ++ ) {
        if ( buf[ i ] == '(' ) stack[ ++ stack_i ] = i;
        else {
            if ( stack_i > 0 ) {
                stack_i --;
                int cur = i - stack[ stack_i ];
                if ( cur > max ) max = cur;
            }
            else stack[ 0 ] = i;
        }
    }
    free( stack );
    
    return max;
}

int longest_p_sum( SV* str ) {
    STRLEN len;
    char* buf = SvPVbyte( str, len );
   
    int* pad = malloc( len * sizeof( int ));
    int sum = 0;
    for ( int i = 0; i < len; i ++ ) 
        pad[ i ] = sum = 
            sum + !sum + ( buf[ i ] == '(' ? 1 : -1 );
    int max = 0;
    int cur = 0;
    int counting = 0;
    int zeroless = 1;
    sum = 0;
    for ( int i = len - 1; i >= 0; i -- ) {
        zeroless = zeroless && pad[ i ];
        sum = zeroless 
            ? sum + !sum + ( buf[ i ] == ')' ? 1 : -1 ) 
            : 1;
        if ( pad[ i ] && sum ) {
            cur ++;
            counting = 1;
        }
        else if ( counting ) {
            if ( cur > max ) max = cur;
            counting = 0;
            cur = 0;
        }
    }
    if ( cur > max ) max = cur;
    free( pad );
    
    return max;
}

END_OF_C

[download]

In reply to Re^5: Weird performance issue with Strawberries and Inline::C by Anonymous Monk
in thread Weird performance issue with Strawberries and Inline::C by Anonymous Monk

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.