Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #2179 > unrolled thread

Parallel bucket sort was updated to version 1.01...

Back to article view | Back to comp.programming

Contents

  Parallel bucket sort was updated to version 1.01... "aminer" <aminer@videotron.ca> - 2012-09-07 11:48 -0500
    Re: Parallel bucket sort was updated to version 1.01... "aminer" <aminer@videotron.ca> - 2012-09-10 14:05 -0500

#2179 — Parallel bucket sort was updated to version 1.01...

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.

[toc] | [next] | [standalone]

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web