Vấn đề với quicksort song song trong erlang

Question

Tôi đang gặp vấn đề với viết quicksort trong erlang. Những gì tôi đang làm là tôi đang sinh ra hai quy trình và sau đó chặn quá trình hiện tại cho đến khi tôi nhận được phản hồi từ cả hai mảng phụ bên trái và bên phải. Nhận được cả hai câu trả lời này, tôi gửi một tin nhắn cho cha mẹ của nó cho nó danh sách tính toán. Parent ! {self(), Lone ++ [H] ++ Ltwo}

Nhưng tôi đang gặp lỗi khi vô hiệu hóa việc hoàn tác trong cả hai quy trình phụ. Đây là mã.

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

gọi là:

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

Answer 1

Mã bản thân không phải là vấn đề. Sắp xếp nhanh chóng hoạt động tốt. Lý do, có lẽ, tại sao bạn đang nhận được một undef trong các quy trình phụ là do thực tế là các chức năng quick/2 không được xuất khẩu ở tất cả. Khi bạn gọi spawn_link với module và hàm, hàm cần được xuất khẩu.

Bạn có thể sửa lỗi này bằng một trong hai thêm

-export([quick/2]). 

Hoặc bằng cách thay đổi spawn_links một cái gì đó giống như

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

Mặc dù nếu bạn làm điều đó theo cách sau, bạn sẽ cần phải tạo ra một biến

Self = self() 

Trước khi bạn thực hiện cuộc gọi hoặc người nào khác, nó sẽ không trở lại đúng quy trình.

Answer 2

Mã ở trên hoạt động tốt bằng cách xuất chức năng nhanh/2.

Sau đó, tôi so sánh thời gian chạy của quicksort sinh ra so với quicksort không được khai báo. Các quicksort sinh sản được lấy bất cứ nơi nào giữa 15 giây đến 32 giây để sắp xếp một danh sách 1 triệu số ngẫu nhiên trong phạm vi (1.1000000).

Các quicksort unspawned là (mã dưới đây):

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

mất bất cứ nơi nào giữa 5sec và 8sec để sắp xếp cùng một danh sách của một triệu số ngẫu nhiên.

Tôi đang thử nghiệm mã trên Thinkpad cũ của tôi, bộ xử lý 1,7 Ghz (lõi đơn) và RAM 512 Mb.

Bất kỳ lời giải thích nào cho quicksort sinh sản để hoạt động kém hơn so với cách nhanh chóng không được khai báo?

Answer 3

Tôi đã sửa đổi một chút mã để ngăn không cho nó sinh ra nhiều quy trình. Khi nó đạt đến một mức nhất định trong cây nó chuyển sang tuần tự.

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