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
}
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 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
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 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
...
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
...
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
...
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
...
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!! 😅
Top comments (0)