Problema con quicksort parallelo in erlang

Ho problemi con la scrittura quicksort in erlang. Quello che sto facendo è che sto generando due processi e poi bloccando il processo corrente fino a ottenere la risposta da entrambi i sub-array sinistro e destro. Ottenendo entrambe queste risposte mando un messaggio al suo genitore dandogli la lista calcolata. Parent ! {self(), Lone ++ [H] ++ Ltwo}Problema con quicksort parallelo in erlang

Ma sto ottenendo errore di ottenere undef in entrambi i sottoprocessi. Ecco il codice.

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

chiamato come:

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

fonte

2010-09-04 pranjal

Domanda: Attualmente sto leggendo il libro di Joe Armstrong, dove si mostra una simile (non parallelo però) algoritmo quicksort con il seguente commento: ". Questo codice viene mostrato per la sua eleganza, piuttosto che la sua efficienza Utilizzando ++ in questo modo non è generalmente considerata una buona pratica di programmazione. " Qualche commento a riguardo degli sviluppatori di Erlang più esperti in merito alla soluzione di pranjal? –

++ vanno bene. Il compilatore lo ottimizzerà comunque. Ecco il link http://www.erlang.org/doc/efficiency_guide/myths.html#id2259083 – user425720

Grazie, è stato un link interessante! –

Il codice stesso non è il problema. L'ordinamento rapido funziona bene. Il motivo, probabilmente, del perché si sta ottenendo undef nei sottoprocessi è dovuto al fatto che la funzione quick/2 non viene affatto esportata. Quando chiami spawn_link con il modulo e la funzione, la funzione deve essere esportata.

È possibile risolvere questo problema sia aggiunto

-export([quick/2]).

o cambiando la spawn_links a qualcosa di simile

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

Anche se lo fate quest'ultimo proposito, è necessario creare una variabile

Self = self()

Prima di effettuare le chiamate, altrimenti non si ritorna alla procedura corretta.

fonte

2010-09-04 19:27:15 Olives

Grazie, funziona esportando rapidamente/2.Posso chiederti perché ho bisogno di esportare velocemente/2? – pranjal

Perché se non viene esportato, può essere chiamato solo da funzioni native del modulo. Pensala come una funzione privata. Quindi quando chiami erlang: spawn_link/3 è un modulo differente che tenta in modo efficace di chiamare main: quick/2. Ma non può perché main: quick/2 è una funzione privata e nessun altro modulo lo sa. – Olives

Il codice sopra funziona correttamente esportando la funzione quick/2.

In seguito ho confrontato il tempo di esecuzione del quicksort generato vs il quicksort non sparso. Il quicksort generato richiede da 15 a 32 secondi per ordinare un elenco di 1 milione di numeri casuali nell'intervallo (1,1000000).

Il quicksort unspawned è (codice qui sotto):

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

prende ovunque tra 5sec e 8sec per ordinare stesso elenco di un milione di numeri casuali.

Sto testando il codice sul mio vecchio Thinkpad, processore da 1.7 Ghz (single core) e 512 Mb RAM.

Qualche spiegazione per il quicksort generato in modo che abbia un rendimento inferiore a quello non depurato?

fonte

2010-09-05 08:25:24 pranjal

Beh, se hai un solo core non hai alcuna possibilità di lavorare in parallelo, quindi non mi aspetto alcun vantaggio. D'altra parte, mentre i processi possono essere economici in Erlang, non sono gratuiti e le mandate e gli spawn dei messaggi richiedono una copia completa dell'elenco. Pensa anche a cosa succede vicino al caso base, generi molti processi per rimandare la lista vuota. Potrebbe essere interessante scrivere una versione che genera i processi per il primo paio di passaggi e quindi ricade nella versione non ancora pronta. (Se si dispone di una macchina multicore per provarlo.) – cthulahoops

Sul mio computer portatile dual core è ancora leggermente più lento anche quando creo solo due processi. – cthulahoops

Ho provato su dual core, infatti ho limitato lo spawning quando le dimensioni dell'array raggiungono meno di 100. (la dimensione totale dell'elenco è di 1 milione), ottengo circa 2,4 secondi con la versione generata e circa 3,2 secondi con la versione non nascosta. – pranjal

Ho apportato una leggera modifica del codice per impedirne la generazione in molti processi. Quando raggiunge un certo livello nell'albero passa a sequenziale.

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

fonte

2013-01-05 15:12:30 patwotrik

Problema con quicksort parallelo in erlang

risposta

Problemi correlati