Je suis confronté à un problème d'écriture Quicksort à Erlang. Ce que je fais, c'est que je reproche deux processus puis je bloque le processus actuel jusqu'à ce que je reçois la réponse des sous-tableaux de gauche et de droite. Obtenir ces deux réponses, j'envoie un message à son parent lui donnant la liste calculée. Mais je reçois une erreur de Gettingting Undef dans les deux sous-processus.
Voici le code. appelé comme: parent! {auto (), Lone ++ [h] ++ LTWO}
3 Réponses :
Le code lui-même n'est pas le problème. Le tri rapide fonctionne bien. La raison, probablement, pourquoi vous obtenez un NEDF dans les sous-processus est due au fait que la fonction rapide / 2 n'est pas exportée du tout. Lorsque vous appelez Spawn_Link avec le module et la fonction, la fonction doit être exportée.
Vous pouvez résoudre ce problème par soit ajouté P>
Self = self()
Merci, cela fonctionne en exportant rapide / 2. Puis-je demander pourquoi j'ai besoin d'exporter rapide / 2?
Parce que si ce n'est pas exporté, il ne peut être appelé qu'à partir des fonctions qui sont originaires de votre module. Pensez-y comme une fonction privée. Ensuite, lorsque vous appelez Erlang: SPAWN_LINK / 3 Il s'agit d'un différents modules essayant efficacement d'appeler principal: rapide / 2. Mais cela ne peut pas parce que le principal: rapide / 2 est une fonction privée et aucun autre module ne le sait.
Le code ci-dessus fonctionne bien en exportant une fonction rapide / 2.
Plus tard sur I, j'ai comparé la durée d'exécution de la maigre QuickSort vs le QuickSort Abatched. Le QuickSort ACTIVELABLE prend n'importe où entre 15 secondec à 32 secondes pour trier une liste de 1 million de nombres aléatoires dans la plage (1 1000000). P>
Le QuickSort Autorisé non développé est (Code ci-dessous): P>
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 ]).
Eh bien, si vous n'avez qu'un seul noyau, vous n'avez aucune possibilité de travailler en parallèle, alors je ne m'attendais pas à un avantage. D'autre part, tandis que les processus peuvent être peu coûteux dans Erlang, ils ne sont pas libres et les envois de messages et les spawns nécessitent une copie complète de la liste. Pensez également à ce qui se passe à proximité de l'affaire de base, vous appartenez beaucoup de processus à renvoyer la liste vide. Il serait peut-être intéressant d'écrire une version qui reproche aux processus pour les premières étapes, puis revenait à la version non créée. (Si vous avez une machine multicœur pour l'essayer.)
Sur mon ordinateur portable à double noyau, il est encore légèrement plus lent, même lorsque j'apparais que deux processus seulement.
J'ai été testé sur le double noyau, en fait, j'ai limité le frai lorsque la taille de la matrice atteint moins de 100 ans. (Taille totale de la liste étant 1 million), je mets environ 2,4 secondes avec une version engendrée et environ 3,2 secondes avec une version non cuue.
N'oubliez pas que pour chaque processus engagé Erlang copie la liste à qui traite son propre tas. Avec un calcul approximatif log2len * len Les éléments de liste sont copiés au total, ce qui est assez élevé pour une liste d'un million d'entiers.
Listes: Trier / 1 Pour 1 million prend environ 800 ms. Listes: Trier / 1 Est-ce que la fusion est la tridélisation écrite de manière intelligente. Si vous considérez que cette liste peut être triée par l'algorithme avec le pire cas O (n * log2n) (c'est-à-dire une sorte de fusion) que même une copie de tous les membres de la liste entre les processus peut compter et cela fait. Vous devez avoir beaucoup de noyaux pour faire une version parallèle plus rapidement et la syntoniser soigneusement.
J'ai fabriqué une légère modification du code pour l'empêcher de se reproduire de nombreux processus. Lorsqu'il atteint un certain niveau dans l'arborescence, il passe à séquentielle.
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).
Question: Je lis actuellement le livre de Joe Armstrong, où il affiche un algorithme Quicksort similaire (non parallèle) avec le commentaire suivant: "Ce code est affiché pour son élégance plutôt que son efficacité. Utiliser ++ de cette manière n'est généralement pas généralement considéré comme une bonne pratique de programmation. " Des commentaires à ce sujet de développeurs d'erlang plus expérimentés en ce qui concerne la solution de Pranjal?
++ sont tous corrects. Le compilateur l'optimisera de toute façon. Voici le lien erlang.org/doc/efficient_guide/myths.html#ID2259083 < / a>
Merci, c'était un lien intéressant!