Sorting algorithms/Quicksort: Difference between revisions
Content added Content deleted
imported>Rcmlz |
imported>Rcmlz |
||
Line 8,241: | Line 8,241: | ||
<syntaxhighlight lang="raku" line> |
<syntaxhighlight lang="raku" line> |
||
constant $BATCH-SIZE = 2**10; |
|||
my atomicint $worker = $*KERNEL.cpu-cores; |
|||
#| Recursive, parallel, quicksort implementation |
#| Recursive, parallel, quicksort implementation |
||
proto quicksort-parallel(| --> Positional) {*} |
|||
multi quicksort-parallel(@unsorted where @unsorted.elems < 2) { @unsorted } |
multi quicksort-parallel(@unsorted where @unsorted.elems < 2) { @unsorted } |
||
multi quicksort-parallel(@unsorted) { |
multi quicksort-parallel(@unsorted) { |
||
my %class{Order} is default([]); |
|||
my $pivot = @unsorted.pick; |
my $pivot = @unsorted.pick; |
||
⚫ | |||
# separate unsorted input into Order Less, Same and More compared to $pivot |
|||
⚫ | |||
⚫ | |||
my $more = samewith(%class{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; |
|||
} |
} |
||
#=« Implementation Notes: |
|||
⚫ | |||
* recursion on Less partition can create a large number of new threads |
|||
* samewith() refactors out the actual name of the routine. |
|||
» |
|||
</syntaxhighlight> |
</syntaxhighlight> |
||
Line 8,266: | Line 8,281: | ||
<a>.List => <a>.List, |
<a>.List => <a>.List, |
||
<a a> => <a a>, |
<a a> => <a a>, |
||
<a b> => <a b>, |
|||
<b a> => <a b>, |
<b a> => <a b>, |
||
<h b a c d f e g> => <a b c d e f g h>, |
<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), |
(2, 3, 1, 4, 5) => (1, 2, 3, 4, 5), |
||
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort |
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort |
||
; |
; |
||
my @implementations = &quicksort, &quicksort-parallel; |
|||
plan @testcases.elems * @implementations.elems; |
|||
for @implementations -> &fun { |
|||
say &fun.name; |
say &fun.name; |
||
is-deeply &fun(.key), .value, .key ~ " => " ~ .value for @testcases; |
|||
} |
} |
||
done-testing; |
|||
</syntaxhighlight> |
</syntaxhighlight> |
||
<pre> |
<pre> |
||
1..16 |
|||
quicksort |
quicksort |
||
ok 1 - => |
ok 1 - => |
||
Line 8,295: | Line 8,315: | ||
ok 15 - 2 3 1 4 5 => 1 2 3 4 5 |
ok 15 - 2 3 1 4 5 => 1 2 3 4 5 |
||
ok 16 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧 |
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> |
</pre> |
||