Problema con quicksort paralelo en erlang

Tengo problemas para escribir quicksort en erlang. Lo que estoy haciendo es que estoy generando dos procesos y luego bloqueando el proceso actual hasta que obtengo la respuesta de las sub-matrices izquierda y derecha. Obteniendo ambas respuestas, envío un mensaje a su padre dándole la lista calculada. Parent ! {self(), Lone ++ [H] ++ Ltwo}Problema con quicksort paralelo en erlang

Pero estoy recibiendo el error de obtener undef en ambos subprocesos. Aquí está el código.

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

llamado como:

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

Fuente

2010-09-04 pranjal

Pregunta: Actualmente estoy leyendo el libro de Joe Armstrong, donde se muestra una similar (no en paralelo, aunque) algoritmo de ordenación rápida con el siguiente comentario: ". Este código se muestra por su elegancia en lugar de su eficiencia Utilizando ++ de esta manera, generalmente no se considera una buena práctica de programación ". ¿Algún comentario sobre eso de desarrolladores de Erlang más experimentados con respecto a la solución de pranjal? –

++ están bien. El compilador lo optimizará de todos modos. Aquí está el enlace http://www.erlang.org/doc/efficiency_guide/myths.html#id2259083 – user425720

¡Gracias, ese fue un enlace interesante! –

El código en sí no es el problema. El tipo rápido funciona bien. La razón, probablemente, por la que obtiene undef en los subprocesos se debe al hecho de que la función quick/2 no se exporta en absoluto. Cuando llama a spawn_link con el módulo y la función, la función necesita ser exportada.

Puede solucionar este problema mediante cualquiera añade

-export([quick/2]).

o cambiando el spawn_links a algo así como

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

Aunque si lo haces de esta última manera, usted tendrá que crear una variable

Self = self()

Antes de hacer las llamadas o de lo contrario no volverá al proceso correcto.

Fuente

2010-09-04 19:27:15 Olives

Gracias, funciona exportando quick/2.¿Puedo preguntar por qué necesito exportar quick/2? – pranjal

Porque si no se exporta, solo se puede invocar desde funciones nativas de su módulo. Piense en ello como una función privada. Luego cuando llamas a erlang: spawn_link/3 es un módulo diferente tratando de llamar a main: quick/2. Pero no puede porque main: quick/2 es una función privada y ningún otro módulo lo sabe. – Olives

El código anterior funciona bien al exportar la función quick/2.

Más tarde comparé el tiempo de ejecución del quicksort generado con el quicksort no generado. El quicksort generado toma de 15 segundos a 32 segundos para ordenar una lista de 1 millón de números aleatorios en el rango (1,1000000).

La ordenación rápida es unspawned (código de abajo):

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

toma en cualquier lugar entre 5 segundos y 8sec para ordenar misma lista de un millón de números aleatorios.

Estoy probando el código en mi viejo Thinkpad, procesador de 1.7 Ghz (núcleo único) y 512 Mb de RAM.

¿Alguna explicación para que el quicksort generado funcione peor que el no creado?

Fuente

2010-09-05 08:25:24 pranjal

Bueno, si solo tiene un núcleo único, entonces no tiene ninguna capacidad para trabajar en paralelo, por lo que no esperaría ningún beneficio. Por otro lado, si bien los procesos pueden ser baratos en Erlang, no son gratuitos y los envíos y generación de mensajes requieren una copia completa de la lista. También piense en lo que sucede cerca del caso base, genera muchos procesos para devolver la lista vacía. Puede ser interesante escribir una versión que engendre procesos para los primeros pasos y luego vuelva a la versión no generada. (Si tiene una máquina multinúcleo para probarlo) – cthulahoops

En mi computadora portátil de doble núcleo todavía es un poco más lento, incluso cuando genero solo dos procesos. – cthulahoops

Probé en doble núcleo, de hecho limité el desove cuando el tamaño de la matriz llega a menos de 100. (El tamaño total de la lista es de 1 millón), obtengo alrededor de 2.4 segundos con la versión engendrada y alrededor de 3.2 segundos con la versión no inventada. – pranjal

Hice una pequeña modificación del código para evitar que se genere en muchos procesos. Cuando alcanza un cierto nivel en el árbol, cambia a secuencia.

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

Fuente

2013-01-05 15:12:30 patwotrik

Problema con quicksort paralelo en erlang

Respuesta

Cuestiones relacionadas