以前提示したクイックソートの修正
以前↓で提示した拙作クイックソートモジュールですが、
http://hsp.tv/play/pforum.php?mode=all&num=66495
最近ふと見直して、かなりヘンテコな処理をしていたことに気づきました。FIFOでもないしスタックでもない変態仕様。
2年前の自分の発想に首を傾げながら修正...。
こんなものがつい最近まで HU3DM(http://dev.onionsoft.net/seed/info.ax?id=843) に内蔵されて平気で動いていました...。勿論もう入れ替えましたけど。
多分誰も気にしていないと思いますが、修正&改良版を貼っておきます。
まずはスタックをまともにしたのと、
高速化の為に、長さ2の断片が生じた時はスタックに積まずにその場で並び替えるようにしました。
昇順と降順で処理が別になってるのは速度を稼ぐためです。
前回と同じデータで試すと当方(CPU : Celeron 1.20GHz, RAM : PC133 SDRAM)では所要時間が約 0.764 倍になりました。(72ms → 55ms)
(因みに、プラグイン hspda の sortval にやらせると 1ms。凄いね。)
#module N_M_S2_5 ;1次元配列のクイックソート ;区間を指定できる。 ;他の1次元配列を巻き添えにしてソートする。 ; ;[書式] ; ; MS2_Quick3 TGTARRY,ATTENDANT , opt, s,e ; ; TGTARRY : ターゲット配列 ; ATTENDANT : 付き添い配列 ; opt : 整列オプション(0,other)=(昇順,降順) ; s,e : 開始,終了インデックス ; ;[備考] ; ; 要素数1以下のデータを渡してはならない。 ; エラーチェックを省いている。引数の不正は致命傷になる。 #deffunc MS2_Quick3 array TGT, array ATTENDANT, int opt, int s,int e ;[定義] ; ;・「ASTGT (Assigned Section in TGT)」 : ターゲット配列のうち、今回ソート対象となっている範囲。 ;・「thresholding」 : 一定の区間内でピボット(この値をpとする)を決定し、p以下の要素を区間前方に、p以上の要素を区間前方に寄せ集める操作。 ;・「PTS (Present Thresholding Section)」 : thresholding操作の対象となっている区間。 ;・「PSI (Present Scan Index)」 : thresholding操作においてp以下,以上の値を探索するための現在検査中の要素のインデックス。左→右の検査でのインデックスを「RWPSI (Rightward PSI)」、右→左のものを「LWPSI (Leftward PSI)」と呼ぶ。 ;・「division」 : thresholding操作完了後、PTSを2分割する操作。 len_ASTGT = e-s+1 ;ASTGTの長さ StackCnt = 1 ;スタックされている区間数(初期化) dim STACK,len_ASTGT : STACK = s,e ;スタック初期化。要素(2*i),(2*i+1)に第i区間の開始,終了インデックスが記録される。 if opt { ;降順 repeat ;< pop > sidx_PTS = STACK(2*StackCnt-2) : eidx_PTS = STACK(2*StackCnt-1) ;PTS開始/終了インデックス if TGT(sidx_PTS) < TGT(sidx_PTS+1) : p = TGT(sidx_PTS) : else : p = TGT(sidx_PTS+1) ;pは区間の左端2値のうち小さい方とする ;< thresholding > RWPSI = sidx_PTS : LWPSI = eidx_PTS repeat ;< rightward scan > repeat if TGT(RWPSI) <= p : break RWPSI ++ loop ;< leftward scan > repeat if TGT(LWPSI) >= p : break LWPSI -- loop if RWPSI < LWPSI { ;要交換 tmpnum = TGT(RWPSI) : TGT(RWPSI) = TGT(LWPSI) : TGT(LWPSI) = tmpnum ;TGT tmpnum2 = ATTENDANT(RWPSI) : ATTENDANT(RWPSI) = ATTENDANT(LWPSI) : ATTENDANT(LWPSI) = tmpnum2 ;ATTENDANT RWPSI ++ : LWPSI -- } else : break ;要分割。ここで次のことが保証されている。① sidx_PTS≦LWPSI≦RWPSI≦eidx_PSI ② RWPSI-LWPSI≦1 loop ;< division > ;RWPSIの左隣を境界としてPTSを分割する StackCnt -- ;現PTSの登録解除 ;< 左側新規区間候補の吟味 > if RWPSI - sidx_PTS >= 3 { ;登録価値有り STACK(2*StackCnt) = sidx_PTS, RWPSI-1 StackCnt ++ } else { ;左側新規区間候補の長さが0～2の場合 if RWPSI - sidx_PTS = 2 { ;特に2の場合 //ここでソートしてしまう if TGT(sidx_PTS) < TGT(sidx_PTS+1) { ;要交換 sidx_PTSplus = sidx_PTS+1 tmpnum = TGT(sidx_PTS) : TGT(sidx_PTS) = TGT(sidx_PTSplus) : TGT(sidx_PTSplus) = tmpnum tmpnum2 = ATTENDANT(sidx_PTS) : ATTENDANT(sidx_PTS) = ATTENDANT(sidx_PTSplus) : ATTENDANT(sidx_PTSplus) = tmpnum2 } } } ;< 右側新規区間候補の吟味 > if eidx_PTS - RWPSI >= 2 { ;登録価値有り STACK(2*StackCnt) = RWPSI, eidx_PTS StackCnt ++ } else { ;右側新規区間候補の長さが1,2の場合 if eidx_PTS - RWPSI = 1 { ;特に2の場合 //ここでソートしてしまう if TGT(RWPSI) < TGT(eidx_PTS) { ;要交換 tmpnum = TGT(RWPSI) : TGT(RWPSI) = TGT(eidx_PTS) : TGT(eidx_PTS) = tmpnum tmpnum2 = ATTENDANT(RWPSI) : ATTENDANT(RWPSI) = ATTENDANT(eidx_PTS) : ATTENDANT(eidx_PTS) = tmpnum2 } } } ;< finish check > if StackCnt = 0 : break loop } else { ;昇順 repeat ;< pop > sidx_PTS = STACK(2*StackCnt-2) : eidx_PTS = STACK(2*StackCnt-1) if TGT(sidx_PTS) < TGT(sidx_PTS+1) : p = TGT(sidx_PTS+1) : else : p = TGT(sidx_PTS) ;pは区間の左端2値のうち大きい方とする ;< thresholding > RWPSI = sidx_PTS : LWPSI = eidx_PTS repeat ;< rightward scan > repeat if TGT(RWPSI) >= p : break RWPSI ++ loop ;< leftward scan > repeat if TGT(LWPSI) <= p : break LWPSI -- loop if RWPSI < LWPSI { ;要交換 tmpnum = TGT(RWPSI) : TGT(RWPSI) = TGT(LWPSI) : TGT(LWPSI) = tmpnum tmpnum2 = ATTENDANT(RWPSI) : ATTENDANT(RWPSI) = ATTENDANT(LWPSI) : ATTENDANT(LWPSI) = tmpnum2 RWPSI ++ : LWPSI -- } else : break loop ;< division > ;RWPSIの左隣を境界としてPTSを分割する StackCnt -- ;< 左側新規区間候補の吟味 > if RWPSI - sidx_PTS >= 3 { ;登録価値有り STACK(2*StackCnt) = sidx_PTS, RWPSI-1 StackCnt ++ } else { ;左側新規区間候補の長さが0～2の場合 if RWPSI - sidx_PTS = 2 { ;特に2の場合 //ここでソートしてしまう if TGT(sidx_PTS) > TGT(sidx_PTS+1) { ;要交換 sidx_PTSplus = sidx_PTS+1 tmpnum = TGT(sidx_PTS) : TGT(sidx_PTS) = TGT(sidx_PTSplus) : RWPSI(sidx_PTSplus) = tmpnum tmpnum2 = ATTENDANT(sidx_PTS) : ATTENDANT(sidx_PTS) = ATTENDANT(sidx_PTSplus) : ATTENDANT(sidx_PTSplus) = tmpnum2 } } } ;< 右側新規区間候補の吟味 > if eidx_PTS - RWPSI >= 2 { ;登録価値有り STACK(2*StackCnt) = RWPSI,eidx_PTS StackCnt ++ } else { ;右側新規区間候補の長さが1,2の場合 if eidx_PTS - RWPSI = 1 { ;特に2の場合 //ここでソートしてしまう if TGT(RWPSI) > TGT(eidx_PTS) { ;要交換 tmpnum = TGT(RWPSI) : TGT(RWPSI) = TGT(eidx_PTS) : TGT(eidx_PTS) = tmpnum tmpnum2 = ATTENDANT(RWPSI) : ATTENDANT(RWPSI) = ATTENDANT(eidx_PTS) : ATTENDANT(eidx_PTS) = tmpnum2 } } } ;< finish check > if StackCnt = 0 : break loop } return #global ;------------------------------------------------------------------------- #include "d3m.hsp" #include "hspda.as" screen 0,350,480 numdim = 2000 dim TGT,numdim dim TGTCPY,numdim dim ATTENDANT,numdim repeat numdim TGT(cnt) = rnd(numdim) TGTCPY(cnt) = TGT(cnt) ATTENDANT(cnt) = cnt loop s = 0 : e = 1999 len_range = e-s+1 mes ""+numdim+"個中 "+s+"～"+e+" 間のデータをソート中..." t1 = d3timer() MS2_Quick3 TGT,ATTENDANT, 0, s,e t2 = d3timer() mes "完了。所要時間 "+str(t2-t1)+" ms" sdim buf_TGTCPY,8*numdim sdim buf_TGT,8*numdim repeat numdim-1 buf_TGTCPY += ""+TGTCPY(cnt)+"\n" buf_TGT += ""+TGT(cnt)+"\n" loop buf_TGTCPY += TGTCPY(numdim-1) buf_TGT += TGT(numdim-1) lisb = 0,0 pos 0,50 : mes "整列前データ" objmode 1,1 objsize 100,400 pos 0,70 : listbox lisb(0),0,buf_TGTCPY pos 150,50 : mes "整列後データ" pos 150,70 : listbox lisb(1),0,buf_TGT
次期HSP(ver3.5かな？)ではソート命令(sortval,sortget etc.)が標準で搭載されるらしいので今後はこういったモジュールの需要は一般には無くなる感じがしますが、
ソート区間を限定できるところはこのモジュールのいいところかな？と思っています。
標準命令化される予定の sortval では強制的に配列全体がソート対象になるので、短い間にソートを何回も繰り返すとき必要な部分の切り出しとか、
不要部を宜しい定数でクリアしたりとかでパフォーマンスが落ちてしまって、結局ルーチンを自作するのと変わらなかったり...。
sortval で区間指定 & 別配列の巻き添えソートができればもう最高なんですけど。
