Problem z równoległym quicksort w erlang

Mam problem z pisaniem quicksort w erlangu. Co robię, uruchamiam dwa procesy, a następnie blokuję bieżący proces, dopóki nie otrzymam odpowiedzi od lewej i prawej pod-macierzy. Otrzymując obie te odpowiedzi, wysyłam wiadomość do jej rodzica, przekazując mu wyliczoną listę. Parent ! {self(), Lone ++ [H] ++ Ltwo}Problem z równoległym quicksort w erlang

Ale dostaję błąd przyjmowania undef w obu podprocesach. Oto kod.

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

nazywa się:

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

Źródło

2010-09-04 pranjal

Pytanie: Jestem obecnie czyta książkę Joe Armstrong, gdzie pokazuje podobny (choć nie równolegle) algorytm quicksort z następującym komentarzem: „. Ten kod jest pokazany na swoją elegancję niż jego efektywności Korzystanie ++ w ten sposób nie uważa się powszechnie za dobrą praktykę programistyczną. " Jakieś komentarze od bardziej doświadczonych deweloperów Erlang w odniesieniu do rozwiązania pranjal? –

++ są w porządku. Kompilator i tak to zoptymalizuje. Oto link http://www.erlang.org/doc/efficiency_guide/myths.html#id2259083 – user425720

Dziękuję, to był interesujący link! –

Sam kod nie jest problemem. Szybki sortowanie działa dobrze. Powodem, dla którego prawdopodobnie otrzymujesz undef w podprocesach, jest fakt, że funkcja quick/2 nie jest w ogóle eksportowana. Kiedy wywołujesz spawn_link z modułem i funkcją, funkcja musi zostać wyeksportowana.

Można to naprawić albo dodany

-export([quick/2]).

lub przez zmianę spawn_links coś jak

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

ale jeśli robisz to ten drugi sposób, trzeba utworzyć zmienną

Self = self()

Przed wykonaniem połączenia lub nie będzie powrotu do prawidłowego procesu.

Źródło

2010-09-04 19:27:15 Olives

Dzięki, działa poprzez eksportowanie szybkie/2.Czy mogę zapytać, dlaczego muszę eksportować szybkie/2? – pranjal

Ponieważ jeśli nie jest eksportowany, to można go wywołać tylko z funkcji, które są natywne dla twojego modułu. Pomyśl o tym jako o prywatnej funkcji. Następnie, gdy wywołujesz erlang: spawn_link/3, to inne moduły efektywnie próbują wywołać main: quick/2. Ale nie może, ponieważ main: quick/2 jest prywatną funkcją i żaden inny moduł o tym nie wie. – Olives

Powyższy kod działa poprawnie, eksportując funkcję szybkiego/2.

Później porównałem czas działania zrekrutowanego quicksortu z nieopisanym quicksortem. Zrodzony quicksort zajmuje od 15 sekund do 32 sekund, aby posortować listę 1 miliona liczb losowych w zakresie (1 100 000).

unspawned quicksort jest (kod poniżej):

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

trwa gdziekolwiek pomiędzy 5s i 8SEC uporządkować tę samą listę milion liczb losowych.

Testuję kod na moim starym Thinkpadzie, procesorze 1.7 Ghz (pojedynczy rdzeń) i 512 Mb pamięci RAM.

Jakieś wytłumaczenie dla zrodzonego quicksortu, by wykonać gorzej niż nieodkryty?

Źródło

2010-09-05 08:25:24 pranjal

Cóż, jeśli masz tylko jeden rdzeń, to nie masz żadnej możliwości równoległego działania, więc nie spodziewałbym się żadnej korzyści. Z drugiej strony, podczas gdy procesy mogą być tanie w Erlang, nie są one darmowe, a wysyłanie wiadomości i spawnowanie wymaga pełnej kopii listy. Pomyśl także o tym, co dzieje się w pobliżu bazy, odradzasz wiele procesów, aby odesłać pustą listę. Interesujące może być napisanie wersji, która spawnuje procesy przez pierwsze kilka kroków, a następnie powraca do nieodkrytej wersji. (Jeśli masz maszynę wielordzeniową, aby ją wypróbować.) – cthulahoops

Na moim dwurdzeniowym laptopie wciąż jest trochę wolniej, nawet gdy spawnuję tylko dwa procesy. – cthulahoops

Przetestowałem na dual core, w rzeczywistości ograniczyłem spawning, gdy rozmiar tablicy sięga poniżej 100. (całkowita wielkość listy to 1 milion), otrzymuję około 2,4 sekundy z wersją spawn i około 3,2 sekundy z nieodkrytą wersją. – pranjal

Wprowadziłem niewielką modyfikację kodu, aby zapobiec jego spawnowaniu do wielu procesów. Kiedy osiągnie pewien poziom w drzewie, przełącza się na sekwencję.

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

Źródło

2013-01-05 15:12:30 patwotrik

Problem z równoległym quicksort w erlang

Odpowiedz

Powiązane problemy