Hello,
Here is what have changed in version 3.0:
I have implemented a Binary search like this:
==
function BinSearch(var a: TTabPointer; value:pointer;left, right:long;SCompare: TSortCompare): Integer;
var
First: long;
Last: long;
Pivot: long;
Found: Boolean;
begin
First := left;
Last := right;
Found := False;
Result := -1;
while (First <= Last) and (not Found) do
begin
Pivot := (First+Last)div 2;
if scompare(a[Pivot],value)=0 then
begin
Found := True;
Result := Pivot;
end
else if scompare(a[Pivot],value)>0 then
Last := Pivot - 1
else
First := Pivot + 1;
end;
end;
==
And i have added a ne SequentialMerge like this:
===
Procedure SequentialMerge(var to1:TTabPointer; var temp:TTabPointer; lowX, highX,lowY, highY, lowTo:long;SCompare: TSortCompare);
var highto:long;
begin
highTo := lowTo + highX - lowX + highY - lowY + 1;
for lowto:=lowto to highto
do
begin
if (lowX > highX)
then
begin
to1[lowTo] := temp[lowY];
inc(lowY);
end
else if (lowY > highY)
then
begin
to1[lowTo] := temp[lowX];
inc(lowX);
end
else
begin
if scompare(temp[lowX],temp[lowY])<0
then
begin
to1[lowTo]:=temp[lowX];
inc(lowX);
end
else
begin
to1[lowTo]:=temp[lowY];
inc(lowY);
end;
end;
end;
end;
===
And i have added the TParallelSort.merge_parallel1()
method that will be called in parallel. like this:
===
procedure TParallelSort.merge_parallel1(job:pointer);
begin
merge_parallel(tjob2(job).t,tjob2(job).p1,tjob2(job).r1,tjob2(job).p2,tjob2(job).r2,tjob2(job).a,tjob2(job).p3,tjob2(job).comp,tjob2(job).value,tjob2(job).event);
lockeddeclong1(tjob2(job).value);
if long(tjob2(job).value^)=0 then tjob2(job).event.setevent;
tjob2(job).free;
end;
==
And i have added a TParallelSort.merge_parallel() method that
uses my threadpool engine to call the TParallelSort.merge_parallel1 method:
===
procedure TParallelSort.merge_parallel(var t:TTabPointer; p1, r1:long; p2, r2:long;var a:TTabPointer; p3:long;SCompare: TSortCompare;value:pointer;event:TSimpleEvent);
var length1,length2,tmp,q1,q2,q3:long;
mergeLeft,mergeRight:TJob2;
begin
length1 := (r1 - p1) + 1;
length2 := (r2 - p2) + 1;
if ( length1 = 0 ) then exit;
//if ((( length1 + length2 ) <= 8000) ) or (long(value^)>=(nbrprocs1-1)) then
if (( length1 + length2 ) <= 8000) then
begin
SequentialMerge(a, t, p1, r1, p2, r2, p3,scompare);
exit;
end;
if (length1 < length2) then
begin
merge_parallel(t, p2,r2,p1, r1, a,p3,SCompare,value,event);
exit;
end;
q1 := (p1 +r1) div 2;
q2 :=my_binary_search( t,t[q1 ], p2, r2,SCompare);
// q2 := binsearch( t,t[q1 ], p2, r2,SCompare);
{if (q2=-1)
then
begin
writeln('titi');
SequentialMerge(a, t, p1, r1, p2, r2, p3,scompare);
exit;
end;}
q3 := p3 + ((q1 - p1)) + ((q2 - p2)) ;
a[q3] := t[q1];
//mergeLeft:=TParallelMerge.create();
mergeLeft:=TJob2.create();
mergeLeft.t:=t;
mergeLeft.p1:=p1;
mergeLeft.r1:=q1-1;
mergeLeft.p2:=p2;
mergeLeft.r2:=q2-1;
mergeLeft.a:=a;
mergeLeft.p3:=p3;
//mergeLeft.obj:=self;
mergeLeft.comp:=scompare;
mergeleft.value:=value;
mergeLeft.event:=event;
lockedinclong1(value);
{ if (long(value^)>=(nbrprocs1-2)) then
begin
lockeddeclong1(value);
SequentialMerge(a, t, p1, r1, p2, r2, p3,scompare);
mergeleft.free;
exit;
end;}
mergeRight:=TJob2.create();
mergeRight.t:=t;
mergeRight.p1:=q1+1;
mergeRight.r1:=r1;
mergeRight.p2:=q2;
mergeRight.r2:=r2;
mergeRight.a:=a;
mergeRight.p3:=q3+1;
mergeRight.comp:=scompare;
mergeRight.value:=value;
mergeRight.event:=event;
lockedinclong1(value);
{if (long(value^)>=(nbrprocs1-2)) then
begin
lockeddeclong1(value);
SequentialMerge(a, t, p1, r1, p2, r2, p3,scompare);
mergeRight.free;
exit;
end;}
TP.execute(self.merge_parallel1,pointer(mergeLeft));
TP.execute(self.merge_parallel1,pointer(mergeRight));
end;
===
And i have changed the TParallelSort.parallelmerge() method
, now it calls TParallelSort.merge_parallel((), not merge1(), like this:
==
procedure TParallelSort.parallelmerge(obj:pointer) ;
var
local_count:long;
value:long;
event1:TSimpleEvent;
i:long;
begin
event1:=tsimpleevent.create;
value:=0;
//Merge1(Tjob1(obj).a1,Tjob1(obj).a2,Tjob1(obj).Low,Tjob1(obj).Mid,Tjob1(obj).Hi,Tjob1(obj).comp);
merge_parallel(Tjob1(obj).a1,Tjob1(obj).Low,Tjob1(obj).Mid,Tjob1(obj).Mid+1,Tjob1(obj).Hi,Tjob1(obj).a2,0,Tjob1(obj).comp,@value,event1);
event1.waitfor(INFINITE);
event1.resetevent;
for i:=Tjob1(obj).Low to Tjob1(obj).Hi
do
begin
Tjob1(obj).a1:=Tjob1(obj).a2[i-Tjob1(obj).Low]
end;
setlength(Tjob1(obj).a2,0);
local_count:=LockedIncLong(count1);
if local_count=TJob1(obj).count then Tjob1(obj).event.setevent;
TJob1(obj).free;
event1.free;
end;
===
Thank you,
Amine Moulay Ramdane.
Recent
