Возврат рекурсивных троичных пятен
примите этот после функции:
int binaryTree::findHeight(node *n) {
if (n == NULL) {
return 0;
} else {
return 1 + max(findHeight(n->left), findHeight(n->right));
}
}
Довольно стандартный рекурсивный treeHeight функция для данного дерева двоичного поиска binaryTree. Теперь, я помогал другу (он берет курс алгоритмов), и я столкнулся с некоторой странной проблемой с этой функцией, которую я не мог 100% объяснять ему.
С тем, чтобы макс. быть определенным как max(a,b) ((a)>(b)?(a):(b)) (который, оказывается, макс. определение в windef.h), рекурсивная функция волнуется (она выполняет что-то как n^n времена, где n древовидная высота). Это, очевидно, делает проверку, что высота дерева с 3 000 элементов берет очень, очень долго.
Однако, если макс. определяется через шаблонную обработку, как std это, все хорошо. Так использование std::max решенный его проблема. Я просто хочу знать почему.
Кроме того, почему делает countLeaves функция хорошо работает, с помощью той же программной рекурсии?
int binaryTree::countLeaves(node *n) {
if (n == NULL) {
return 0;
} else if (n->left == NULL && n->right == NULL) {
return 1;
} else {
return countLeaves(n->left) + countLeaves(n->right);
}
}
Это потому что в возврате троичной функции, значений a => countLeaves(n->left) и b => countLeaves(n->right) были рекурсивно дважды названы просто, потому что они были результантами?
Спасибо!
На вопрос ответили ниже
Я просто хотел связать некоторую литературу по предмету для дальнейшего использования:
http://www.boostpro.com/tmpbook/preprocessor.html
http://msdn.microsoft.com/en-us/library/z3f89ch8.aspx
Основное различие между этими двумя реализациями теми, чтобы быть:
#define max(i, j) (((i) > (j)) ? (i) : (j))
по сравнению с
template T max (T i, T j) { return ((i > j) ? i : j) }
Спасибо всем!
4 ответа
Макросы расширяются препроцессором, прежде чем компилятор увидит код. Это означает, что, например, макроданные могут быть оценены более одного раза.
С вашим макросом вы получите что-то похожее на:
int binaryTree::findHeight(node *n) {
if (n == NULL) {
return 0;
} else {
return 1 + (findHeight(n->left) > findHeight(n->right)) ? // call once...
findHeight(n->left) : findHeight(n->right); // and ouch
}
}
Как вы можете видеть, он будет оценивать обе функции, а затем еще одно дополнительное время. Вот почему макросы могут быть злом.
Макрос можно отключить, определив NOMINMAX перед включением заголовков Windows. Затем используйте функцию в
Если он должен использовать макрос, ему придется хранить вычисления в переменной:
int binaryTree::findHeight(node *n) {
if (n == NULL) {
return 0;
} else {
const int leftHeight = findHeight(n->left);
const int rightHeight = findHeight(n->right);
return 1 + max(leftHeight, rightHeight);
}
}
С помощью функции каждый вызов будет вычисляться prior для вызова функции. То есть это чем-то похоже на предыдущий блок кода. Он вычисляет аргументы функции, получает результаты, а затем передает их в функцию std::max. Повторных оценок нет.
лучшим вариантом было бы объявить функцию со следующей подписью:
int max(int, int)
Это предотвратит рекурсивное расширение макроса.
Это из-за определения макс. Вы делаете 3 вызова findHeight () вместо 2.
Макрос max вычисляет аргументы дважды - и поскольку ваш аргумент является рекурсивным вызовом функции, это, вероятно, является источником проблемы с перфомансом.