Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail
From: "aminer" <aminer@videotron.ca>
Newsgroups: comp.programming.threads,comp.programming
Subject: Re: Parallel bucket sort was updated to version 1.01...
Date: Mon, 10 Sep 2012 14:05:10 -0500
Organization: A noiseless patient Spider
Lines: 177
Message-ID: <k2la4q$gee$1@dont-email.me>
References: <k2d8gq$sca$1@dont-email.me>
Injection-Date: Mon, 10 Sep 2012 18:05:14 +0000 (UTC)
Injection-Info: mx04.eternal-september.org; posting-host="c43ca82f9e8d62a602307fe9d2e9b807"; logging-data="16846"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18/vAUpkvy5kZnki75mdtjm"
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.5512
X-RFC2646: Format=Flowed; Response
X-Newsreader: Microsoft Outlook Express 6.00.2900.5512
Cancel-Lock: sha1:JiTcfkjulnpGczmJZaDt6+NUemU=
X-Priority: 3
X-MSMail-Priority: Normal
Xref: csiph.com comp.programming.threads:1058 comp.programming:2187

Hello,

I have updated parallel bucketsort to versin 1.02..


Now you can sort in both ascending and descending order,
and i have changed a little bit the interface , now
if you want to sort in ascending order you have to call
the bucketsort method with ctAscending , and if you
want to sort in descending  order call it with ctDescending
like this

myobj.bucketsort(tab,comp,comp1,ctAscending);
// use ctAscending or CtDescending.



You can download parallel bucketsort from:

http://pages.videotron.com/aminer/




Thank you,
Amine Moulay Ramdane

"aminer" <aminer@videotron.ca> wrote in message 
news:k2d8gq$sca$1@dont-email.me...
>
> Hello,
>
> Bucket sort is not a sorting algorithm itself, rather it is a
> procedure for partitioning data to be sorted using some given
> sorting algorithm-a "meta-algorithm" so to speak.
>
> Bucket sort will be better, when elements are uniformly distributed
> over an interval [a, b]  and buckets have not significantly different
> number of elements.
>
> bucketsort sequential computational complexity using quicksort is
> = p × (n/p) log(n/p) = n log(n/p)
>
> bucket sort parallel computational complexity using quicksort
> = (n/p) log(n/p)
>
> Parallel BucketSort gave me also 3x scaling when sorting strings on a
> quad cores, it scales better than my parallel quicksort and it can be
> much faster than my parallel quicksort.
>
> I have thought about my parallel quicksort , and i have found
> that parallelquicksort is fine but the problem with it is that the
> partition function is not parallelizable , so i have thought about this
> and i have decided to write a parallel BucketSort,and this parallel
> bucketsort can give you much better performance than parallel quicksort
> when sorting 100000 strings or more, just test it yourself and see,
> parallel bucketsort can sort just strings at the moment, and it can use
> quicksort or mergesort, mergesort is faster.
>
> I have updated parallel bucketsort to version 1.01 , i have
> changed a little bit the interface, now you have to pass
> to the bucketsort method three parameters: the array,
> a  TSortCompare function and a TSortCompare1 function.
>
> Here is a small example in Object Pascal:
>
> program test;
>
> uses parallelbucketsort,sysutils,timer;
>
> type
>
> TStudent = Class
> public
> mystring:string;
> end;
>
> var tab:Ttabpointer;
> myobj:TParallelSort;
> student:TStudent;
> i,J:integer;
> a:integer;
>
>
> function comp1(Item1:Pointer): string;
> begin
> result:=TStudent(Item1).mystring ;
> end;
> ?
> function comp(Item1, Item2: Pointer): integer;
> begin
> if TStudent(Item1).mystring > TStudent(Item2).mystring
> then
> begin
> result:=1;
> exit;
> end;
> if TStudent(Item1).mystring < TStudent(Item2).mystring
> then
> begin
> result:=-1;
> exit;
> end;
> ?
> if TStudent(Item1).mystring = TStudent(Item2).mystring
> then
> begin
> result:=0;
> exit;
> end;
> end;
> ?
> begin
>
> myobj:=TParallelSort.create(1,ctQuicksort); // set to the number of 
> cores...
>
> setlength(tab,1000000);
> ?
> for i:=low(tab) to high(tab)
> do
> begin
> student:=TStudent.create;
> student.mystring:= inttostr(i);
> tab[high(tab)-i]:= student;
> end;
> ?
> HPT.Timestart;
>
> myobj.bucketsort(tab,comp,comp1);
> //myobj.qsort(tab,comp);
> writeln('Time in microseconds: ',hpt.TimePeriod);
> ?
> writeln;
> writeln('Please press a key to continu...');
> readln;
>
> for i := LOW(tab) to HIGH(Tab)-1
> do
> begin
> if tstudent(tab[i]).mystring > tstudent(tab[i+1]).mystring
> then
> begin
> writeln('sort has failed...');
> halt;
> end;
> end;
>
> for i := LOW(tab) to HIGH(Tab)
> do
> begin
> writeln(TStudent(tab[i]).mystring,' ');
> end;
>
> for i := 0 to HIGH(Tab) do freeandnil(TStudent(tab[i]));
>
> setlength(tab,0);
> myobj.free;
>
> end.
>
>
> You can download parallel bucketsort from:
>
> http://pages.videotron.com/aminer/
>
>
> Thank you,
> Amine Moulay Ramdane.
>
>
>
>
>
>