Anonymous user
Sorting algorithms/Quicksort: Difference between revisions
→{{header|Raku}}
imported>Rcmlz |
imported>Rcmlz |
||
Line 8,241:
<syntaxhighlight lang="raku" line>
constant $BATCH-SIZE = 2**10;
my atomicint $worker = $*KERNEL.cpu-cores;
#| Recursive, parallel, quicksort implementation
proto quicksort-parallel(| --> Positional) {*}
multi quicksort-parallel(@unsorted where @unsorted.elems < 2) { @unsorted }
multi quicksort-parallel(@unsorted) {
my $pivot = @unsorted.pick;
%class = @unsorted.classify( * cmp $pivot );▼
# separate unsorted input into Order Less, Same and More compared to $pivot
my $less = start { samewith(%class{Less}) };▼
await $less andthen |$less.result, |%class{Same}, |$more▼
# atomically decide if we sort the Less partition on a new worker thread
my $less = ⚛$worker > 0 &&
%partitions{Less}.elems > $BATCH-SIZE
?? start {
ENTER $worker⚛--;
LEAVE $worker⚛++;
samewith(%partitions{Less})
}
!! samewith(%partitions{Less});
# if we went parallel, we need to await the result
# concat all sorted partitions into a list and return
|$less, |%partitions{Same}, |$more;
}
▲* uses the current thread for More partition
</syntaxhighlight>
Line 8,266 ⟶ 8,281:
<a>.List => <a>.List,
<a a> => <a a>,
<a b> => <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
;
plan @testcases.elems * @implementations.elems;
for @implementations -> &fun {
say &fun.name;
}
done-testing;
</syntaxhighlight>
<pre>
1..16
quicksort
ok 1 - =>
Line 8,295 ⟶ 8,315:
ok 15 - 2 3 1 4 5 => 1 2 3 4 5
ok 16 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
</pre>
and some benchmarking
<syntaxhighlight lang="raku" line>
my $elem-length = 8;
my @large of Str = ('a'..'z').roll($elem-length).join xx 10 * $worker * $BATCH-SIZE;
say "Benchmarking by sorting {@large.elems} strings of size $elem-length - using batches of $BATCH-SIZE strings and $worker workers.";
my @becnhmark = gather
for @implementations -> &fun {
&fun(@large);
take (&fun.name => now - ENTER now);
}
say @becnhmark;
</syntaxhighlight>
<pre>
Benchmarking by sorting 40960 strings of size 8 - using batches of 1024 strings and 4 workers.
[quicksort => 5.271144286 quicksort-parallel => 2.645456851]
</pre>
| |||