♪ドレミファソートをDelphiに移植して幾つかの覚え書き。
quick sortは在る閾値pに対して、対象をp以下、p以上に二分して分割ソートしていく。
♪ドレミファソートの場合、それをp未満、p、pより大きい、の3つに分割し、p未満とpより大きい部分を分割ソートの対象とする。
オリジナルの♪ドレミファソートの場合、左右のデータの入れ替え時に、入れ替えたデータがpだった場合、一旦左右の端にpを詰め込んでいく。左右のデータ入れ替え終了後に、左右に詰め込んだpを中央に持ってきて三分割することになる。この最後の処理がかなり重く、オリジナルのロジックではソートデータの構造やスワップ処理党に工夫を凝らしてかなり高速化している。逆に、このぐらい高速化しないと元が中々取れない。
Delphiでプリミティブに実装した場合、このオーバーヘッドがかなりきつく、median of 3の通常のquick sortよりも大分遅い。早かったのは全部一定値のデータ とメディアンキラーな山形のデータ配置のみ。いろいろ試して見て、以下のコードがどうにか実用範囲内のスピードに落ち着いた感じ。
procedure T♪DoReMiFaSortThread.Sort(pData:PDataAry);
procedure srt(L,R:integer);
const
InsLimit = 48;
var
w,p:uint32;
wp : array[0..4] of uint32;
x,i,j,M,pr_idx,pr_l_idx,pl_idx,pl_r_idx,chgL_idx,chgR_idx:integer;
begin
if InsLimit<(R-L) then begin
// ♪ドレミファソート
// pivot > 5つの中から選ぶ
M:=(L+R) div 2;
wp[0]:=pData[L];
wp[1]:=pData[(L+M) div 2];
wp[2]:=pData[M];
wp[3]:=pData[(M+R) div 2];
wp[4]:=pData[R];
for i := 1 to 4 do begin
w:=pData[i];
if (pData[i-1] > w) then begin
j:=i;
repeat
pData[j]:=pData[j-1];
dec(j);
until (j<=0) OR (pData[j-1]<=w);
pData[j]:=w;
end;
end;
p:=wp[3];
// sort
i:=L; j:=R;
pl_idx:=-1; pr_idx:=-1;
repeat
while (pData[i]<p) do inc(i); // p以上を探す
while (pData[j]>p) do dec(j); // p以下を探す
if i=j then begin
inc(i); dec(j);
break;
end;
if i<j then begin
w:=pData[i]; pData[i]:=pData[j]; pData[j]:=w;
// pivot値の一番左端&右端のindexを覚えておく
if pData[i]=p then begin
if (pl_idx=-1) then pl_idx:=i;
pl_r_idx:=i;
end;
if pData[j]=p then begin
if (pr_idx=-1) then pr_idx:=j;
pr_l_idx:=j;
end;
// 次へ
inc(i); dec(j);
end;
until i>j;
// ユーザー要請による中断判定
if Terminated then raise EAbortSort.Create('abort');
// 分割後、左の範囲に対してpivot値を右端に寄せる
chgL_idx:=j;
if pl_idx<>-1 then
for x := pl_r_idx downto pl_idx do begin
if pData[x]=p then begin
pData[x]:=pData[chgL_idx]; pData[chgL_idx]:=p;
dec(chgL_idx);
end;
end;
// 分割後、右の範囲に対してpivot値を左端に寄せる
chgR_idx:=i; // 右分割位置の左index start値
if pr_idx<>-1 then
for x := pr_l_idx to pr_idx do begin
if pData[x]=p then begin
pData[x]:=pData[chgR_idx]; pData[chgR_idx]:=p;
inc(chgR_idx);
end;
end;
// pivot値を除いて、左右分割して再帰呼び出し
srt(L,chgL_idx);
srt(chgR_idx,R);
end else begin
// 挿入ソート
for i := L+1 to R do begin
w:=pData[i];
if (pData[i-1] > w) then begin
j:=i;
repeat
pData[j]:=pData[j-1];
dec(j);
until (j<=0) OR (pData[j-1]<=w);
pData[j]:=w;
end;
end;
end;
end;
begin
srt(0,AryLimit-1);
end;
データスワップ時にpの位置の左右両端を覚えておき、スワップ終了後にpを中央に寄せるという形。これだとmedian of 3のquick sortより通常4~5%落ちくらいの測度で納まる。constance dataやmedian killerだとかなり早い。うーむ。思っている以上にデータ転送のコストが高いんだねぇ...。
追記
左右両方の区間でpを寄せるよりも、どちらか片方だけ寄せる方がコストとスピードのバランスが良さげ。
追記その2
結局の所、pivotをどうやって旨く取るかってのが大部分を握ってるなぁ...。
最近のコメント