From 5e7e64e96d5abaca4586348e441268923e40f574 Mon Sep 17 00:00:00 2001 From: "Markus \"Holli\" Holzer" Date: Tue, 22 Sep 2020 10:17:18 +0200 Subject: faster! faster!! --- challenge-079/markus-holzer/raku/bench.raku | 84 +++++++++++++++++++++++------ challenge-079/markus-holzer/raku/ch-1.raku | 19 +++++-- 2 files changed, 84 insertions(+), 19 deletions(-) diff --git a/challenge-079/markus-holzer/raku/bench.raku b/challenge-079/markus-holzer/raku/bench.raku index 1ab34ceea2..a37c8befaa 100644 --- a/challenge-079/markus-holzer/raku/bench.raku +++ b/challenge-079/markus-holzer/raku/bench.raku @@ -1,32 +1,86 @@ use Bench; +use experimental :cached; unit sub MAIN(Int $N = 42); -#say i($N); -#say r($N); -#say f($N); -#say k($N); -#say l($N); - +#say ($N...1).map( &i ).sum; +#say ($N...1).map( &r ).sum; +#say (1..$N).map( &f ).sum; +#say (1..$N).map( &k ).sum; +#say ($N...1).map( &l ).sum; +#say a($N); +#say b($N); +#exit; sub i { +$^n.base(2).indices(1) } sub r { +($^n.base(2) ~~ m:g/1/) } -sub f { +sub f is cached { $^n == 0 ?? 0 !! $^n !%% 2 + f( $^n div 2 ) } -sub k($n is copy) { +sub k($n is copy) is cached { my $c = 0; while $n != 0 { $n = $n +& ($n-1); $c++ }; $c } -sub l { +sub l is cached { state @b = 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4; $^n == 0 ?? 0 !! @b[ $^n +& 0xf ] + l($^n +> 4) } -Bench.new.timethese( 10000, { - base2-with-indices => { i($N) }, - base2-with-regex => { r($N) }, - div2-recursive => { f($N) }, - kernighan => { k($N) }, - lookup-recursive => { l($N) }}) \ No newline at end of file +sub a($n) { + my @scale = (1, 2 * * ...^ * > $n); + my $total-bits = 0; + + for @scale -> $pwr { + my $fill = ($n + 1) / (2 * $pwr); + my $max = $pwr * 2; + + my $fill-full = $fill.Int; + my $fill-frac = $fill - $fill-full; + + my $bits-full = $fill-full * $pwr; + my $bits-frac = 0; + + if $fill-frac > 0.5 { + $bits-frac = ($fill-frac - 0.5) * $max; + # say "($fill-frac - 0.5) * $pwr" if $verbose; + } + + my $bits = $bits-full + $bits-frac; + # say "bits-full=$bits-full, bits-frac=$bits-frac, bits=$bits" if $verbose; + + $total-bits += $bits; + } + + $total-bits; +} + +sub b(Int $N) +{ + my Int $t = 2; + my Int $r = 0; + my Int $n = $N; + + while $n { + my $a = $t +> 1; + my $s = $N +& ( $t - 1); + my $d = ( $N div $t ); + + $r += $d * $a; + $r += $s - $a + 1 if $s > $a - 1; + $t = $t +< 1; + $n = $n +> 1; + } + + return $r +} + +Bench.new.timethese( 1000, { + ash => { a($N) }, + holli => { b($N) }, +# base2-with-indices => { ($N...1).map( &i ).sum }, +# base2-with-regex => { ($N...1).map( &r ).sum }, +# div2-recursive => { ($N...1).map( &f ).sum }, +# kernighan => { ($N...1).map( &k ).sum }, +# lookup-recursive => { ($N...1).map( &l ).sum } +})git \ No newline at end of file diff --git a/challenge-079/markus-holzer/raku/ch-1.raku b/challenge-079/markus-holzer/raku/ch-1.raku index 592d814445..9ccf316272 100644 --- a/challenge-079/markus-holzer/raku/ch-1.raku +++ b/challenge-079/markus-holzer/raku/ch-1.raku @@ -1,7 +1,18 @@ unit sub MAIN( Int $N ); -# This is not only the simplest, but also a quite fast solution -# It only loses (sometimes) to the kernighan algorithm -# See bench.raku in this directory +my Int $t = 2; +my Int $r = 0; +my Int $n = $N; -say ($N...1).map( + *.base(2).indices(1) ).sum % 1000000007 \ No newline at end of file +while $n { + my $a = $t +> 1; + my $s = $N +& ( $t - 1); + my $d = ( $N div $t ); + + $r += $d * $a; + $r += $s - $a + 1 if $s > $a - 1; + $t = $t +< 1; + $n = $n +> 1; +} + +say $r % 1000000007; \ No newline at end of file -- cgit From 93f93db1b10b67f24fed13405eb7c69c4f98011a Mon Sep 17 00:00:00 2001 From: "Markus \"Holli\" Holzer" Date: Tue, 22 Sep 2020 10:30:09 +0200 Subject: faster! faster!! --- challenge-079/markus-holzer/raku/bench.raku | 16 ++++++++-------- challenge-079/markus-holzer/raku/ch-1.raku | 10 +++++----- 2 files changed, 13 insertions(+), 13 deletions(-) diff --git a/challenge-079/markus-holzer/raku/bench.raku b/challenge-079/markus-holzer/raku/bench.raku index a37c8befaa..b137f7e90d 100644 --- a/challenge-079/markus-holzer/raku/bench.raku +++ b/challenge-079/markus-holzer/raku/bench.raku @@ -8,8 +8,8 @@ unit sub MAIN(Int $N = 42); #say (1..$N).map( &f ).sum; #say (1..$N).map( &k ).sum; #say ($N...1).map( &l ).sum; -#say a($N); -#say b($N); +say a($N); +say b($N); #exit; sub i { +$^n.base(2).indices(1) } @@ -63,13 +63,13 @@ sub b(Int $N) while $n { my $a = $t +> 1; - my $s = $N +& ( $t - 1); + my $s = $N +& ( $t - 1 ); my $d = ( $N div $t ); - $r += $d * $a; - $r += $s - $a + 1 if $s > $a - 1; - $t = $t +< 1; - $n = $n +> 1; + $r += $d * $a; + $r += 1 + $s - $a if $s > $a - 1; + $t +<= 1; + $n +>= 1; } return $r @@ -83,4 +83,4 @@ Bench.new.timethese( 1000, { # div2-recursive => { ($N...1).map( &f ).sum }, # kernighan => { ($N...1).map( &k ).sum }, # lookup-recursive => { ($N...1).map( &l ).sum } -})git \ No newline at end of file +}) \ No newline at end of file diff --git a/challenge-079/markus-holzer/raku/ch-1.raku b/challenge-079/markus-holzer/raku/ch-1.raku index 9ccf316272..bf62b2bf06 100644 --- a/challenge-079/markus-holzer/raku/ch-1.raku +++ b/challenge-079/markus-holzer/raku/ch-1.raku @@ -6,13 +6,13 @@ my Int $n = $N; while $n { my $a = $t +> 1; - my $s = $N +& ( $t - 1); + my $s = $N +& ( $t - 1 ); my $d = ( $N div $t ); - $r += $d * $a; - $r += $s - $a + 1 if $s > $a - 1; - $t = $t +< 1; - $n = $n +> 1; + $r += $d * $a; + $r += 1 + $s - $a if $s > $a - 1; + $t +<= 1; + $n +>= 1; } say $r % 1000000007; \ No newline at end of file -- cgit From 083ff144a1eeebd1c7783dfae1acb78f63fedf65 Mon Sep 17 00:00:00 2001 From: "Markus \"Holli\" Holzer" Date: Tue, 22 Sep 2020 11:08:32 +0200 Subject: faster! faster!! --- challenge-079/markus-holzer/raku/bench.raku | 30 ++++++++++++++--------------- challenge-079/markus-holzer/raku/ch-1.raku | 27 +++++++++++++------------- 2 files changed, 29 insertions(+), 28 deletions(-) diff --git a/challenge-079/markus-holzer/raku/bench.raku b/challenge-079/markus-holzer/raku/bench.raku index b137f7e90d..c42bbb0ae6 100644 --- a/challenge-079/markus-holzer/raku/bench.raku +++ b/challenge-079/markus-holzer/raku/bench.raku @@ -55,24 +55,24 @@ sub a($n) { $total-bits; } -sub b(Int $N) +sub b(Int \N) { - my Int $t = 2; - my Int $r = 0; - my Int $n = $N; - - while $n { - my $a = $t +> 1; - my $s = $N +& ( $t - 1 ); - my $d = ( $N div $t ); - - $r += $d * $a; - $r += 1 + $s - $a if $s > $a - 1; - $t +<= 1; - $n +>= 1; + my Int \t = 2; + my Int \r = 0; + my Int \n = N; + + while n { + my Int \a = t +> 1; + my Int \s = N +& ( t - 1 ); + my Int \d = N div t; + + r := r + d * a; + r := r + 1 + s - a if 1 + s > a; + t := t +< 1; + n := n +> 1; } - return $r + return r } Bench.new.timethese( 1000, { diff --git a/challenge-079/markus-holzer/raku/ch-1.raku b/challenge-079/markus-holzer/raku/ch-1.raku index bf62b2bf06..c9215dde2f 100644 --- a/challenge-079/markus-holzer/raku/ch-1.raku +++ b/challenge-079/markus-holzer/raku/ch-1.raku @@ -1,18 +1,19 @@ -unit sub MAIN( Int $N ); +unit sub MAIN( Int \N ); -my Int $t = 2; -my Int $r = 0; -my Int $n = $N; +my Int \t = 2; +my Int \r = 0; +my Int \n = N; -while $n { - my $a = $t +> 1; - my $s = $N +& ( $t - 1 ); - my $d = ( $N div $t ); +while n { + my Int \a = t +> 1; + my Int \s = N +& ( t - 1 ); + my Int \d = N div t; - $r += $d * $a; - $r += 1 + $s - $a if $s > $a - 1; - $t +<= 1; - $n +>= 1; + r := r + d * a; + r := r + 1 + s - a if 1 + s > a; + t := t +< 1; + n := n +> 1; } -say $r % 1000000007; \ No newline at end of file + +say r % 1000000007; \ No newline at end of file -- cgit From 4363345dd35aab6d50430cafdcc9e19ca3d9ac6a Mon Sep 17 00:00:00 2001 From: "Markus \"Holli\" Holzer" Date: Tue, 22 Sep 2020 11:10:31 +0200 Subject: faster! faster!! --- challenge-079/markus-holzer/raku/bench.raku | 8 ++++---- challenge-079/markus-holzer/raku/ch-1.raku | 8 ++++---- 2 files changed, 8 insertions(+), 8 deletions(-) diff --git a/challenge-079/markus-holzer/raku/bench.raku b/challenge-079/markus-holzer/raku/bench.raku index c42bbb0ae6..76ba62d8fe 100644 --- a/challenge-079/markus-holzer/raku/bench.raku +++ b/challenge-079/markus-holzer/raku/bench.raku @@ -66,10 +66,10 @@ sub b(Int \N) my Int \s = N +& ( t - 1 ); my Int \d = N div t; - r := r + d * a; - r := r + 1 + s - a if 1 + s > a; - t := t +< 1; - n := n +> 1; + r := r + d * a; + r := r + 1 + s - a if 1 + s > a; + t := t +< 1; + n := n +> 1; } return r diff --git a/challenge-079/markus-holzer/raku/ch-1.raku b/challenge-079/markus-holzer/raku/ch-1.raku index c9215dde2f..8aa1e57dd2 100644 --- a/challenge-079/markus-holzer/raku/ch-1.raku +++ b/challenge-079/markus-holzer/raku/ch-1.raku @@ -9,10 +9,10 @@ while n { my Int \s = N +& ( t - 1 ); my Int \d = N div t; - r := r + d * a; - r := r + 1 + s - a if 1 + s > a; - t := t +< 1; - n := n +> 1; + r := r + d * a; + r := r + 1 + s - a if 1 + s > a; + t := t +< 1; + n := n +> 1; } -- cgit