StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POSpeed comparison between recursive and nonrecursive implementation
text
Body
copied!<p>I have an complex algorithm which uses really deep recursion. Because there is stack overflow with some specific data I have tried to rewrite it without recursion (using external stack on the heap). So I have two modifications of the same algorithm. Then I have performed some tests and I have found out that recursive implementation is much time faster than another one. </p> <p>Can someone explain it to me, please? It is part of my final university project to discuss these results (why is one implementation highly faster than another one). I think that it is because of different caching of stack and heap but I am not sure.</p> <p>Thanks a lot!</p> <hr> <p><strong>EDIT</strong></p> <p>OK, there is a code. The algorithm is written in C++ and solves tree isomorphism problem. Both implementations are same except one method which compares two nodes. The comparison is defined recursively - one node is lesser than another if one of it's children is lesser than corresponding child of another node.</p> <p>Recursive version</p> <pre><code>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; } </code></pre> <p>Nonrecursive implementation</p> <pre><code>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; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload