- ベストアンサー
再帰処理を非再帰処理に書き換える場合
- 再帰処理を非再帰処理に書き換える際の方法や注意点について説明します。
- 再帰処理を非再帰処理に書き換える場合、階層数の上限を設けることが重要です。
- 非再帰処理に書き換える際には、goto文や疑似スタックなどを使用する必要があることがあります。
- LongSecret
- お礼率96% (146/151)
- C・C++・C#
- 回答数2
- ありがとう数2
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
その他の回答 (1)
- Tacosan
- ベストアンサー率23% (3656/15482)
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（か、その時の状況に応じてもっと最適化した専用スタック）を使う、という事になると思われます。 今回はそういう事で、解決としておきましょう。 お二方、どうもありがとうございました♪
関連するQ&A
- （構造体）ループ条件のscanf文が処理されない！？
ループのscanf文を入力していないのに勝手にループの中に入って処理をしています。なぜでしょうか？ #include<stdio.h> #include<malloc.h> #include<process.h> typedef struct node{ struct node *left; char name[20]; int age; struct node *right; }NODE; NODE *memalloc(void); void main(void) { NODE *head, *p, *old; /*ダミーノード作成*/ p = memalloc(); head = p; p -> left = p; p -> right = p; old = head; p = memalloc(); printf("名前 年齢入力 >"); scanf("%s, %d", p -> name, &p -> age); old -> left = p; old -> right = p; p -> left = old; p -> right = old; while(p = memalloc(), old = p, printf("名前 年齢入力 >"), scanf("%s, %d", p -> name, &p -> age) != EOF){ printf("確認\n"); old -> right = p; p -> left = old; head -> left = p; p -> right = head; } p = head -> right; while(head -> left != p -> right){ printf("名前:%20s 年齢:%5d\n", p -> name, p -> age); p = p -> right; } } NODE *memalloc(void) { NODE *ptr; if((ptr = (NODE *)malloc(sizeof(NODE))) != NULL){ return ptr; } printf("\n動的メモリ割当に失敗しました。\n"); exit(1); return(0); }
- ベストアンサー
- C・C++・C#
- 木構造と再帰
1週間考えましたが分かりません 正の整数mとn(n <= 9)を入力して、1以上n以下のn個の数字を自由に組み合わせて構成されるm桁の数字列のすべてを表示するJavaのプログラムである。 以下に、本プログラムの動作例を示す。 桁数を入力してください 4(入力) 1以上9以下の整数を入力してください 2(入力) 1111 1112 1121 1122 1211 1212 1221 1222 2111 2112 2121 2122 2211 2212 2221 2222 このとき、本プログラムのsetNode()メソッドの中身を記述してプログラムを完成させよ。ただし、setNodeメソッドは再帰的手続きとし、プログラムのほかの部分を変更(追加、削除を含めて)しないこと。 import java.io.*; class Node { private int value; private Node child[]; public void setNode(int value, int digit, int range); { //ここに解答 } public int getValue() { return value; } public Node getChild(int index) { return child[index]; } } class NumberString { static int range; public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); System.out.plintln("桁数を入力してください"); String str1 = br.readLine(); int digit = Integer.parseInt(str1); System.out.plintln("1以上9以下の整数を入力してください"); String str2 = br.readLine(); range = Integer.parseInt(str2); Node root = new Node(); root.setNode(0, digit, range); for(int i = 0;i < range; i++){ printNumber(root.getChild(i), digit, ""); } } private static void printNumber(Node n, int digit, String str) { if(digit == 1){ System.out.plintln(str + n.getValue()); return; } for(int i = 0;i < range;i++){ printNumber(n.getChild(i), digit - 1, str + n.getValue()); } } }
- ベストアンサー
- Java
- (構造体)双方向連結リストの作成！
ダミーノードを先頭に、双方向連結リストを作成したいのですがなかなかうまくできません。とりあえず、ダミーノード無しのものはなんとか出来ましたが、循環連結がうまくいっていない次第です。 どうかお力添え願います。 #include<stdio.h> #include<malloc.h> #include<process.h> typedef struct node{ struct node *left; char name[20]; int age; struct node *right; }NODE; NODE *memalloc(void); void main(void) { NODE *head, *tail, *p; tail = NULL; while(p = memalloc(), printf("名前 年齢入力(Ctrl + Zで終了)＞"), scanf("%s %d", p -> name, &p -> age) != EOF){ p -> left = tail; tail = p; } p = tail; head = NULL; while(p != NULL){ p -> right = head; head = p; p = p -> left; } head -> left = tail; p = head; printf("リスト表示\n"); while(p != NULL){ printf("名前:%20s 年齢:%5d\n", p -> name, p -> age); p = p -> right; } } NODE *memalloc(void) { NODE *ptr; if((ptr = (NODE *)malloc(sizeof(NODE))) != NULL){ return ptr; } printf("\n動的メモリ割当に失敗しました。\n"); exit(1); return 0; }
- ベストアンサー
- C・C++・C#
- shared_ptr クラスについて
shared_ptrクラスを使いたいのですが、使えません、どうしてでしょうか？ソースはこれです。 #include<iostream> #include <string> #include <fstream> #include<memory> using namespace std; class SMonster{ string name; int power; public: SMonster(); SMonster(int p); ~SMonster(){ }; void SetPower(int p); int GetPower(SMonster& t)const; void walk(const string& str); int GetPoint(void)const; }; class B {}; class D : public B {}; int main(void) { shared_ptr<D> sp0(new D); SMonster m(200); SMonster n(100); std::cout<<m.GetPower(m)<<std::endl; std::cout<<n.GetPower(n)<<std::endl; ShowWindow(10); }
- ベストアンサー
- C・C++・C#
- 2つのvisitorでデータを処理する
class Node{ public: virtual void* accept(Visitor* v)=0; //PPVisitor用 virtual void* accept(Visitor* v, void* obj)=0; //IRVisitor用 }; 上記の派生クラス(データ)を、Visitorクラスから派生したPPVisitorとIRVisitorで処理しようと思っています。 Visitorクラスには各データに対するvisit関数を仮想関数として宣言しているのですが、この方法だとPPVisitorとIRVisitorが互いのvisit関数を定義しなければ抽象クラスになってしまいます。 Visitorクラスからそれぞれを呼び出せるようにしつつPPVisitorとIRVisitorを分離する方法は無いでしょうか。 自身のvisitorではないvisit関数は何もしない関数として定義するという方法で一応動きましたが、あまり良くない気がします。
- ベストアンサー
- C・C++・C#
- あるクラスの派生クラスと、その他の型で処理を振り分
■環境 Windows7 Visual Studio 2010 Visual C++（C++11） 大抵の型は共通処理を行いたいが、ある特定の型だけは特別な処理を行いたい、 そんなケースでは、テンプレートの明示的な特殊化が利用出来るかと思います。 しかし、『ある特定の抽象クラスの派生クラス』だけは特別な処理を行いたい、 これを実現するには、どのようにするのがよろしいでしょうか？ 以下のコードは、意図した通りに動作しません。 良い方法があれば、ご教授いただけますでしょうか？ // 抽象クラス class AbstractClass { public: virtual void MustOverides() = 0; }; // 派生クラス class ChildClass : public AbstractClass { public: virtual void MustOverides(){}; }; template<typename AnyType> void CommonFunc(const AnyType& target) { // 呼ばれる } template<> void CommonFunc<AbstractClass>(const AbstractClass& target) { // 呼ばれない、呼ばせたい } void CommonFunc(AbstractClass& target) { // 呼ばれない、呼ばせたい } void CommonFunc(const AbstractClass& target) { // 呼ばれない、呼ばせたい } void main() { ChildClass Child; CommonFunc(Child); } よろしくお願いいたします。
- 締切済み
- C・C++・C#
- new演算子のオーバーロードについて
#include <stdio.h> #include <windows.h> class MyNew { public: void* ptr; MyNew( void* p ) { ptr = p; } void* MyNew::operator new( size_t size ) { printf("new-\n"); return malloc( size ); } void MyNew::operator delete( void* ptr ) { printf("delete-\n"); free( ptr ); } }; void main( void ) { MyNew p = new int; } クラスのメモリ確保をnew演算子のオーバーロードを用いて書いてみたのですがオーバーロードしたnew演算子が呼ばれません。 なぜでしょうか？ /** VisualStdio2005コンソールアプリケーション WindowsXP */
- ベストアンサー
- C・C++・C#
- boost::shared_ptr::getにて
こんにちは。 C++で書かれたプログラムの保守をしています。 以下のような感じで書かれたクラスがあります。 class Foo { public : Foo(){} ; virtual ~Foo(){} ; void Set( boost::shared_ptr< int > pValue ) { _pValue = pValue.get() ; } protected : void* _pValue ; } ; このクラスから _pValue を再び boost::shared_ptr< int > にして取得するにはどうしたら良いのでしょうか？ 強引に、 boost::shared_ptr< int > Get( void ) { boost::shared_ptr< int > temp ; temp.reset( (int*)_pValue ) ; ｒeturn temp ; } とやっても案の定ダメでした。 void* _pValue の部分はいろいろ使われていて変更できません。 何かよい手段はないものでしょうか？
- ベストアンサー
- C・C++・C#
- 線形リストのコードでどーしても理解できない個所があります。
線形リストのコードでどーしても理解できない個所があります。 (以下、コード部分) typedef struct __node { char name[20]; char tel[16]; struct __node *next; } Node; typedef struct { Node *head; Node *tail; } List; Node *AllocNode(void) { return ((Node *)calloc(1, sizeof(Node))); } /*--- 新たに生成したノードを先頭へ挿入 ---*/ void InsertNode(List *list, const char *name, const char *tel) { Node *ptr = list->head; list->head = AllocNode(); strcpy(list->head->name, name); strcpy(list->haed->tel, tel); list->head->next = ptr; } /*--- pが指すノードの直前にノードを挿入 ---*/ void PutNodeP(List *list, Node *p, const char *name, const char *tel) { if (p == list->head) InsertNode(list, name, tel); else { Node *temp = AllocNode(); if (p == list->tail) list->tail = temp; else *temp = *p; strcpy(p->name, name); strcpy(p->tel, tel); temp->next = p; } } 上の29行目以降の≪pが指すノードの直前にノードを挿入≫についてです。 if文部分については理解できますが、else文部分について、何をやっているのかわからないです。Ｃの基本的な部分（ポインタも含めて）については充分に理解しているつもりです。 どなたか御教授頂けないでしょうか。 長々と書いてしまいましたがよろしくお願いします。
- 締切済み
- C・C++・C#
- JavaでのポリモーフィズムをC#で表現するには？
最近ふと気になったのですが、以下のJavaのコードと等価なコードは、C#ではどのように書けばよいのでしょうか？ --- public Class1 { public void foo() { System.out.println("Class1"); } } public Class2 extends Class1 { public void foo() { System.out.println("Class2"); super.foo(); } } public Class3 extends Class2 { public void foo() { System.out.println("Class3"); super.foo(); } } --- 気分的には次のように書きたいところなのですが、このように書くとコンパイルエラーになってしまいます。 --- public class Class1 { public virtual void foo() { Console.WriteLine("Class1"); } } public class Class2 : Class1 { public virtual override void foo() { Console.WriteLine("Class2"); base.foo(); } } public class Class3 : Class2 { public override void foo() { Console.WriteLine("Class3"); base.foo(); } } --- 調べた限り、ストレートな方法で記述することは不可能だと感じたのですが、やはりそうなのでしょうか？ そうだとしたら、現実にこのように記述する必要が生じた場合には、どのように対処すればよいのでしょうか？ また、C#の言語仕様はなぜこのようになっているのでしょうか？（VMの仕組みも関係あるのでしょうか？） 知っていらっしゃる方がいましたら、教えていただけると助かります。
- ベストアンサー
- その他（プログラミング・開発）
お礼
どうもありがとうございます♪ なるほど、この場合だとループと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) こんなもんでした。 これは捨てがたいですｗ 自前のスタックでも 思ったよりも簡単かもしれない、という事が分かりましたが その他のアイデアや突っ込みどころがありましたら是非教えてください。