erlang中并行快速排序的问题

Question

我在 erlang 中编写快速排序时遇到问题。我正在做的是生成两个进程，然后阻止当前进程，直到我得到左右子数组的响应。得到这两个响应后，我向其父级发送一条消息，为其提供计算列表。 家长！ {self(), Lone ++ [H] ++ Ltwo}

但是我在两个子进程中都遇到了获取 undef 的错误。 这是代码。

  quick(Parent, []) -> Parent ! {self(), []};
  quick(Parent, [H | T]) ->
      Pone = spawn_link(main, quick, [ self(), [ X || X <- T, H >= X ] ]) ,
      Ptwo = spawn_link(main, quick, [ self(), [ Y || Y <- T, H < Y ] ]) ,
      receive
          {Pone, Lone} ->
              receive
                  {Ptwo, Ltwo} -> Parent ! {self(), Lone ++ [H] ++ Ltwo}
              end;
          {Ptwo, Ltwo} ->
              receive
                  {Pone, Lone} -> Parent ! {self(), Lone ++ [H] ++ Ltwo}
              end
      end.

  sortquick(List) ->
      quick(self(), List).

称为：

main:sortquick([12,4,7,22,25]).

Answer 1

代码本身不是问题。快速排序效果很好。您在子进程中得到 undef 的原因可能是由于函数 Quick/2 根本没有导出。当您使用模块和函数调用spawn_link时，需要导出该函数。

您可以通过添加

-export([quick/2]).

或将spawn_links更改为类似的内容

spawn_link(fun() -> quick(Self, [Y || Y <- T, H < Y]) end

来解决此问题，但如果您采用后一种方式，则需要

Self = self()

在进行调用之前创建一个变量，否则它将不会返回到正确的进程。

Answer 2

上面的代码通过导出 fast/2 函数可以正常工作。

后来我比较了生成的快速排序和未生成的快速排序的运行时间。
生成的快速排序需要 15 秒到 32 秒的时间来对范围 (1,1000000) 内的 100 万个随机数的列表进行排序。

未生成的快速排序是（下面的代码）：

 55 quicksort([]) -> [];
 56 quicksort([H]) -> [H];
 57 quicksort([H | T]) ->
 58     [Headnew | Tailnew] = [H | T],
 59     quicksort([ X || X <- Tailnew, Headnew >= X ]) ++ [Headnew] ++ quicksort([ Y || Y <- Tailnew, Headnew < Y ]).

需要 5 秒到 8 秒之间的任何时间来对一百万个随机数的相同列表进行排序。

我正在我的旧 Thinkpad、1.7 Ghz 处理器（单核）和 512 Mb RAM 上测试代码。

有什么解释可以解释生成的快速排序比未生成的快速排序性能差吗？

Answer 3

我对代码进行了轻微修改，以防止它生成到许多进程。当它达到树中的某个级别时，它会切换到顺序。

qsort([]) ->
    [];
qsort([H | T]) -> 
    qsort([ X || X <- T, X < H ]) ++ [H] ++ qsort([ X || X <- T, X >= H ]).

quick(Parent, [], _) -> Parent ! {self(), []};
quick(Parent, [H | T], C) when C > 0->
   Pone = spawn_link(test, quick, [ self(), [ X || X <- T, H >= X ], C-1 ]) ,
   Ptwo = spawn_link(test, quick, [ self(), [ Y || Y <- T, H < Y ], C-1 ]) ,
   receive
       {Pone, Lone} ->
              receive
                  {Ptwo, Ltwo} -> Parent ! {self(), Lone ++ [H] ++ Ltwo}
              end;
          {Ptwo, Ltwo} ->
              receive
                  {Pone, Lone} -> Parent ! {self(), Lone ++ [H] ++ Ltwo}
              end
      end;
quick(Parent, [H | T], _) -> 
    Parent ! {self(), qsort([ X || X <- T, X < H ]) ++ [H] ++ qsort([ X || X <- T, X >= H ])}.

sortquick(List) ->
    quick(self(), List, 4).