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

Groups > comp.programming.threads > #1052

Parallel bucket sort was updated to version 1.01...

Cross-posted to 2 groups.

Show key headers only | View raw

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.

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar

Thread

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

csiph-web