[erlang-questions] Bucket Sort

[tonakai]

hi,
i've implement a concurrent bucket sort in erlang, but its kind of
slow (slower then the sequential version)
i think my mistake is that i first create the buckets, then i send
them to processes i spawned. Will it increase the speed if i send each
integer to processes rather then sending the list at the end? i am
thinking that will increase message-passing...

here is the code:

start2(List, N, Max) ->

    Buckets = sortbucket(
                dict:to_list(seqbucketsort:divide(List, N, Max))
        ),
    Pid_buckets = [{spawn(fun loop/0), Bucket} || {_,Bucket}<-Buckets],
    M = [rpc(P,B) || {P,B} <- Pid_buckets],
    lists:append(
        lists:sort(M)
    )
.

%%This is how i measure the time spend
timedstart(List, N, Max) ->
    statistics(runtime),
    statistics(wall_clock),
    start2(List,N,Max),
    {_, Time1} = statistics(runtime),
    {_, Time2} = statistics(wall_clock),
    io:format("Concurrent Bucket Sort Time =~p (~p) microseconds~n",

rpc(Pid, Request) ->
    Pid ! {self(), Request},
    receive
	{Pid, Response} ->
	    Response
    end.

loop() ->
    receive
	{From, List} ->
	    From ! {self(), lists:sort(List)}
    end.

thanks,

On Thu, May 21, 2009 at 12:24 PM, tonakai <aykutsoysal@REDACTED> wrote:
> On Thu, May 21, 2009 at 3:33 AM, Colm Dougan <colm.dougan@REDACTED> wrote:
>>
>> On Thu, May 21, 2009 at 12:20 AM, tonakai <aykutsoysal@REDACTED> wrote:
>> > Hi,
>> > i am a erlang newbie and trying to implement bucket sort, but i am stuck at
>> > the beginning because I can't figure out a way to divide the list into small
>> > buckets, i try to use accumulators but number of buckets is not fixed, i
>> > think i need to find a way to populate lists of lists.
>> > also i am thinking for concurrent version of it, but its also same problem,
>> > i need to send the number to the correct bucket (process).
>> > any ideas?
>>
>> Can you give an example of the type of data you are working with?
>
> I am working with simple integers for now.
>>
>> Typically the 'dict' module is useful for grouping things, e.g. :
>>
>>   List =
>>   [1,2,3,3,4,4,4,5,6,6,7,8,9,10,10,11],
>>
>>   D1 =
>>   lists:foldl(
>>       fun(El, Acc) ->
>>           Bucket = (3 * (El div 3)),
>>           dict:append(Bucket, El, Acc)
>>       end,
>>       dict:new(),
>>       List
>>   ),
>>
>>   io:format("~p~n", [dict:to_list(D1)]),
>>
>>
>> Colm
>
> Thanks it works :)
>
> i modify your code to divide the list to bucket:
> %%N is the number of buckets and Max is the maximum limit for the integers in
> %%the list, so that i can calculate the range of the buckets.
> divide(List, N, Max) -> lists:foldl(
>    fun(E1, Acc) ->
>    Bucket = ((Max div N)*(E1 div (Max div N))),
>    dict:append(Bucket, E1, Acc)
>    end,
>    dict:new(), List).
>
> thanks again, i will work more and let you know if something goes wrong....
>
> --
> Aykut Soysal
> Pod Palackehova Vrchem a05-517 Brno
> aykutsoysal@REDACTED
> http://aykutsoysal.com
> +420774281226
>



-- 
Aykut Soysal
Pod Palackehova Vrchem a05-517 Brno
aykutsoysal@REDACTED
http://aykutsoysal.com
+420774281226