再帰処理を非再帰処理に書き換える場合

質問

TreeViewなど階層数・要素数が動的に変化し
それらすべての要素に対して一括処理をするといった
本質的に、真に再帰的な操作をしなければならないような場合なのですが

状況説明のため少ないメンバに絞ると
こんなノードの抽象クラスがあるとします

namespace TreeView { namespace Node { class Super; }}
class MemoryMap;

class TreeView::Node::Super {

protected:

typedef Super* PTR;
PTR next, child;

Super();
virtual ~Super();
virtual Void Save( MemoryMap* ) const = 0;

public:

static Void Release( PTR* pp );
template <class T> static Void Release( T** pp ){ Release( (PTR*)pp ); }

};

んで

using TreeView::Node::Super;

Super::Super() : next(NULL), child(NULL){}
Super::~Super(){}

こんな感じにしといて、任意に追加、挿入しときますと

その後一括解放のためのReleaseの本体は

Void Super::Release( PTR* pp ){

for ( PTR p; p = *pp; ){
if ( p->child ) Release( &p->child );
*pp = p->next;
delete p;
}

}

こんな感じで、再帰を使えば結構簡単に書けると思うのですが

・・・利用法から考えてよっぽどないとは思うのですが
やはりそこは一応
スタックオーバーフローの危険性をコードサイドから積極的に
ほぼ回避しておくべきと考えると

階層数の上限を設けておいて
最低、追加・挿入時には、それをチェックする

というのが良いかと思うのですが

仮に別のアプローチで
こういった類の再帰（もっと複雑な場合のが多いかも）を非再帰関数に直すには
やっぱり

・goto文
・自分でヒープ上などに作る疑似スタック
・そのスタックに、gotoのジャンプ位置を保存できるenumとかの定数フラグ

などを使用せざるを得ない
って感じになってくるんでしょうかね？

回答No.1

kmee · ベストアンサー

別にgotoは使わなくてもいいんじゃないですか?
PTRをスタックするだけで。
ループの繰り返し

void Super::Release( PTR* pp ){
std::stack<PTR> sp; // スタックの準備
sp.push(*pp) ; // 次に処理したいノードをスタックに積む
// 関数での引数に相当。

while ( ! sp.empty() ){ // スタックが空→終了
// トップの内容を見る。スタックは変化しない
// 関数で引数の受け取りに相当
PTR p = sp.top() ;

if( p == NULL ) {
// 関数でのreturnに相当
sp.pop() ; // topは処理済みになるのでスタックから削除
continue ; // 次へ
}

if ( p->child ) { // 子があったら、
sp.push(p->child) ;// 子をスタックへ積んで
continue ; // 次へ:再帰呼び出しに相当
}

sp.push(p->next); // 次の候補であるp->nextをスタックに積む

*pp = p->next;
delete p;

sp.pop() ; // topは処理済みになるのでスタックから削除

}
}

お礼

どうもありがとうございます♪

なるほど、この場合だとループとcontinue文で出来そうですね。

ただ、このコードでは
実際やってみれば分かりますが

namespace Debug {
void f(int i);
void f(const void* );
}

class AAA : Super { //実験を楽にするためだけなので超適当

void Save( MemoryMap* ) const override {}
public:
AAA*& Next() const { return (AAA*&)next; }
AAA*& Child() const { return (AAA*&)child; }
int i;
AAA(int a) : i(a){}
~AAA(){ Debug::f(i); }

};

namespace Debug { //各状況チェック
void f(int i){
TCHAR c[20];
_stprintf_s(c,20,_T("%d\r\n"),i);
OutputDebugString(c);
}
void Debug::f( const Void* p ){
TCHAR c[100];
_stprintf_s(c,100,_T("%08p\r\n"),p);
OutputDebugString(c);
}
}

で、基底クラスのデストラクタは

Super::~Super(){ static int num=0; Debug::f(++num); }

にかえ

AAA* base = new AAA(423);
base->Next() = new AAA( 5464 );
base->Child() = new AAA( 5555 );
base->Next()->Child() = new AAA( 777 );
base->Next()->Next() = new AAA( 888 );
base->Next()->Child()->Next() = new AAA( 1111 );

Super::Release( &base );
Debug::f(base);

としてみると
質問文で私が作った再帰版では

5555
1
423
2
777
3
1111
4
5464
5
888
6
00000000

となり、最後にbaseも自動的にNULLに変わって
解決ですが

kmeeさんご提示のコードでは

5555
1

までで死にます。
原因は、NULLに直らないことによる2重deleteです。

私が作った再帰版ではポインタポインタを引数として渡しているので
超お手軽な表記になっていますが

そこを考慮して簡易的に書きなおしてみると

#include <stack>

void Super::Release( PTR* pp ){

std::stack<PTR*> sp;
sp.push(pp);

for ( PTR p; !sp.empty(); ){
p = *sp.top();
if ( !p ){ sp.pop(); continue; }
if ( p->child ){ sp.push( &p->child ); continue; }
*sp.top() = p->next;
delete p;
}

}

こんなかんじですかね。
これなら

5555
1
423
2
777
3
1111
4
5464
5
888
6
00000000

で、期待どおりです。
（たぶんないとは思いますが、ややこしいコードなので、気づいてないとこでバグってる箇所があるかもしれませんｗ　見つかったら教えていただけるとありがたいです。）

ただ
今まで書いたコードについて
全て当てはまりそうかどうか
パフォーマンス、メンテなど含めgoto文とcontinue
どっちが良いかなど

まだ精査したいことがいくつかあるので
しばらくお待ちください。

補足

追加報告です。

＞原因は、NULLに直らないことによる2重deleteです。

あれ、正確にはdelete済みのやつのメンバへのアクセス違反でしたかね
そこんとこ失礼しました。
（意味的に再帰になるコードは、どう組んでも分かり辛いですねｗ）

今のところ

親よりchildの方の処理を先に行う

childより親の方の処理を先に行う

の2パターンあり得るというだけで

ノード操作関連ではcontinueとループを使った方法でも問題なさそうと分かりました。

ただ、パフォーマンス的には
10回程度やって平均が

0.002866971356706sec(stack&gotoなし)
対
0.001327178776805sec(再帰)

ぐらいになってるような状況でした。

そこで、まだコードを出していないgotoだとどうなるかですが

std::stackの微妙な仕様が若干煩わしかったので
ポインタの出し入れのみと拡張を簡単に行う自作スタックを作ってやってみました。
（キャッシュの連続性を求めてポインタの配列を動的に確保するという形で、拡張が必要になったら拡張のみは行い、縮小はせず、デストラクタで一括解放）

なお、書き忘れてましたが、プリコンパイル済みヘッダで

typedef VOID Void;
typedef size_t szt;
typedef BOOL Bool;

こんなことをやってます。

///////SimpleStack.h//////

#pragma once

class SimpleStack {

typedef Void* VP;

VP* data;
szt len, cur;
const szt cycle; //再確保が必要な場合のサイクル（要素数）

Void PushVP( VP );
bool PopVP( VP* pp ){
if (!cur) return false;
*pp = data[--cur];
return true;
}

public:

SimpleStack( szt cycle_ = 4 );
~SimpleStack();

template < typename T > Void Push( T* p ){ PushVP( (VP)p ); }
template < typename T > bool Pop( T** pp ){ return PopVP( (VP*)pp ); }

};

///////SimpleStack.cpp//////

#include "StdAfx.h"
#include "SimpleStack.h"

SimpleStack::SimpleStack( szt cycle_ ) : len(0), cur(0), cycle(cycle_) {}
SimpleStack::~SimpleStack(){ if (len) free( data ); }

Void SimpleStack::PushVP( const VP p ){

if ( cur == len ){

const szt newlen = len + cycle;
VP* t = (VP*)malloc( sizeof( VP ) * newlen );

if ( len ){
memcpy( t, data, sizeof(VP)*len );
free( data );
}

data = t;
len = newlen;

}

data[cur++] = p;

}

これで、Push(ポインタ);で押し込み
Pop(&ポインタ);で拾いつつ、戻り値チェックでスタックが空かどうか分かります。

そうすると、gotoを使う場合、一例としてはこうなります。

Void Super::Release( PTR* pp ){

SimpleStack sp;
PTR p;

while ( p = *pp ){
if ( p->child ){ sp.Push(pp); pp = &p->child; continue; }
RELEASED_ALL_CHILDREN: //ここに来る時にはpの子ノードは解放済み
*pp = p->next;
delete p;
}

if ( sp.Pop(&pp) ){ p = *pp; goto RELEASED_ALL_CHILDREN; }

}

なんと、コード量で言うとそんなには変わりがないって感じでした。

でもって、この場合やっぱりジャンプ箇所一つだけなので、フラグはなくていいですね。

そして、Push,Pop及びそれに伴うチェックがchildがらみの個所のみなので
それほど可読性も低くないと思われます。

速度ですが

0.002866971356706sec(stack&gotoなし)
0.001327178776805sec(再帰)
0.001447426842494sec(stack&goto)

こんなもんでした。

これは捨てがたいですｗ

自前のスタックでも
思ったよりも簡単かもしれない、という事が分かりましたが

その他のアイデアや突っ込みどころがありましたら是非教えてください。

回答No.2

Tacosan

1つ気になったんだけど, malloc+memcpy と realloc ってどっちが速いんだろう.

大差ないとは思うけど.

お礼

ありがとうございます♪

そう言う突っ込みも待ってたとこですｗ
まさにちょうどって感じです。

reallocはいろんなサイト見てたら
疑念を抱く表記がいくつかヒットするので
後でもし勘違いとかで
バグを作りこんでて…とかなると恐ろしいので
使用を避けていた、というのもありますが
そもそも、頻繁に確保解放を行う可能性があるならば
それは恰好の改善ポイントとなり得ます。

といいますのも

例えばもしgotoなりcontinueなりを使って

再帰関数でなくした場合

ツリービューの再描画
virtual void Draw( HDC ) const = 0;

とかこんな感じになり得るであろうものが
たまたまユーザーのウインドウ操作とかによって
( バックバッファを別途用意した描画省略をしてない限り )

場合によっては猛スピードで呼び出される、場合もないことはないとかんがえられるわけですね。

で、ついでに言うと
下で書いたAAAクラスのコードは実験のために外から自由にいじれるようになってるのですが
実際には直触りするのはなるべく避けたいわけです。

なのでどうやってbaseのポインタを管理するかですが

ここで、もうひとつTreeBaseクラスを作りましょう。

namespace TreeView { namespace Node {
class Super;
class TreeBase;
}}

class SimpleStack;

class TreeView::Node::TreeBase {

Super* base;
SimpleStack* stack;

public:

TreeBase();
~TreeBase();

Bool Load( LPCTSTR );
Void ReleaseAll();

};

そんで、TreeView::Node::Superのほうをこうしておきます。

class SimpleStack;

class TreeView::Node::Super {

friend class TreeBase; ////これでほとんどのメンバをprivateにできます。

typedef Super* PTR;
typedef const Super* CPTR;

virtual Void Save( MemoryMap* ) const = 0;

static void Release( SimpleStack*, PTR* ); //TreeBaseのstackを受け取る
template < class T > static void Release( SimpleStack* sp, T** pp ){ Release( sp, (PTR*)pp ); }

PTR next, child; //もし継承先から使わなければこれもprivateでOK

protected:

Super();
virtual ~Super();

};

で、実験として

後はこんな感じに

using TreeView::Node::TreeBase;

TreeBase::TreeBase() : base(null), stack(null) { stack = new SimpleStack(8); }
TreeBase::~TreeBase(){ Super::Release( stack, &base ); delete stack; }

Bool TreeBase::Load( LPCTSTR const filepath ){

//ただし実験なのでfilepathは無視w

//baseの扱いは、実際にはReleaseと同じようにSuperへ委託する可能性が高いです。

base = new AAA(423);
base->next = new AAA( 5464 );
base->child = new AAA( 5555 );
base->next->child = new AAA( 777 );
base->next->next = new AAA( 888 );
Super* p = base->next->child->next = new AAA( 1111 );

return TRUE;

}

Void TreeBase::ReleaseAll(){ Super::Release( stack, &base ); }

で、こうやっておくと

SimpleStackに

Void Reset(){ if (len){ free( data ); len = cur = 0; } }

こんなメンバを追加してやることで

TreeBaseの裁量次第で
SimpleStackの確保領域は、遅延解放が出来るようになりますから

かなり自由にコントロール出来るのです。

もちろん、SimpleStackの方をもっと書き換えれば
メモリではなくメモリマップドファイルとかにすることも可能でしょう

ただ、人間が手で操作するツリービューを念頭に置いているので

階層が例えば1000…も行くことはまずあり得ないというほど、考えにくいですが

仮にそこまでいったとしても、ポインタ4バイトなら4KB、8バイトでも8KB程度です。この程度だと、ビットマップのバックバッファ持ってたら一瞬でひっくり返りますし、ツリービューはアプリ中にそうそう何十個も作るようなものでもないので

そう言う点はそれほどの心配はない気もします。

補足

その後もいろんなパターンでやってみましたが

SimpleStackのメンバに

szt GetCur() const { return cur; }

template < typename T > T& Last(){
return (T&)data[cur-1];
}

Void Pop(){ if (cur) --cur; }

を追加し

void Super::Release( SimpleStack* const sp, PTR* pp ){

sp->Push(pp);

for ( PTR p; sp->GetCur(); ){
p = *sp->Last<PTR*>();
if ( !p ){ sp->Pop(); continue; }
if ( p->child ){ sp->Push( &p->child ); continue; }
*sp->Last<PTR*>() = p->next;
delete p;
}

}

と、非goto非再帰にしてみると

どうも下のgoto版より１～２％ほどの差で速いような気がしなくもないです。
ムラがあるので実際には気のせいかもしれません（アセンブリは未確認です）が

ただ、少なくとも、全体像としては、速い順に

スタック（再帰関数）> SimpleStack(goto or continue) > std::stack( continue )

は安定している感じです。
場合により肉迫はし、或いは並んだり誤差で上回ったりすることもありますが、平均するとやはり積み上げ・取り出し作業がいる限りは、ヒープでスタックに勝つのは無理かもしれません。

ついでに、自分で下に「1000階層」という具体的な数字を出してみたときに
「コントロールのツリービューとしての」その異常さを意識したのでｗ

今回の件に関しては、単純に

＞階層数の上限を設けておいて
＞最低、追加・挿入時には、それをチェックする

の方が結局のところ良いかもしれません。（ええ～ｗ）

各再帰関数の引数は
必要物をパックした構造体のポインタ１つか、場合により0にする(非staticでthisポインタだけで十分とかの場合）など、最小限にしといて
100階層以内とかで適当に調整すれば十分でしょうｗ

現状でもその時だけSimpleStackを使えば、GetCur関数を使って非再帰関数で最大階層数をチェックできます。

もちろん、コントロールのツリービューではなく
もっと階層数を深く持つ可能性のあるものであれば
SimpleStack（か、その時の状況に応じてもっと最適化した専用スタック）を使う、という事になると思われます。

今回はそういう事で、解決としておきましょう。

お二方、どうもありがとうございました♪