DEV Community

loading...
Cover image for Weekly Challenge #083 Task #2 :: (Perl)

Weekly Challenge #083 Task #2 :: (Perl)

jeongoon profile image Myoungjin Jeon ・4 min read

TASK #2 › Flip Array

While Testing Race

I wrote a Raku code to solve the task #2. My first goal is that get faster result by using more resource of my laptop by using .race. So I came up with

... snip
    @n.combinations( 1..^ @n ).
    race( :8degree:500batch ).  👈
    map(
        -> \n {
            with $s - 2 * n.sum { # same as ( $s- n.sum ) - n.sum
                next if $_ < 0;
                $_ => n.elems
            }
        } ).
    race( :8degree:500batch ).  👈
    min.
    value.
    say
}
Enter fullscreen mode Exit fullscreen mode

A couple of race() are added because I found the two throttles, the result was satisfying. It wasn't dramatically faster but about twice faster. You can find more details Here

When we compare the speed of between making permutations by using [X] and combinations, permutations is always faster than combinations.

Permutations vs Combinations [Speed]

i.e.

> ([X] (^20).map({ $_, -$_ })).elems # ^20 eqv. 0..19
1048576
Enter fullscreen mode Exit fullscreen mode

is faster than,

> (^20).combinations.elems
1048576
Enter fullscreen mode Exit fullscreen mode

When you run it in Raku you will feel that permutaions is definitely faster.

One question came across my head. "What if I could reduce the length of the combinations?".
In this case, we can reduce the combinations because we only need the summation of two groups.

for example...

(12) <=> (7, 4)
Enter fullscreen mode Exit fullscreen mode

So If we know summation of one group(12) then we can calculate another(7,4). because we know total sum as well (12+7+4)
i.e.

  sum(7,4) == sum(12,7,4) - sum(12)
Enter fullscreen mode Exit fullscreen mode

If the length of the list are the same(len 4 + len 4 = len 8). I can even check half side of the list but... I just skipped that part. I doesn't look helpful here (or maybe it does.. IDK...)

Returning to Perl

As a result, I wrote a Perl code like below.

... snip ...
my $totalSum = sum @N;
my $halfLen  = int( .5 * @N ); # reduce the combinations in half

# initial values ...
my $minElems = +@N;
my $minSum  = $totalSum;

for my $combi ( combinations( +@N, 1, $halfLen ) ) {
    my $aSum = sum @N[ @$combi ];
    my $bSum = $totalSum - $aSum;

    my $curr =
      ( # $aSum == $bSum
       [ 0, ( scalar @$combi < $halfLen
              ? scalar @$combi : scalar( @N - @$combi) ) ],
        # $aSum  > $bSum
       [ $aSum - $bSum, scalar ( @N - @$combi) ],
        # $aSum  < $bSum
       [ $bSum - $aSum, scalar @$combi ] )[ $aSum <=> $bSum ];

    print "[sum: $$curr[0], elems: $$curr[1]] with @N[@$combi] ... " if $d;

    if ( $$curr[0] > $minSum ) {        # minimum sum not changed
        next;
    }
    elsif ( $$curr[0] < $minSum ) {     # minimum sum cahnged
                                        # so does minimum elements
        ( $minSum, $minElems ) = @$curr;
    }
    elsif ( $$curr[1] < $minElems ) {   # minimum sum is same
                                        # but no. elements is less
        $minElems = $$curr[1];
    }
    else {
        say "" if $d;
    }
}
... snip
Enter fullscreen mode Exit fullscreen mode

I tested with a bit long list which is

12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
Enter fullscreen mode Exit fullscreen mode

And the result is reasonably fast.

Not So Precise Benchmarks

Perl With Combinatorics Module

shell> time perl ch-2.using-algorithm-combinatorics.pl 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
6

________________________________________________________
Executed in    2.41 secs   fish           external 
...
Enter fullscreen mode Exit fullscreen mode

With My own combinations module

shell> time perl ch-2.pl 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
6

________________________________________________________
Executed in    1.86 secs   fish           external 
...
Enter fullscreen mode Exit fullscreen mode

But those are still slower than any compiled my version of Go and Haskell
(I'll update the full source link after pull request finished)

Go version

Note: that ch-2.go use full length of combinations, I just start to learn golang and wrote the code before thinking shirinking the combinations. nevertheless result was so quite satisfying.

shell> go run ch-2.go 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8 # not compiled
6

________________________________________________________
Executed in  443.40 millis    fish           external 
...
Enter fullscreen mode Exit fullscreen mode
shell> go build ch-2.go  # go has already optimise the code
shell> time ./ch-2 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
6

________________________________________________________
Executed in  238.32 millis    fish           external 
...
Enter fullscreen mode Exit fullscreen mode

Haskell Version

Here we go, Haskell version. I made my own version of combinations again. you can find it HERE because -- In Haskell -- recursive version is unbeatably faster than my own version of non-recursive combinations.

shell> ghc -O2 ch-2.hs
shell> time ./ch-2 12 7 4 5 6 9 20 12 7 4 5 6 9 20 9 4 2 1 13 8
6

________________________________________________________
Executed in  202.51 millis    fish           external 
...
Enter fullscreen mode Exit fullscreen mode

I reckon that go version will win after optimizing the code where I did in Perl, but I don't think I will change the code. 😓

However Raku version was not successful

Here is link for code, but I conclude that Raku doesn't like flow control. and IMHO, this part will be where Raku needs to improve!! 😅

Discussion

pic
Editor guide