Sorting algorithms/Quicksort: Difference between revisions

Line 8,239:

The partitions can be sorted in parallel.

⚫

#| 7-Line, recursive, parallel, quicksort implementation

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.

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:

Line 8,287:

</syntaxhighlight>

Let's run some tests

Let's run some tests.

Line 8,288:

Line 8,301:

<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort

;

my @implementations = &quicksort, &quicksort-parallel;

my @implementations = &quicksort, &seven-line-quicksort-parallel, &quicksort-parallel;

plan @testcases.elems * @implementations.elems;

for @implementations -> &fun {

Line 8,297:

Line 8,310:

</syntaxhighlight>

<pre>

1..16

1..24

quicksort

ok 1 - =>

ok 2 - a => a

ok 3 - a a => a a

Line 8,307:

Line 8,320:

ok 7 - 2 3 1 4 5 => 1 2 3 4 5

ok 8 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧

quicksort-parallel

seven-line-quicksort-parallel

ok 9 - =>

ok 10 - a => a

ok 11 - a a => a a

Line 8,316:

Line 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:

Line 8,343:

## run benchmark on the two versions

my $elem-length = 8;

my @large of Str = ('a'..'z').roll($elem-length).join xx 10 * $worker * $BATCH-SIZE;

Line 8,334:

Line 8,355:

<pre>

Benchmarking by sorting 40960 strings of size 8 - using batches of 1024 strings and 4 workers.

[quicksort => 4.~~691771502~~ quicksort-parallel => 1.~~296705289~~]

[quicksort => 6.075300648 seven-line-quicksort-parallel => 4.889432647 quicksort-parallel => 1.147604289]</pre>

</pre>

=={{header|Red}}==