Сравнение скорости между рекурсивной и нерекурсивной реализацией - PullRequest
Новая
       19

Сравнение скорости между рекурсивной и нерекурсивной реализацией

1 голос
/ 18 мая 2011

У меня сложный алгоритм, который использует действительно глубокую рекурсию. Поскольку существует переполнение стека некоторыми конкретными данными, я попытался переписать их без рекурсии (используя внешний стек в куче). Итак, у меня есть две модификации одного и того же алгоритма. Затем я выполнил несколько тестов и обнаружил, что рекурсивная реализация намного быстрее, чем другая.

Может кто-нибудь объяснить мне, пожалуйста? Обсуждение этих результатов является частью моего окончательного университетского проекта (почему одна реализация значительно быстрее другой). Я думаю, что это из-за разного кэширования стека и кучи, но я не уверен.

Большое спасибо!

EDIT

ОК, есть код. Алгоритм написан на C ++ и решает проблему изоморфизма деревьев. Обе реализации одинаковы, за исключением одного метода, который сравнивает два узла. Сравнение определяется рекурсивно - один узел меньше другого, если один из его потомков меньше соответствующего потомка другого узла.

Рекурсивная версия 

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;
}

Ответы [ 2 ]

2 голосов
/ 18 мая 2011

Ваш нерекурсивный код выполняет динамическое выделение памяти (явно с новым и неявным образом при использовании std :: stack), а рекурсивный - нет. Динамическое выделение памяти - чрезвычайно дорогая операция.

Чтобы ускорить процесс, попробуйте сохранить значения, а не указатели: 

stack <Comparison> astack;

затем код как: 

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

Comparison cp = astack.top();
0 голосов
/ 18 мая 2011

Это не отвечает на ваш вопрос сравнения скорости, а скорее предлагает способы увеличить размер стека для вашего рекурсивного решения.

Вы можете увеличить размер стека (по умолчанию: 1 МБ) в VC ++: поиск "stacksize" в справке Visual Studio.

И вы можете сделать то же самое в gcc. Существует ТАК обсуждение по этому вопросу .

...