HSPポータル
サイトマップ お問い合わせ


HSPTV!掲示板

スレッド一覧 | 新規書き込み | 新着一覧 | 使い方 | 過去ログ

未解決 解決 停止 削除要請

2015
0315		cmoritoshiクイックソートの再帰について12解決


cmoritoshi

リンク

2015/3/15(Sun) 11:12:18|NO.67877

こんにちは。いつもお世話になっています。

HSPでは再帰がちょっと問題あるということを見かけ、
この掲示板でもクイックソートのスクリプトが上がっていましたが、
http://hsp.tv/play/pforum.php?mode=all&num=67460
ざっと見た感じだと、Wikipediaで見たのより
複雑だったので、ちょっと質問してみました。

//クイックソート

//Wikipedia C言語実装例より

#module

#defcfunc med3 int x,int y,int z
//x, y, z の中間値を返す
	if x<y {
		if y<z :return y :else :if z<x :return x :else :return z
	}
	else {
		if z<y :return y :else :if x<z :return x :else :return z
	}
	return 0

#deffunc quicksort array a,int left,int right
/* クイックソート
 * a     : ソートする配列
 * left  : ソートするデータの開始位置
 * right : ソートするデータの終了位置
 */
	if left < right {
		i =left :j =right
		tmp =0 :pivot =med3(a(i),a(i+(j-i)/2),a(j))		//(i+j)/2ではオーバーフローしてしまう
		repeat
			//a[] を pivot 以上と以下の集まりに分割する
			repeat
				if a(i)>=pivot :break			//a[i] >= pivot となる位置を検索
				i++
			loop
			repeat
				if pivot>=a(j) :break			//a[j] <= pivot となる位置を検索
				j--
			loop
			if i>=j :break
			tmp =a(i) :a(i) =a(j) :a(j) =tmp	//a[i],a[j] を交換
			i++ :j--
		loop
		quicksort a,left,i-1
		quicksort a,j+1,right
	}
	return

#global

data=5,3,9,8,7,10,2,1,4,6
quicksort data,0,9			//開始は0,終了はn-1

このスクリプトでも平気で動くんですけど、
実用上問題ないんでしょうか？
問題なければこのスクリプトのほうがすっきりしてるし良いと思ってるんですが、
何か問題があれば教えてください。



この記事に返信する

anal

リンク

2015/3/15(Sun) 14:23:52|NO.67882

10の要素を10000回ソート
youのスクリプト 414ms
もうひとつのスクリプト 318ms
ruby 95ms
10000の要素を10回ソート

youのスクリプト 923ms
もうひとつのスクリプト 850ms
ruby 188ms



FunnyMaker

リンク

2015/3/15(Sun) 14:34:48|NO.67884

analさんが既に試してくれてますが、単に速度の問題です。
再帰でも要素数が 2^511 を超えない限り安全なはず(たしかgosubのネストの限界が511だった気がします)。要するに心配不要。

ただし、ご存じの通りユーザー定義命令の正体はサブルーチンですので、呼び出しには多少のオーバーヘッドがあります。
HU3DMでは速度が最優先なので非再帰構造を採用しています。

以下、速度テストです。

< CPU > Intel Celeron 1.20 GHz
< Internal cache > 1st : 32KB, 2nd : 256 KB
< RAM > PC133 SDRAM 512MB



#uselib "winmm.dll"
	#cfunc timeGetTime "timeGetTime"

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//

//クイックソート

//Wikipedia C言語実装例より

#module

#defcfunc med3 int x,int y,int z
//x, y, z の中間値を返す
	if x<y {
		if y<z :return y :else :if z<x :return x :else :return z
	}
	else {
		if z<y :return y :else :if x<z :return x :else :return z
	}
	return 0

#deffunc quicksort array a,int left,int right
/* クイックソート
 * a     : ソートする配列
 * left  : ソートするデータの開始位置
 * right : ソートするデータの終了位置
 */
	if left < right {
		i =left :j =right
		tmp =0 :pivot =med3(a(i),a(i+(j-i)/2),a(j))		//(i+j)/2ではオーバーフローしてしまう
		repeat
			//a[] を pivot 以上と以下の集まりに分割する
			repeat
				if a(i)>=pivot :break			//a[i] >= pivot となる位置を検索
				i++
			loop
			repeat
				if pivot>=a(j) :break			//a[j] <= pivot となる位置を検索
				j--
			loop
			if i>=j :break
			tmp =a(i) :a(i) =a(j) :a(j) =tmp	//a[i],a[j] を交換
			i++ :j--
		loop
		quicksort a,left,i-1
		quicksort a,j+1,right
	}
	return

#global

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//

#module N_M_S2_5
	;1次元配列のクイックソート
	;区間を指定できる。
	;他の1次元配列を巻き添えにしてソートする。
	;
	;[書式]
	;
	;	MS2_Quick3 TGTARRY,FOLLOWER , opt, s,e
	;	
	;	TGTARRY : ターゲット配列
	;	FOLLOWER : 付き添い配列
	;	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を閾値として要素を区間前後に振り分ける操作。
		;・「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

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//

screen 0,350,480

#define N 2000

mes "～ sort test ～\n"+N+" elements"

;< MS2_Quick3 >
	mes "< MS2_Quick3 >"
	dim TGT, N		//ターゲット
	dim TGTCPY, N	//↑のコピー
	dim FOLLOWER, N	//付き添い配列
	repeat N : TGT(cnt) = rnd(N) : FOLLOWER(cnt) = cnt : loop : memcpy TGTCPY,TGT, 4*N
	wait 50
	t1 = timeGetTime()
	MS2_Quick3 TGT,FOLLOWER, 0, 0,N-1
	t2 = timeGetTime()
	mes "It took "+str(t2-t1)+" ms."

;< quicksort >
	mes "< quicksort >"
	dim TGT, N
	wait 50
	t1 = timeGetTime()
	quicksort TGT,0,N-1
	t2 = timeGetTime()
	mes "It took "+str(t2-t1)+" ms."



FunnyMaker

リンク

2015/3/15(Sun) 14:40:10|NO.67885

失礼。私の結果を書き忘れていました。

MS2_Quick3 : 55ms
quicksort : 72ms

です。
言うまでもなく私のモジュールでは他の配列を巻き添えにしていますが、それでもなお速度面で再帰型に勝っています。



FunnyMaker

リンク

2015/3/15(Sun) 16:56:08|NO.67886

大変失礼しました。対象データが平等ではありませんでした。
あれでは比較になっていませんね。
近日疲れているせいかミスが...。ごめんなさい。

他配列の巻き添えも外して、再帰と非再帰の違いに焦点を絞ってテストをやり直しました。

< CPU > Intel Celeron 1.20 GHz
< Internal cache > 1st : 32KB, 2nd : 256 KB
< RAM > PC133 SDRAM 512MB

要素数 2000 int型

nonRecQuicksort : 45 ms
quicksort : 63 ms

( 63/45 = 1.4 )



#uselib "winmm.dll"
	#cfunc timeGetTime "timeGetTime"

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//

//クイックソート

//Wikipedia C言語実装例より

#module

#defcfunc med3 int x,int y,int z
//x, y, z の中間値を返す
	if x<y {
		if y<z :return y :else :if z<x :return x :else :return z
	}
	else {
		if z<y :return y :else :if x<z :return x :else :return z
	}
	return 0

#deffunc quicksort array a,int left,int right
/* クイックソート
 * a     : ソートする配列
 * left  : ソートするデータの開始位置
 * right : ソートするデータの終了位置
 */
	if left < right {
		i =left :j =right
		tmp =0 :pivot =med3(a(i),a(i+(j-i)/2),a(j))		//(i+j)/2ではオーバーフローしてしまう
		repeat
			//a[] を pivot 以上と以下の集まりに分割する
			repeat
				if a(i)>=pivot :break			//a[i] >= pivot となる位置を検索
				i++
			loop
			repeat
				if pivot>=a(j) :break			//a[j] <= pivot となる位置を検索
				j--
			loop
			if i>=j :break
			tmp =a(i) :a(i) =a(j) :a(j) =tmp	//a[i],a[j] を交換
			i++ :j--
		loop
		quicksort a,left,i-1
		quicksort a,j+1,right
	}
	return

#global

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//

#module N_M_S2_5
	;1次元配列のクイックソート
	;区間を指定できる。
	;
	;[書式]
	;
	;	nonRecQuicksort TGT , opt, s,e
	;	
	;	TGT : ターゲット配列
	;	opt : 整列オプション(0,other)=(昇順,降順)
	;	s,e : 開始,終了インデックス
	;
	;[備考]
	;
	;	要素数1以下のデータを渡してはならない。
	;	エラーチェックを省いている。引数の不正は致命傷になる。
	
	#deffunc nonRecQuicksort array TGT, int opt, int s,int e
		;[定義]
		;
		;・「ASTGT (Assigned Section in TGT)」 : ターゲット配列のうち、今回ソート対象となっている範囲。
		;・「thresholding」 : 一定の区間内でピボット(この値を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
							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
								}
							}
						}
					;< 右側新規区間候補の吟味 >
						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
								}
							}
						}
				;< 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
							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
								}
							}
						}
					;< 右側新規区間候補の吟味 >
						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
								}
							}
						}
				;< finish check >
					if StackCnt = 0 : break
			loop
		}
		return
#global

//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++//

screen 0,350,480

#define N 2000

mes "～ sort test ～\n"+N+" elements"

;< nonRecQuicksort >
	mes "< nonRecQuicksort >"
	dim TGT, N		//ターゲット
	repeat N : TGT(cnt) = rnd(N) : loop
	wait 50
	t1 = timeGetTime()
	nonRecQuicksort TGT, 0, 0,N-1
	t2 = timeGetTime()
	mes "It took "+str(t2-t1)+" ms."

;< quicksort >
	mes "< quicksort >"
	dim TGT, N
	repeat N : TGT(cnt) = rnd(N) : loop
	wait 50
	t1 = timeGetTime()
	quicksort TGT,0,N-1
	t2 = timeGetTime()
	mes "It took "+str(t2-t1)+" ms."



FunnyMaker

リンク

2015/3/15(Sun) 17:17:13|NO.67887

またミスに気づいたので追記。タイムは変わりませんでしたが。
テスト用コード中に2つある、ターゲット生成用の
repeat N : TGT(cnt) = rnd(N) : loop
という文の前に
randomize 0
を補ってください。

(うん、今日はもうだめだなぁ(笑))



cmoritoshi

リンク

2015/3/15(Sun) 17:34:32|NO.67888

おお！処理時間に差が出るんですね。
データが多いと時間の差が顕著に表れてきますもんね。

回答してくれたお二方ありがとうございました。



レノス

リンク

2015/3/16(Mon) 01:57:39|NO.67910

> quicksort a,left,i-1
> quicksort a,j+1,right
ここの1行目の quicksort の中で i, j の値が変わってしまうので、
2行目の引数の j は想定されている値になってます。
(実際のところ j は (i-1) より小さい値に変化するので、必要以上の範囲をソートします。)

この例ではあまり問題ないですが、一応。



anal

リンク

2015/3/16(Mon) 02:03:37|NO.67911

レノス氏の書き込み見て思ったんだがHSPで再帰っていろいろとめんどくさい気が
変数がスタックに詰まれるわけじゃないから、思わぬ書き換えあるかもしれんし
FunnyMonkey氏のようなループでやったほうが安全性の面でもいいかも



end

リンク

2015/3/16(Mon) 06:23:00|NO.67912

確か「ZP。」氏も同じような質問したような。
http://hsp.tv/play/pforum.php?mode=all&num=66493
クイックソートかは分かりませんが、参考になれば幸いです。



FunnyMaker

リンク

2015/3/16(Mon) 07:35:12|NO.67915

>レノス さん

そうですよね。
まぁ、i,jの絶妙なバランスによって損害はごく小さくとどめられていますが。
昨日は眠すぎて見逃してたんですが、i,jがローカル指定されていませんね。
これは由々しき事態。
HSP付属ドキュメントの「モジュール機能ガイド」にはこうあります。


　モジュール内の変数は、基本的にすべて静的(static)に共有されています。 
つまり一度設定された変数は、他の値が代入されない限り、内容を失う ことはありません。
このため、再帰呼び出し(自分自身を呼び出すこと) を行なう場合には注意が必要です。 

　それぞれの定義命令内では、local宣言により明示的にローカルな変数を 作成することができます。
再帰呼び出しを行なう場合には、必ず内部で 使用する変数をローカルにするようにしてください。 
(ローカル宣言を行なうと、変数の生成と破棄のために通常よりも 実行コストがかかることも留意しておいてください。)

ということで、


#deffunc quicksort array a,int left,int right
を、


#deffunc quicksort array a,int left,int right, local i,local j
とすることで安全性は確保できるんじゃないか思います。
当然、変数の生成・破棄のお祭りになるので実行コストが上がりますが。


>end さん
あ、懐かしい...。
今更なんですが、あのスクリプトでgosubのネストが511を超えたのは、ピボットの取り方と再帰の仕方が悪いからなんだと思うんですよね。
あのとき自信がなくてそこに言及できなかったのが悔やまれます。
(でないと、No.67884での私の発言との間に矛盾が生じる)

ピボットを閾値として要素を前後に振り分ける操作をすると、通常は2つの区間が新たに発生します。
ここで、「より身近い方」を優先して再帰で渡すことにより、全要素数 2^511 までなら確実に耐えられるようになると考えています。
(2分法のようなイメージですが、この場合、生成される区間の一方は必ず元の半分よりも短くなります)



FunnyMaker

リンク

2015/3/16(Mon) 07:37:22|NO.67916

誤字訂正

「より身近い方」 → 「より短い方」



cmoritoshi

リンク

2015/3/16(Mon) 23:02:07|NO.67940

やっぱり再帰だと動作が怪しくなるんですね。
再帰はあまり使わないようにします。

トップ | HSP3ダウンロード | HSPTVで遊ぶ | HSPで作る | サイト情報 | プライバシーポリシー | お問合せ

ONION software Copyright 1997-2025(c) All rights reserved.