Myoungjin Jeon

Posted on

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

## 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
}
``````

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
``````

is faster than,

``````> (^20).combinations.elems
1048576
``````

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)
``````

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)
``````

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 toPerl

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
``````

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
``````

And the result is reasonably fast.

## Not So Precise Benchmarks

### Perl WithCombinatorics 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
...
``````

### WithMy 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
...
``````

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
...
``````
``````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
...
``````

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
...
``````

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!! 😅