1

本当に深い再帰を使用する複雑なアルゴリズムがあります。特定のデータでスタック オーバーフローが発生するため、再帰なしで (ヒープ上の外部スタックを使用して) 書き直そうとしました。したがって、同じアルゴリズムの 2 つの変更があります。次に、いくつかのテストを実行したところ、再帰的な実装は別の実装よりもはるかに高速であることがわかりました。

誰か説明してくれませんか？これらの結果を議論することは、私の最後の大学プロジェクトの一部です (なぜ、ある実装が別の実装よりも非常に高速なのか)。スタックとヒープのキャッシングが異なるためだと思いますが、よくわかりません。

どうもありがとう！

編集

はい、コードがあります。アルゴリズムは C++ で書かれており、ツリー同形問題を解決します。2 つのノードを比較する 1 つのメソッドを除いて、両方の実装は同じです。比較は再帰的に定義されます。あるノードの子の 1 つが別のノードの対応する子よりも小さい場合、そのノードは別のノードよりも小さくなります。

再帰バージョン

char compareTo( const IMisraNode * nodeA, const IMisraNode * nodeB ) const {
    // comparison of same number of children
    int min = std::min( nodeA->getDegree( ), nodeB->getDegree( ) );
    for ( int i = 0; i < min; ++i ) {
        char res = compareTo( nodeA->getChild( i ), nodeB->getChild( i ) );
        if ( res < 0 ) return -1;
        if ( res > 0 ) return 1;
    }
    if ( nodeA->getDegree( ) == nodeB->getDegree( ) ) return 0; // same number of children
    else if ( nodeA->getDegree( ) == min ) return -1;
    else return 1;
}

非再帰的な実装

struct Comparison {
    const IMisraNode * nodeA;
    const IMisraNode * nodeB;
    int i;
    int min; // minimum of count of children

    Comparison( const IMisraNode * nodeA, const IMisraNode * nodeB ) :
    nodeA( nodeA ), nodeB( nodeB ),
    i( 0 ), min( std::min( nodeA->getDegree( ), nodeB->getDegree( ) ) ) { }
} ;

char compareTo( const IMisraNode * nodeA, const IMisraNode * nodeB ) const {
    Comparison * cmp = new Comparison( nodeA, nodeB );
    // stack on the heap
    std::stack<Comparison * > stack;
    stack.push( cmp );

    char result = 0; // result, the equality is assumed

    while ( !result && !stack.empty( ) ) { // while they are not same and there are nodes left
        cmp = stack.top( );

        // comparison of same children
        if ( cmp->i < cmp->min ) {
            // compare these children
            stack.push( new Comparison( cmp->nodeA->getChild( cmp->i ), cmp->nodeB->getChild( cmp->i ) ) );
            ++cmp->i; // next node
            continue; // continue in comparing on next level
        }
        if ( cmp->nodeA->getDegree( ) != cmp->nodeB->getDegree( ) ) { // count of children is not same
            if ( cmp->nodeA->getDegree( ) == cmp->min ) result = -1; // node A has lesser count of children
            else result = 1; 
        }
        delete cmp;
        stack.pop( );
    }

    while ( !stack.empty( ) ) { // clean stack
        delete stack.top( );
        stack.pop( );
    }

    return result;
}
4

2 に答える 2

2

非再帰コードは動的メモリ割り当てを行います (new を使用して明示的に、std::stack を使用して暗黙的に) が、再帰コードは行いません。動的メモリ割り当ては、非常にコストのかかる操作です。

スピードアップするには、ポインターではなく値を格納してみてください。

stack <Comparison> astack;

次に、次のようにコードします。

astack.push( Comparison( cmp->nodeA->getChild( cmp->i ), cmp->nodeB->getChild( cmp->i ) ) );

Comparison cp = astack.top();
于 2011-05-18T11:46:39.917 に答える
0

これは速度比較の質問には答えませんが、再帰的なソリューションのスタック サイズを増やす方法を提案します。

VC++ でスタック サイズ (デフォルト: 1MB) を増やすことができます: Visual Studio ヘルプで「stacksize」を検索してください。

そして、gcc でも同じことができます。そのまさにその質問についてSO の議論があります。

于 2011-05-18T11:58:15.323 に答える