|
 |
|
|
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がサブルーチンの呼び出し元を覚えきれないときエラーになります。」という事らしいですが、
エラーを出さないようにうまくプログラムが組めるでしょうか？
| |
|
|
2014/12/17(Wed) 20:48:46|NO.66494
コードをザッと呼んだだけですが、再帰しようとしていますよね...?
#deffuncで定義したルーチンへのジャンプはgosubによるサブルーチンジャンプと大体一緒です。
命令の中から自身を何回も再呼び出していてはネストが深くなって、HSPではアウトになります。
提示されたコードでは、sublev (サブルーチンのネストレベル)が511を超えた時点で死んでいました。
再帰を使わない方法に変更する必要があります。
|
|
|
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 △----------------------------*//
| |
|
|
2014/12/18(Thu) 20:36:08|NO.66498
返信遅くなりすみません。
ありがとうございます！ とても参考になりました！
ちょっと理解が難しいですが、なんとかできそうです。
解決済みにしておきます。
|
|
|
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
少々長くなってしまいましたが、参考になれれば幸いです。
| |
|
ソートプログラムでスタック領域のオーバーフロー
