Проблема с параллельной быстрой сортировкой в ​​эрланге

Question

У меня проблема с написанием быстрой сортировки на эрланге.Что я делаю, так это то, что я порождаю два процесса и затем блокирую текущий процесс, пока не получу ответ от левого и правого подмассивов.Получив оба эти ответа, я отправляю сообщение его родителю, давая ему вычисляемый список.Parent ! {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

Приведенный выше код работает нормально, экспортируя функцию quick / 2.

Позже я сравнил время выполнения порожденной быстрой сортировки с неявленной быстрой сортировкой.Порожденная быстрая сортировка занимает от 15 секунд до 32 секунд, чтобы отсортировать список из 1 миллиона случайных чисел в диапазоне (1 1000000).

Невозможная быстрая сортировка (код ниже):

 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 ГГц (одноядерный) и 512 МБ ОЗУ.

Есть ли объяснение тому, что порожденная быстрая сортировка работает хуже, чем порожденная?

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).