peval(fun pqsort/1, Left) ++ [Pivot] ++ peval(fun pqsort/1, Right).

I was hoping Erlang would be clever enough to execute the two functions in parallel, but that's a fairly unreasonable (and completely incorrect) assumption!

But how to fix it? There is a parallel implementation of the map function in Joe's book, and Montsamu has a variation of it on his blog:

-module(plists).

-export([pmap/2]).

pmap(F, L) ->

S = self(),

Pids = lists:map(fun(I) -> spawn(fun() -> pmap_f(S, F, I) end) end, L),

pmap_gather(Pids).

pmap_gather([H|T]) ->

receive

{H, Ret} -> [Ret|pmap_gather(T)]

end;

pmap_gather([]) ->

[].

pmap_f(Parent, F, I) ->

Parent ! {self(), (catch F(I))}.

The pmap_gather function is the interesting one. It will traverse the list of Pids, and wait for each to send back its result. Using pmap, we update pqsort as follows:

pqsort([]) -> [];

pqsort([Pivot]) -> [Pivot];

pqsort([Pivot|Rest]) ->

io:format("+", []),

Left = [X || X <- Rest, X < Pivot],

Right = [Y || Y <- Rest, Y >= Pivot],

[SortedLeft, SortedRight] = plists:pmap(fun pqsort/1, [Left, Right]),

io:format("-", []),

SortedLeft ++ [Pivot] ++ SortedRight.

And with a perfectly unbalanced (for quicksort) list to sort, we expect 1 process, then 3 as the first spawns 2 new ones, then down again to zero:

(emacs@21ccw.blogspot.com)47> pqsort:pqsort([4,2,1,3,6,5,7]).

+++---[1,2,3,4,5,6,7]

For the same example we had last time, sorting 100 random numbers, the number of concurrent process graph during execution looks like this:

Much better!

## 1 comment:

Which tool you create this graph? Percept?

Post a Comment