Rosetta Code

Sorting algorithms/Merge sort: Difference between revisions

Page Discussion

Sorting algorithms/Merge sort (view source)

Revision as of 10:45, 2 October 2023

1,700 bytes added ,  8 months ago
→‎{{header|Raku}}
imported>Rcmlz
imported>Rcmlz
Line 6,482:
=={{header|Raku}}==
<syntaxhighlight lang="raku" line>
#| Recursive, single-thread, merge-sortmergesort implementation
sub merge-sortmergesort ( @a ) {
return @a if @a <= 1;
 
# recursion step
my $m = @a.elems div 2;
my @l = samewith @a[ 0 ..^ $m ];
my @r = samewith @a[ $m ..^ @a ];
 
# short cut - in case of no overlapping in left and right parts
return flat @l, @r if @l[*-1] !after @r[0];
return flat @r, @l if @r[*-1] !after @l[0];
 
# merge step
return flat gather {
take @l[0] before @r[0]
?? @l.shift
!! @r.shift
while @l and @r;
 
take @l, @r;
}
}
}</syntaxhighlight>
}
</syntaxhighlight>
Some intial testing
 
Line 6,516 ⟶ 6,515:
output = 1 2 3 4 5 6 7 8 9</pre>
 
Let's implement it using parallel sorting.
 
<syntaxhighlight lang="raku" line>
#| Recursive, naive multi-thread, mergesort implementation
# no I/O or other blocking operation included -> low thread number appropriate - saving one for the system
sub mergesort-parallel-naive ( @a ) {
$*SCHEDULER = ThreadPoolScheduler.new( max_threads => Kernel.cpu-cores - 1 );
return @a if @a <= 1;
# many calculations but single calculation is fast -> large batch size appropriate
my UInt $BATCH = 2**10;
 
my $m = @a.elems div 2;
#| Recursive, multi-thread, merge-sort implementation
 
multi merge-sort-parallel ( @a where @a.elems < 2) { @a }
# recursion step launching new thread
multi merge-sort-parallel ( @a ) {
my @l = start { samewith @a[ 0 ..^ $m ] };
# meanwhile recursively sort right side
my @r = samewith @a[ $m ..^ @a ] ;
 
# as we went parallel on left side, we need to await the result
await @l[0] andthen @l = @l[0].result;
 
# short cut - in case of no overlapping left and right parts
return flat @l, @r if @l[*-1] !after @r[0];
return flat @r, @l if @r[*-1] !after @l[0];
 
# merge step
return flat gather {
take @l[0] before @r[0]
?? @l.shift
!! @r.shift
while @l and @r;
 
take @l, @r;
}
}
</syntaxhighlight>
 
and tune the batch size required to launch a new thread.
 
<syntaxhighlight lang="raku" line>
##| Recursive, batch tuned multi-thread, mergesort implementation
sub mergesort-parallel ( @a, $batch = 2**9 ) {
return @a if @a <= 1;
 
my $m = @a.elems div 2;
 
# recursion step
my @l = $m > $BATCH
my @l = $m >= $batch
?? start { samewith @a[ 0 ..^ $m ] }
!! ?? start { samewith @a[ 0 ..^ $m ];, $batch }
!! samewith @a[ 0 ..^ $m ], $batch ;
 
# meanwhile recursively sort right side
my @r = samewith @a[ $m ..^ @a ], $batch;
 
# if we went parallel on left side, we need to await the result
Line 6,555 ⟶ 6,584:
}
</syntaxhighlight>
 
Let's run some tests and a minimal benchmark
Let's run some tests
 
<syntaxhighlight lang="raku" line>
say "x" x 10 ~ " Testing " ~ "x" x 10;
use Test;
my @functions-under-test = &mergesort, &mergesort-parallel-naive, &mergesort-parallel;
my @testcases =
() => (),
Line 6,568 ⟶ 6,600:
;
 
plan @testcases.elems * @functions-under-test.elems;
use Benchmark;
for @functions-under-test -> &fun {
my $elem-length = 8;
say &fun.name;
my @unsorted of Str = ('a'..'z').roll($elem-length).join xx 10 * Kernel.cpu-cores * 2**10;
is-deeply &fun(.key), .value, .key ~ " => " ~ .value for @testcases;
my $runs = 10;
 
sub test-and-benchmark(&function) {
say &function.name;
say "Testing";
is-deeply &function(.key), .value, .key ~ " => " ~ .value for @testcases;
say "Benchmarking";
my ($start, $end, $diff, $avg) = timethis $runs, sub { &function(@unsorted) }
say "$runs runs avg: $avg secs";
}
done-testing;
 
&test-and-benchmark(&merge-sort);
&test-and-benchmark(&merge-sort-parallel);
</syntaxhighlight>
{{out}}
<pre>xxxxxxxxxx Testing xxxxxxxxxx
<pre>merge-sort
1..18
Testing
mergesort
ok 1 - =>
ok 2 - a => a
Line 6,594 ⟶ 6,617:
ok 5 - h b a c d f e g => a b c d e f g h
ok 6 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
mergesort-parallel-naive
Benchmarking
10 runs avg: 5 secs
merge-sort-parallel
Testing
ok 7 - =>
ok 8 - a => a
Line 6,604 ⟶ 6,624:
ok 11 - h b a c d f e g => a b c d e f g h
ok 12 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
mergesort-parallel
Benchmarking
ok 13 - =>
10 runs avg: 3.6 secs</pre>
ok 14 - a => a
ok 15 - a a => a a
ok 16 - b a 3 => 3 a b
ok 17 - h b a c d f e g => a b c d e f g h
ok 18 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧</pre>
 
and some Benchmarking
 
<syntaxhighlight lang="raku" line>
use Benchmark;
my $runs = 5;
my $elems = 10 * Kernel.cpu-cores * 2**10;
my @unsorted of Str = ('a'..'z').roll(8).join xx $elems;
my UInt $l-batch = 2**13;
my UInt $m-batch = 2**11;
my UInt $s-batch = 2**9;
my UInt $t-batch = 2**7;
 
say "elements: $elems, runs: $runs, cpu-cores: {Kernel.cpu-cores}, large/medium/small/tiny-batch: $l-batch/$m-batch/$s-batch/$t-batch";
 
my %results = timethese $runs, {
single-thread => { mergesort(@unsorted) },
parallel-naive => { mergesort-parallel-naive(@unsorted) },
parallel-tiny-batch => { mergesort-parallel(@unsorted, $t-batch) },
parallel-small-batch => { mergesort-parallel(@unsorted, $s-batch) },
parallel-medium-batch => { mergesort-parallel(@unsorted, $m-batch) },
parallel-large-batch => { mergesort-parallel(@unsorted, $l-batch) },
};
 
for %results.kv -> $name, ($start, $end, $diff, $avg) {
say "$name avg $avg secs"
}</syntaxhighlight>
<pre>
elements: 40960, runs: 5, cpu-cores: 4, large/medium/small/tiny-batch: 8192/2048/512/128
single-thread avg 9 secs
parallel-naive avg 7.4 secs
parallel-tiny-batch avg 2.8 secs
parallel-small-batch avg 2.8 secs
parallel-medium-batch avg 2.8 secs
parallel-large-batch avg 2.4 secs
</pre>
 
=={{header|REBOL}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/348810"