-module(psrs).
-export([main_process/2,child_process/1]).
main_process(Data,P) ->
%均匀划分
[FirstList|LeftList]=lists:reverse(divideList(Data,P)),
%创建其他子进程
ChildPidList=process_create(LeftList,[]),%将剩下元素交给子进程,返回子进程号列表
%播送其他进程的进程号
sendPidList([self()|ChildPidList],ChildPidList),
%局部排序
SortList=lists:sort(FirstList),
%正则采样
Sample=getsample(SortList,P),
%接收其他进程样本，采样排序
TotalSample=receive_sample(P-1,Sample),
SortSample=lists:sort(TotalSample),
%选择主元
MainItem=lists:reverse(find_mainitem(SortSample,P-1)),
%播送主元
sendItemList(MainItem,ChildPidList),
%主元划分,每一段是一个列表
PartitionList=list_partition(FirstList,MainItem),%此时段号是反序，所以交换时反序交换
%全局交换
SwapList=swap(PartitionList,[self()|ChildPidList]),
%归并排序
MergeSortList=mergesort(SwapList),
%合并结果
Result=merge_result(ChildPidList,MergeSortList),
%输出结果
io:format("~w~n",[Result]).
child_process(MyList) ->
SortList=lists:sort(MyList),
%接受其他进程pid
receive
{pid,PidList} -> [Master|Pids]=PidList
end,
P=lists:flatlength(PidList),
%正则采样
Sample=getsample(SortList,P),
%向主进程发送样本
Master!{sample,Sample},
%接收主进程发送的主元
receive
{mainitem,MainItem} -> MainItem
end,
%主元划分
PartitionList=list_partition(MyList,MainItem),
%全局交换
SwapList=swap(PartitionList,PidList),
%归并排序
MergeSortList=mergesort(SwapList),
%发送自己的结果
Master!{result,self(),MergeSortList}.
%对列表进行P份划分，然后返回划分后的列表,列表中每P个元素又作为一个列表整体
divideList(Data,P) -> Length=lists:flatlength(Data),
PerLength=Length div P,
dividing(Data,PerLength,[]).
dividing(Data,PerLength,L) -> SubList=lists:sublist(Data,PerLength),%返回第一个元素到第PerLength个元素
Len=lists:flatlength(Data),
if
PerLength<Len ->
NewData=lists:sublist(Data,PerLength+1,Len-PerLength),%返回PerLength后的所有元素
dividing(NewData,PerLength,[SubList|L]);
true ->
[SubList|L]
end.
%将数据分给其他进程，并创建
process_create([],PidList) -> PidList;
process_create([HList|TList],PidList) -> Pid=spawn(psrs,child_process,[HList]),
process_create(TList,[Pid|PidList]).
%将进程号告诉所有进程
sendPidList(TotalPidList,[H]) -> H!{pid,TotalPidList};
sendPidList(TotalPidList,[H|T]) -> H!{pid,TotalPidList},%向其他子进程播送
sendPidList(TotalPidList,T).
%正则采样
getsample(MyList,P) -> Len=lists:flatlength(MyList),
PerLen=Len div P,
getsample(MyList,PerLen,[]).
getsample(MyList,PerLen,L) -> Len=lists:flatlength(MyList),
[H|T]=MyList,
if
PerLen<Len ->
NewData=lists:nthtail(PerLen,MyList),%返回第PerLen个元素后面的元素
getsample(NewData,PerLen,[H|L]);
true ->
[H|L]
end.
%接收其他进程样本
receive_sample(0,Sample) -> Sample;
receive_sample(P,Sample) -> receive
{sample,OtherSample} -> receive_sample(P-1,lists:append(Sample,OtherSample))%将两个列表连接
end.
%选择主元
find_mainitem(Sample,P) -> Len=lists:flatlength(Sample),
PerLen=Len div (P+1),
NewSample=lists:sublist(Sample,PerLen+1,Len-PerLen),
find_mainitem(NewSample,PerLen,[]).
find_mainitem(Sample,PerLen,L) -> [H|T]=lists:sublist(Sample,PerLen),
Len=lists:flatlength(Sample),
if
PerLen<Len ->
NewSample=lists:sublist(Sample,PerLen+1,Len-PerLen),
find_mainitem(NewSample,PerLen,[H|L]);
true ->
[H|L]
end.
%将主元告诉其他进程
sendItemList(MainItem,[HPid]) -> HPid!{mainitem,MainItem};
sendItemList(MainItem,[HPid|TPid]) -> HPid!{mainitem,MainItem},
sendItemList(MainItem,TPid).
%主元划分
list_partition(MyList,MainItem) -> partitioning(MyList,MainItem,[]).
partitioning(LeftPart,[],L) -> [LeftPart|L];
partitioning(MyList,[H|TItem],L) -> {FirstPart,LeftPart}={[X || X <- MyList,X=<H],[X || X <- MyList,X>H]},%分成两部分
partitioning(LeftPart,TItem,[FirstPart|L]).
%全局交换,先发送自己的列表，再接收别的列表
swap(PartitionList,TotalPidList) -> swap_send(PartitionList,lists:reverse(TotalPidList)),%Pid反过来发送
swap_receive(lists:flatlength(TotalPidList),[]).
swap_send([HList],[HPid]) -> HPid!{otherlist,HList};
swap_send([HList|TList],[HPid|TPid]) -> HPid!{otherlist,HList},
swap_send(TList,TPid).
swap_receive(0,L) -> L;
swap_receive(P,L) -> receive
{otherlist,OtherList} -> swap_receive(P-1,[OtherList|L])
end.
%归并排序
mergesort(SwapList) -> NewList=lists_append(SwapList,[]),%将几段小列表合并
lists:sort(NewList).
lists_append([],L) -> L;
lists_append([HList|TList],L) -> lists_append(TList,lists:append(L,HList)).
%合并结果
merge_result([],L) -> L;
merge_result([HPid|TPid],L) ->
receive
{result,HPid,Result} -> merge_result(TPid,lists:append(L,Result))
end.
