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


HSPTV!掲示板


未解決 解決 停止 削除要請

2014
1217
ZP。ソートプログラムでスタック領域のオーバーフロー4解決


ZP。

リンク

2014/12/17(Wed) 20:08:33|NO.66493

現在、ソートプログラムを開発しています。

#module #deffunc Quicksort array data , int lops , int mod , local idx_mes , local data_list1 , local data_list2 , local data_list1_cnt , local data_list2_cnt , local data_list1_mod , local data_list2_mod , local _data /* Quicksort V , I1 , I2 V=数値の入った配列要素 I1=比較数 I2=ソートモード(0=小さい順,1=大きい順) */ if lops<1 :return ;比較数が1以下である場合は終了 dim data_list1,idx_mes ;比較1 dim data_list2,idx_mes ;比較2 idx_mes=data(0) ;先頭文字 //-------- ループ開始 --------// repeat lops-1,1 ;始めの文字を抜かして計測 //----大きい順の場合 if mod{ if idx_mes<data(cnt){ ;始めの数字よりも大きい場合 if data_list1_cnt=0{ data_list1_mod=data(cnt) } else{ if data_list1_mod!=-1{ if data_list1_mod!=data(cnt){ data_list1_mod=-1 } } } data_list1(data_list1_cnt)=data(cnt) data_list1_cnt++ } else{ ;始めの数字よりも小さい場合 if data_list2_cnt=0{ data_list2_mod=data(cnt) } else{ if data_list2_mod!=-1{ if data_list2_mod!=data(cnt){ data_list2_mod=-1 } } } data_list2(data_list2_cnt)=data(cnt) data_list2_cnt++ } }//----小さい順の場合 else{ if idx_mes>data(cnt){ ;始めの数字よりも小さい場合 if data_list1_cnt=0{ data_list1_mod=data(cnt) } else{ if data_list1_mod!=-1{ if data_list1_mod!=data(cnt){ data_list1_mod=-1 } } } data_list1(data_list1_cnt)=data(cnt) data_list1_cnt++ } else{ ;始めの数字よりも大きい場合 if data_list2_cnt=0{ data_list2_mod=data(cnt) } else{ if data_list2_mod!=-1{ if data_list2_mod!=data(cnt){ data_list2_mod=-1 } } } data_list2(data_list2_cnt)=data(cnt) data_list2_cnt++ } } loop //-------- 終了 --------// data_list1(data_list1_cnt)=idx_mes ;最初の値を比較1に代入 data_list1_cnt++ ;比較1のカウントを増加 if data_list1_mod=-1 :Quicksort data_list1,data_list1_cnt,mod ;比較1を再ループ if data_list2_mod=-1 :Quicksort data_list2,data_list2_cnt,mod ;比較2を再ループ memcpy data , data_list1 , data_list1_cnt*4 ;コピー memcpy data , data_list2 , data_list2_cnt*4 , data_list1_cnt*4 ;コピー2 return #global ;モジュールの終了 //----初期登録 #include "d3m.hsp" randomize //----ランダムに値を作成 lop=10000 ;数 dim data,lop repeat lop data.cnt=rnd(10) ;乱数 loop //----ソート前の状態を表示 sdim list repeat lop list+""+data.cnt+" , " loop mesbox list,640,240 //----ソート time=d3timer() Quicksort data,lop,1 _time=1.0*(d3timer()-time)/1000 title "掛かった時間"+strf("%.3f",_time) //----ソート後の状態を表示 sdim list repeat lop list+""+data.cnt+" , " loop pos 0,240 mesbox list,640,240
しかし、このプログラムを実行すると、「スタック領域のオーバーフローです」と表示されてしまいます。
調べてみると、「サブルーチンのネストが多く呼び出しが連続したとき、HSPがサブルーチンの呼び出し元を覚えきれないときエラーになります。」という事らしいですが、
エラーを出さないようにうまくプログラムが組めるでしょうか?



この記事に返信する


FunnyMaker

リンク

2014/12/17(Wed) 20:48:46|NO.66494

コードをザッと呼んだだけですが、再帰しようとしていますよね...?

#deffuncで定義したルーチンへのジャンプはgosubによるサブルーチンジャンプと大体一緒です。
命令の中から自身を何回も再呼び出していてはネストが深くなって、HSPではアウトになります。
提示されたコードでは、sublev (サブルーチンのネストレベル)が511を超えた時点で死んでいました。
再帰を使わない方法に変更する必要があります。



FunnyMaker

リンク

2014/12/17(Wed) 20:59:22|NO.66495

連投失礼します。

ではどうすればよいか?
ということでしたね...。

まぁ、大したことはないんです。私でさえ思いつくんですから。
本当はきちんと説明したいですが、忙しくて説明する暇がないのでとりあえず拙作コードを貼っておきます。参考までに。

待っていれば、もっと上手い人が現れるかもしれません。



#module N_M_S2_5 ;1次元配列のクイックソート ;区間を指定できる。 ;他の1次元配列を巻き添えにしてソートする。 ; ;[書式] ; ; MS2_Quick3 TGTARRY,ATTENDANT , opt, s,e ; ; TGTARRY : ターゲット配列 ; ATTENDANT : 付き添い配列 ; opt : 整列オプション(other,1)=(昇順,降順) ; s,e : 開始,終了インデックス ; ;[備考] ; ; 要素数1以下のデータを渡してはならない。 ; エラーチェックを省いている。引数の不正は致命傷になる。 #deffunc MS2_Quick3 array TGT, array ATTENDANT, int opt, int s,int e ;[用語] ; ;・「守備範囲」 ; ターゲットのうち、今回ソート対象となっている範囲。 ; ;・「操作1」 ; 一定の区間内でピボット(この値をpとする)を決定し、p以下の要素を区間前方に、p以上の要素を区間前方に寄せ集める操作。 ; ;・「アクティブ区間」 ; 現在操作1の対象となっている区間。 ; 常に第0区間がアクティブ区間である。 ; ;・「カレントスキャンインデックス(CSI)」 ; 操作1においてp以下,以上の値を探索するための、現在検査中の要素の、アクティブ区間の左端を基点としたインデックス。 ; 左→右の検査でのインデックスを「LCSI」、右→左のものを「RCSI」と呼ぶ。 len_RANGE = e-s+1 ;守備範囲の大きさ num_area_remain = 1 ;残っている区間数(初期化) dim Area,len_RANGE : Area = s,e ;区間データ初期化 ;! 区間データのフォーマット ! ; 要素(2*i),(2*i+1)に第i区間の開始,終了インデックスが記録される。 ; 要素は前から詰めて記録される。 if opt { ;降順 repeat ln_AA = Area(1)-Area+1 ;アクティブ区間の長さ ;< ピボットの選定 > if TGT(Area) < TGT(Area+1) { val_pivot = TGT(Area) } else { val_pivot = TGT(Area+1) } ;< 操作1 > LCSI = 0 : RCSI = ln_AA-1 repeat ;< LCSIを右に進める > repeat if TGT(Area+LCSI) <= val_pivot : break LCSI ++ loop ;< RCSIを左に進める > repeat if TGT(Area+RCSI) >= val_pivot : break RCSI -- loop if LCSI < RCSI { ;要交換 k0 = Area+LCSI : k1 = Area+RCSI TmpVal1 = TGT(k0) : TGT(k0) = TGT(k1) : TGT(k1) = TmpVal1 ;実値交換 TmpVal2 = ATTENDANT(k0) : ATTENDANT(k0) = ATTENDANT(k1) : ATTENDANT(k1) = TmpVal2 ;付き添い配列操作 LCSI ++ : RCSI -- } else { ;要区間分割 ;※次のことが保証されている ; 0≦RCSI≦LCSI≦ln_AA-1 ; |LCSI-RCSI|≦1 break } loop ;< 区間分割 > ;LCSIの左隣を境としてアクティブ区間を分割する ;区間数の増加は-1,+0,+1のいずれかである。 num_area_remain -- ;アクティブ区間の区間登録解除 ;< 左側新規区間候補の吟味 > if LCSI >= 2 { ;登録価値有り endIdx_AA_prev = Area(1) ;旧アクティブ区間の終了インデックス Area(1) = Area+LCSI-1 num_area_remain ++ flg0 = 1 ;左側新規区間発生フラグ } else : flg0 = 0 ;< 右側新規区間候補の吟味 > if LCSI <= ln_AA-2 { ;登録価値有り if flg0 { Area(2*num_area_remain) = Area+LCSI, endIdx_AA_prev } else { Area += LCSI } num_area_remain ++ flg1 = 0 ;区間数減少フラグ } else { if flg0 { flg1 = 0 } else { flg1 = 1 } } ;< 区間数が減少している場合はエリアデータをシフトする > if flg1 : memcpy Area,Area, 8*num_area_remain, 0,8 ;< 完了検査 > if num_area_remain = 0 : break loop } else { ;昇順 repeat ln_AA = Area(1)-Area+1 ;アクティブ区間の長さ ;< ピボットの選定 > if TGT(Area) < TGT(Area+1) { val_pivot = TGT(Area+1) } else { val_pivot = TGT(Area) } ;< 操作1 > LCSI = 0 : RCSI = ln_AA-1 repeat ;< LCSIを右に進める > repeat if TGT(Area+LCSI) >= val_pivot : break LCSI ++ loop ;< RCSIを左に進める > repeat if TGT(Area+RCSI) <= val_pivot : break RCSI -- loop if LCSI < RCSI { ;要交換 k0 = Area+LCSI : k1 = Area+RCSI TmpVal1 = TGT(k0) : TGT(k0) = TGT(k1) : TGT(k1) = TmpVal1 ;実値交換 TmpVal2 = ATTENDANT(k0) : ATTENDANT(k0) = ATTENDANT(k1) : ATTENDANT(k1) = TmpVal2 ;付き添い配列操作 LCSI ++ : RCSI -- } else { ;要区間分割 ;※次のことが保証されている ; 0≦RCSI≦LCSI≦ln_AA-1 ; |LCSI-RCSI|≦1 break } loop ;< 区間分割 > ;LCSIの左隣を境としてアクティブ区間を分割する ;区間数の増加は-1,+0,+1のいずれかである。 num_area_remain -- ;アクティブ区間の区間登録解除 ;< 左側新規区間候補の吟味 > if LCSI >= 2 { ;登録価値有り endIdx_AA_prev = Area(1) ;旧アクティブ区間の終了インデックス Area(1) = Area+LCSI-1 num_area_remain ++ flg0 = 1 ;左側新規区間発生フラグ } else : flg0 = 0 ;< 右側新規区間候補の吟味 > if LCSI <= ln_AA-2 { ;登録価値有り if flg0 { Area(2*num_area_remain) = Area+LCSI, endIdx_AA_prev } else { Area += LCSI } num_area_remain ++ flg1 = 0 ;区間数減少フラグ } else { if flg0 { flg1 = 0 } else { flg1 = 1 } } ;< 区間数が減少している場合はエリアデータをシフトする > if flg1 : memcpy Area,Area, 8*num_area_remain, 0,8 ;< 完了検査 > if num_area_remain = 0 : break loop } return #global //*----------------------------▽ sample ▽----------------------------*// #include "d3m.hsp" screen 0,350,480 numdim = 5000 dim TGT,numdim dim TGTCPY,numdim dim ATTENDANT,numdim repeat numdim TGT(cnt) = rnd(numdim) TGTCPY(cnt) = TGT(cnt) ATTENDANT(cnt) = cnt loop s = 1000 : e = 3999 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 //*----------------------------△ sample △----------------------------*//



ZP。

リンク

2014/12/18(Thu) 20:36:08|NO.66498

返信遅くなりすみません。
ありがとうございます! とても参考になりました!
ちょっと理解が難しいですが、なんとかできそうです。
解決済みにしておきます。



ZP。 最後に。

リンク

2014/12/19(Fri) 19:23:57|NO.66508

完成したので、ソースを載せておきます。

#module #deffunc Quicksort array data , int lops , int mod , local data_list1 , local data_list2 , local nest , local _nest , local loadmem_s , local loadmem_e , local loadmod , local data1cnt , local data2cnt , local zmod1 , local zmod2 , local _data1 , local _data2 , local errmod /* Quicksort V , I1 , I2 V=数値の入った配列要素 I1=比較数 I2=ソートモード(0=小さい順,1=大きい順) */ if looplev>500 :return -1 ;ネストが深すぎる dim data_list1,idx_mes ;比較1 dim data_list2,idx_mes ;比較2 nest=0 ;ネスト _nest=0 nest_max=1000 ;ネスト率のマックス値 dim loadmem_s,nest_max ;データー抜き取り開始位置 dim loadmem_e,nest_max ;データー抜き取り終点位置 dim loadmod,nest_max ;実行モード dim data1cnt,nest_max ;データーカウント1 dim data2cnt,nest_max ;データーカウント2 dim zmod1,nest_max ;データーカウント1 dim zmod2,nest_max ;データーカウント2 loadmem_s(0)=0 loadmem_e(0)=lops dim _data1,lops ;一時保存データー1 dim _data2,lops ;一時保存データー2 repeat if nest>_nest :_nest=nest if errmod :break ;title "ネスト:"+_nest+" "+nest+",["+cnt+"]" if nest<0 :break ;ネストが無くなったらループ脱出 switch loadmod(nest) case 0 _dmos=data(loadmem_s(nest)) ;始めの値を取得 zmod1(nest)=0 :zmod2(nest)=0 ;重複モード(-1=重複確定,0~=重複されていない) repeat loadmem_e(nest)-loadmem_s(nest)-1,1 ;始めの文字を抜かして計測 _cnt=cnt+loadmem_s(nest) if mod{ if data(_cnt)>_dmos{ if cnt>1{ if zmod1(nest)!=-1{ if zmod1(nest)!=data(_cnt){ zmod1(nest)=-1 ;重複確定 } } }else{ ;カウントが0の場合 zmod1(nest)=data(_cnt) } _data1(data1cnt(nest))=data(_cnt) data1cnt(nest)++ } else{ if cnt>1{ if zmod2(nest)!=-1{ if zmod2(nest)!=data(_cnt){ zmod2(nest)=-1 ;重複確定 } } }else{ ;カウントが0の場合 zmod2(nest)=data(_cnt) } _data2(data2cnt(nest))=data(_cnt) data2cnt(nest)++ } } else{ if data(_cnt)<_dmos{ if cnt>1{ if zmod1(nest)!=-1{ if zmod1(nest)!=data(_cnt){ zmod1(nest)=-1 ;重複確定 } } }else{ ;カウントが0の場合 zmod1(nest)=data(_cnt) } _data1(data1cnt(nest))=data(_cnt) data1cnt(nest)++ } else{ if cnt>1{ if zmod2(nest)!=-1{ if zmod2(nest)!=data(_cnt){ zmod2(nest)=-1 ;重複確定 } } }else{ ;カウントが0の場合 zmod2(nest)=data(_cnt) } _data2(data2cnt(nest))=data(_cnt) data2cnt(nest)++ } } loop _data1(data1cnt(nest))=_dmos ;始めの値を代入 data1cnt(nest)++ ;カウント増加 if nest_max<nest-2{ ;ネストが振り切った場合は個別に処理510超えるとエラー Quicksort _data1,data1cnt(nest),mod Quicksort _data2,data2cnt(nest),mod if stat=-1 :errmod=-1 :swbreak memcpy data , _data1 , data1cnt(nest)*4 , loadmem_s(nest)*4 memcpy data , _data2 , data2cnt(nest)*4 , loadmem_s(nest)*4 + data1cnt(nest)*4 nest-- swbreak } memcpy data , _data1 , data1cnt(nest)*4 , loadmem_s(nest)*4 memcpy data , _data2 , data2cnt(nest)*4 , loadmem_s(nest)*4 + data1cnt(nest)*4 loadmod(nest)++ ;モード変更 nest++ ;ネスト増加 if data1cnt(nest-1)>1 & zmod1(nest-1)=-1{ loadmem_s(nest)=loadmem_s(nest-1) loadmem_e(nest)=loadmem_s(nest-1) + data1cnt(nest-1) loadmod(nest)=0 data1cnt(nest)=0 data2cnt(nest)=0 }else{ nest-- } swbreak case 1 loadmod(nest)++ ;モード変更 nest++ ;ネスト増加 if data2cnt(nest-1)>1 & zmod2(nest-1)=-1{ loadmem_s(nest)=loadmem_s(nest-1) + data1cnt(nest-1) loadmem_e(nest)=loadmem_e(nest-1) loadmod(nest)=0 data1cnt(nest)=0 data2cnt(nest)=0 }else{ nest-- } swbreak default nest-- ;ネスト減少 swbreak swend loop if errmod :return errmod return 0 #global ;モジュールの終了 //----初期登録 #include "d3m.hsp" randomize //----ランダムに値を作成 lop=10000 ;数 dim data,lop repeat lop data.cnt=rnd(100) ;乱数 loop //----ソート前の状態を表示 sdim list repeat lop list+""+data.cnt+" , " loop mesbox list,640,240 //----ソート title "計測中" await time=d3timer() Quicksort data,lop,1 if stat :dialog "処理エラー",1,"エラー" _time=1.0*(d3timer()-time)/1000 title "掛かった時間"+strf("%.3f",_time) await //----ソート後の状態を表示 sdim list repeat lop list+""+data.cnt+" , " loop pos 0,240 mesbox list,640,240

少々長くなってしまいましたが、参考になれれば幸いです。



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