Anonymous user
Sorting algorithms/Quicksort: Difference between revisions
→{{header|Raku}}
imported>Rcmlz |
imported>Rcmlz |
||
Line 8,239:
The partitions can be sorted in parallel.
<syntaxhighlight lang="raku" line>
multi seven-line-quicksort-parallel(@unsorted where @unsorted.elems < 2) { @unsorted }
multi seven-line-quicksort-parallel(@unsorted) {
my $pivot = @unsorted.pick;
my %partitions{Order} is default([]) = @unsorted.classify( * cmp $pivot );
my Promise $less = start { samewith(%partitions{Less}) }
my $more = samewith(%partitions{More});
await $less andthen |$less.result, |%partitions{Same}, |$more;
}
</syntaxhighlight>
Let's tune the parallel execution by limiting the number of worker threads and introducing a minimum batch size.
<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 }
Line 8,274 ⟶ 8,287:
</syntaxhighlight>
Let's run some tests.
<syntaxhighlight lang="raku" line>
Line 8,288 ⟶ 8,301:
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort
;
my @implementations = &quicksort, &seven-line-quicksort-parallel, &quicksort-parallel;
plan @testcases.elems * @implementations.elems;
for @implementations -> &fun {
Line 8,297 ⟶ 8,310:
</syntaxhighlight>
<pre>
1..
quicksort
ok 1 - =>
ok 2 - a => a
ok 3 - a a => a a
Line 8,307 ⟶ 8,320:
ok 7 - 2 3 1 4 5 => 1 2 3 4 5
ok 8 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
seven-line-quicksort-parallel
ok 9 - =>
ok 10 - a => a
ok 11 - a a => a a
Line 8,316 ⟶ 8,329:
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 17 - =>
ok 18 - a => a
ok 19 - a a => a a
ok 20 - a b => a b
ok 21 - b a => a b
ok 22 - h b a c d f e g => a b c d e f g h
ok 23 - 2 3 1 4 5 => 1 2 3 4 5
ok 24 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
</pre>
Line 8,321 ⟶ 8,343:
<syntaxhighlight lang="raku" line>
my $elem-length = 8;
my @large of Str = ('a'..'z').roll($elem-length).join xx 10 * $worker * $BATCH-SIZE;
Line 8,334 ⟶ 8,355:
<pre>
Benchmarking by sorting 40960 strings of size 8 - using batches of 1024 strings and 4 workers.
[quicksort => 6.075300648 seven-line-quicksort-parallel => 4.
=={{header|Red}}==
| |||