Самый быстрый способ подсчитать / получить доступ к детям DOMNode с помощью Xerces C++

Question

Я пытаюсь выяснить самый быстрый способ подсчета количества дочерних элементов объекта DOMNode Xerces C++, поскольку я пытаюсь оптимизировать производительность приложения Windows, которое использует DOMParser Xerces 2.6. Кажется, большую часть времени тратят на подсчет и доступ к детям. Наше приложение должно выполнить итерацию каждого узла в документе, чтобы присоединить к нему данные, используя DOMNode::setUserData(), и мы изначально использовали DOMNode::getChildNodes(), DOMNodeList::getLength() и DOMNodeList::item(int index) считать и получать доступ к детям, но это сравнительно дорогие операции.

Значительное улучшение производительности наблюдалось, когда мы использовали другую идиому вызова DOMNode:: getFirstChild() для получения первого дочернего узла и вызова DOMNode::getNextSibling() для доступа к дочернему элементу по определенному индексу или для подсчета числа братьев и сестер первый дочерний элемент, чтобы получить общее количество дочерних узлов.

Однако getNextSibling () остается узким местом на нашем этапе анализа, поэтому мне интересно, есть ли еще более быстрый способ обхода и доступа к дочерним элементам с помощью Xerces.

Спасибо

Answer 1

Проблема с DOMNodeList состоит в том, что это действительно довольно простой список, поэтому такие операции, как length и item(i) иметь расходы на O(n)как можно увидеть в коде, например здесь для длины:

XMLSize_t DOMNodeListImpl::getLength() const{
    XMLSize_t count = 0;
    if (fNode) {
        DOMNode *node = fNode->fFirstChild;
        while(node != 0){
            ++count;
            node = castToChildImpl(node)->nextSibling;
        }
    }

    return count;
}

Таким образом, DOMNodeList не следует использовать, если не ожидается, что DOM-дерево будет изменено во время итерации, потому что доступ к элементу в O(n) таким образом делая итерацию O(n^2) операция - ожидающая катастрофа катастрофа (т.е. достаточно большой xml-файл).

С помощью [DOMNode::getFistChild()][2] и DOMNode::getNextSibling() достаточно хорошее решение для итерации:

DOMNode *child = docNode->getFirstChild();
while (child != nullptr) {
    // do something with the node
    ...
    child = child->getNextSibling();
}

Что происходит, как ожидалось в O(n^2).

Можно также использовать [DOMNodeIterator][3], Но для того, чтобы создать его право DOMDocument требуется, что не всегда под рукой, когда требуется итерация.

Answer 2

Да, вскоре после публикации я добавил код для хранения и управления количеством дочерних элементов для каждого узла, и это имело большое значение. Одни и те же узлы посещались неоднократно, и каждый раз пересчитывалось количество детей. Это довольно дорогая операция, поскольку Xerces существенно перестраивает структуру DOM для этого узла, чтобы гарантировать его жизнеспособность. У нас есть собственный объект, который инкапсулирует DOMNode Xerces вместе с дополнительной информацией, которая нам нужна, и мы используем DOMNode::setUserData, чтобы связать наш объект с соответствующим DOMnode, и теперь он, похоже, является последним остающимся узким местом.