Самый быстрый способ пройти произвольное дерево глубины для удаления? - PullRequest
Новая
       53

Самый быстрый способ пройти произвольное дерево глубины для удаления?

1 голос
/ 16 февраля 2011

Для своих собственных упражнений я пишу XML-парсер.Чтобы заполнить дерево, я использую обычный std::stack и помещаю текущий узел сверху, сделав его дочерним по отношению к последнему верхнему узлу (должен быть первым в глубину?).Так что теперь я делаю то же самое для удаления узлов, и я хочу знать, есть ли более быстрый путь.
Текущий код для удаления: 

struct XmlNode{
    // ignore the rest of the node implementation for now
    std::vector<XmlNode*> children_;
};
XmlNode* root_ = new XmlNode;

// fill root_ with child nodes...
// and then those nodes with child nodes and so fort...

std::stack<XmlNode*> nodes_;
nodes_.push(root_);
while(!nodes_.empty()){
    XmlNode* node = nodes_.top();
    if(node->children_.size() > 0){
        nodes_.push(node->children_.back());
        node->children_.pop_back();
    }else{
        delete nodes_.top();
        nodes_.pop();
    }
}

Работает совершенно нормально, но выглядит вроде медленно.Так есть ли более быстрый / лучший / более распространенный способ сделать это?

1 Ответ

2 голосов
/ 16 февраля 2011

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

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

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

Итерировать - это человек;повторять, божественно.:)

...