・高速化の方法
Quick Sortの部分を以下に示します。 procedure tkousoku.dvs(st,ed:integer); var
i,j,a,b,c:integer; begin
j:=(st+ed)div 2;
a:=ars[st];
ars[st]:=ars[j];
b:=ars[st];
ars[j]:=a;
c:=st+1;
j:=c;
for i:=c to ed do
begin
if ars[i]>b then
begin
a:=ars[i];
ars[i]:=ars[j];
ars[j]:=a;
inc(j);
end;
end;
dec(j);
a:=ars[st];
ars[st]:=ars[j];
ars[j]:=a;
if j-1-st>1 then
dvs(st,j-1);
if ed-(j+1)>1 then
dvs(j+1,ed); end;
配列を普通に使ってやるとだいたい上の様になると思います。
これを以下のようにします。 procedure tkousoku.dvsf(st,ed:integer); var
i,j,a,b,c:integer;
ip,jp:^integer; begin
j:=(st+ed)div 2;
a:=art[st];
art[st]:=art[j];
art[j]:=a;
b:=art[st];
c:=st;
inc(c);
ip:=@art[c];
jp:=@art[c];
for i:=st+1 to ed do
begin
if ip^>b then
begin
a:=ip^;
ip^:=jp^;
jp^:=a;
inc(jp);
end;
inc(ip);
end;
dec(jp);
a:=art[st];
art[st]:=art[j];
art[j]:=a;
if j-1-st>1 then
dvsf(st,j-1);
if ed-(j+1)>1 then
dvsf(j+1,ed); end;
配列の計算の最初のアドレスをポインタに代入して、それを
インクリメントすることによって次の要素に移るようになっています。
この変更によって２０％ほど速度が速くなります。
早くなる理由は、おそらく配列のアドレスを計算するときの処理回数が
減るためではないかと思われます。
このプログラムのテクニックは、他の場合においても有効だと
思います。ただ、配列が一回のループの中で一カ所しか
アクセスしない場合は最適化されるようで、
速度に差は出ません。べつに遅くなることはないので、
いつも使っていればだいたい早くなると思います。
