Mutable против неизменного двоичного обходе дерева в C++

я родом из фона Python и Haskell, поэтому, когда я должен был написать функцию для подсчета количества фильмов в бинарном дереве, я сделал это так:Mutable против неизменного двоичного обходе дерева в C++

int MovieTree::countMovieNodes(MovieNode* parent) 
{ 
    if (parent) 
    return countMovieNodes(parent->left) + countMovieNodes(parent->right) + 1; 
    else 
    return 0; 
} 

int MovieTree::countMovieNodes() 
{ countMovieNodes(root); }

Однако, используя файл заголовка, представленный в классе, я должен был сделать это следующим образом:

void MovieTree::countMovieNodes(MovieNode* parent, int* c) 
{ 
    (*c)++; 
    if (parent->left) 
    countMovieNodes(parent->left, c); 
    if (parent->right) 
    countMovieNodes(parent->right, c); 
} 

int MovieTree::countMovieNodes() 
{ 
    if (!root) return 0; 
    int c=0; countMovieNodes(root, &c); return c; 
}

Я понимаю преимущество первого над последней очень хорошо; каковы преимущества последнего над первым? Это связано с использованием памяти стека, не так ли?

источник

2016-03-09 René G

У меня также есть фон в не-C++, поэтому мне любопытно посмотреть, что здесь работает C++. Хороший вопрос. –

Вероятно, нет никаких преимуществ (и обратите внимание, что вы вызываете неопределенное поведение, потому что 'c' никогда не инициализируется до нуля). Вторая версия фактически займет больше места в стеке, потому что она должна выталкивать 'c' в стек. – Cornstalks

Интересно, почему наш профессор заставил нас так поступать тогда ... да. –

Я не вижу никакого преимущества во втором решении по сравнению с первым решением. На самом деле, я думаю, что это хуже первого. Первый - более чистый, с меньшим количеством строк кода, которые проверяют нулевые указатели.

Однако название вашего вопроса неверно. Второй - также рекурсивный. Это не итеративно.

источник

2016-03-09 05:14:51

Лучше ли новое название? –

@ RenéG, я думаю, это будет лучше, чем «Сравните два метода перемещения двоичного дерева для подсчета количества узлов» –

Одна вещь, которая делает плохой стиль в стиле C++, - это все же передача указателя ради эффекта вызова по ссылке, для которого в C++ у нас есть ссылка, которая делает код более понятным и менее подверженным ошибкам :

void MovieTree::countMovieNodes(MovieNode* parent, int& count) 
{ 
    ++count; 
    .... 
}

Возвращаясь к стилю рекурсии, стиль, который используется в последнем случае, может иметь более высокую производительность из-за оптимизации хвостового вызова.

Короче говоря, TCO избегает стека вызовов увеличиваться для каждого уровня рекурсивного вызова.

В прежней форме нам необходимо сохранить стек для каждого уровня рекурсивного вызова, чтобы мы могли получить результаты и выполнить дальнейшие вычисления (в вашем случае вычисление суммы счета в двух поддеревах).

Для последнего случая компилятор знает, что для второго вызова countMovieNodes не потребуется хранить стек (так как дальнейших вычислений не требуется), чтобы он мог повторно использовать текущий стек для выполнения рекурсивного вызова (только для второй звонок, если мое понимание правильное).

Однако в этом конкретном случае преимущество может быть не таким огромным, поскольку в последнем случае первый вызов countMovieNodes не может выиграть от TCO. Это все еще преимущество.

источник

2016-03-09 06:35:52

Mutable против неизменного двоичного обходе дерева в C++

ответ

Смежные вопросы