Rosetta Code

Sorting algorithms/Quicksort: Difference between revisions

Page Discussion

Sorting algorithms/Quicksort (view source)

Revision as of 10:08, 2 October 2023

9 bytes removed ,  8 months ago
→‎{{header|Raku}}
imported>Rcmlz
imported>Rcmlz
Line 8,229:
<syntaxhighlight lang="raku" line>
#| Recursive, single-thread, single-pass, quicksort implementation
multisub quicksort(@unsorted where @unsorted.elems < 2a) { @unsorted }
return @a if @a.elems < 2;
multi quicksort(@unsorted) {▼
my $pivot = @unsorteda.pick;
my %classprt{Order} is default([]) = @unsorteda.classify: * cmp $pivot;
|samewith(%classprt{Less}), |%classprt{Same}, |samewith(%classprt{More})
}
</syntaxhighlight>
Line 8,240:
 
<syntaxhighlight lang="raku" line>
#| 7-Line, recursiveRecursive, parallel, single-pass, quicksort implementation
multisub seven-line-quicksort-parallel-naive(@unsorted where @unsorted.elems < 2a) { @unsorted }
return @a if @a.elems < 2;
multi seven-line-quicksort-parallel(@unsorted) {▼
my $pivot = @unsorteda.pick;
my %partitionsprt{Order} is default([]) = @unsorteda.classify( * cmp $pivot );
my Promise $less = start { samewith(%partitionsprt{Less}) }
my $more = samewith(%partitionsprt{More});
await $less andthen |$less.result, |%partitionsprt{Same}, |$more;
}
</syntaxhighlight>
 
Let's tune the parallel execution by limitingapplying thea numberminimum ofbatch workersize threadsin andorder introducingto spawn a minimumnew batch sizethread.
 
<syntaxhighlight lang="raku" line>
#| Recursive, parallel, batch tuned, single-pass, quicksort implementation▼
constant $BATCH-SIZE = 2**10;
multisub quicksort-parallel(@unsorteda, $batch = 2**9) {▼
my atomicint $worker = $*KERNEL.cpu-cores;
return @a if @a.elems < 2;
▲#| Recursive, parallel, tuned, single-pass, quicksort implementation
 
proto quicksort-parallel(| --> Positional) {*}
multi quicksort-parallel(@unsorted where @unsorted.elems < 2) { @unsorted }
▲multi quicksort-parallel(@unsorted) {
# separate unsorted input into Order Less, Same and More compared to a random $pivot
my $pivot = @unsorteda.pick;
my %partitionsprt{Order} is default([]) = @unsorteda.classify( * cmp $pivot );
 
# atomically decide if we sort the Less partition on a new thread
my $less = ⚛$worker%prt{Less}.elems >= 0 &&$batch
?? start { samewith(%partitionsprt{Less}.elems >, $BATCH-SIZEbatch) }
??!! ( samewith(%prt{Less}, $batch);
$worker⚛--;
start {
LEAVE $worker⚛++;
samewith(%partitions{Less})
}
)
!! samewith(%partitions{Less});
 
# meanwhile use current thread for sorting the More partition
my $more = samewith(%partitionsprt{More}, $batch);
 
# if we went parallel, we need to await the result
Line 8,283 ⟶ 8,274:
 
# concat all sorted partitions into a list and return
|$less, |%partitionsprt{Same}, |$more;
}
</syntaxhighlight>
Line 8,290 ⟶ 8,281:
 
<syntaxhighlight lang="raku" line>
say "x" x 10 ~ " Testing " ~ "x" x 10;
use Test;
my @implementationsfunctions-under-test = &quicksort, &seven-line-quicksort-parallel-naive, &quicksort-parallel;▼
my @testcases =
() => (),
<a>.List => <a>.List,
<a a> => <a a>,
<("b", "a", b>3) => <(3, "a", "b>"),
<b a> => <a b>,
<h b a c d f e g> => <a b c d e f g h>,
(2, 3, 1, 4, 5) => (1, 2, 3, 4, 5),
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort
;
 
▲my @implementations = &quicksort, &seven-line-quicksort-parallel, &quicksort-parallel;
plan @testcases.elems * @implementationsfunctions-under-test.elems;
for @implementationsfunctions-under-test -> &fun {
say &fun.name;
is-deeply &fun(.key), .value, .key ~ " => " ~ .value for @testcases;
Line 8,310 ⟶ 8,301:
</syntaxhighlight>
<pre>
xxxxxxxxxx Testing xxxxxxxxxx
1..2418
quicksort
ok 1 - =>
ok 2 - a => a
ok 3 - a a => a a
ok 4 - b a b3 => 3 a b
ok 5 - h b a c d f e g => a b c d e f g h
ok 6 - h b a c🎮 d3 fz e4 g🐧 => a3 b4 c d ea fz g🎮 h🐧
seven-line-quicksort-parallel-naive▼
ok 7 - 2 3 1 4 5 => 1 2 3 4 5
ok 87 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
ok 138 - b a => a b▼
▲seven-line-quicksort-parallel
ok 9 - a a => a a
ok 10 - b a 3 => 3 a b
ok 11 - ah b a c d f e g => a ab c d e f g h
ok 12 - a b🎮 3 z 4 🐧 => 3 4 a bz 🎮 🐧
▲ok 13 - b a => a b
ok 14 - h b a c d f e g => a b c d e f g h
ok 15 - 2 3 1 4 5 => 1 2 3 4 5
ok 16 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
quicksort-parallel
ok 1713 - =>
ok 1814 - a => a
ok 1915 - a a => a a
ok 2016 - b a b3 => 3 a b
ok 2117 - h b a c d f e g => a b c d e f g h
ok 2218 - h b a c🎮 d3 fz e4 g🐧 => a3 b4 ca dz e🎮 f g h🐧</pre>
ok 23 - 2 3 1 4 5 => 1 2 3 4 5
ok 24 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
</pre>▼
 
and some benchmarking
 
<syntaxhighlight lang="raku" line>
say "x" x 11 ~ " Benchmarking " ~ "x" x 11;
my $elem-length = 8;
use Benchmark;
my @large of Str = ('a'..'z').roll($elem-length).join xx 10 * $worker * $BATCH-SIZE;▼
my $runs = 5;
my $elems = 10 * Kernel.cpu-cores * 2**10;
▲my @largeunsorted of Str = ('a'..'z').roll($elem-length8).join xx 10 * $worker * $BATCH-SIZEelems;
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";
say "Benchmarking by sorting {@large.elems} strings of size $elem-length - using batches of $BATCH-SIZE strings and $worker workers.";
 
my @benchmark = gather for @implementations -> &fun {
my %results = timethese $runs, {
&fun(@large);
▲multi single-thread => { quicksort(@unsorted) {},
take (&fun.name => now - ENTER now);
parallel-naive => { quicksort-parallel-naive(@unsorted) },
}▼
▲multi seven parallel-linetiny-batch => { quicksort-parallel(@unsorted, $t-batch) {},
say @benchmark;
parallel-small-batch => { quicksort-parallel(@unsorted, $s-batch) },
</syntaxhighlight>▼
parallel-medium-batch => { quicksort-parallel(@unsorted, $m-batch) },
parallel-large-batch => { quicksort-parallel(@unsorted, $l-batch) },
▲};
 
for %results.kv -> $name, ($start, $end, $diff, $avg) {
say "$name avg $avg secs"
▲}</syntaxhighlight>
<pre>
xxxxxxxxxxx Benchmarking xxxxxxxxxxx
Benchmarking by sorting 40960 strings of size 8 - using batches of 1024 strings and 4 workers.
elements: 40960, runs: 5, cpu-cores: 4, large/medium/small/tiny-batch: 8192/2048/512/128
[quicksort => 6.075300648 seven-line-quicksort-parallel => 4.889432647 quicksort-parallel => 1.147604289]</pre>
single-thread avg 6 secs
parallel-naive avg 5.6 secs
parallel-tiny-batch avg 2.8 secs
parallel-small-batch avg 2.4 secs
parallel-medium-batch avg 2.8 secs
parallel-large-batch avg 3.4 secs
▲</pre>
 
=={{header|Red}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/348462"