3

Есть дерево (не бинарное). Дерево может быть очень большим (если интересно, дерево - объектная модель, созданная из xml, который может достигать сотен мегабайт). И есть список правил, по которым нужно проверять элементы дерева. Список тоже может быть достаточно большим (сотни правил, а то и тысячи). Правила вида "если узел имеет такое имя, то его значение может быть таким-то и не может быть таким-то" и "если узел А имеет такое-то значение, то соседний с ним узел Б должен быть таким-то".

Как лучше организовать обход с наименьшими затратами по времени?

Допустим, сделаем цикл по правилам. На каждом правиле обходить всё дерево целиком и на узлах с указанным в правиле именем проверять значение. Это может быть долго, очень долго.

Возьмём другую крайность: делаем один обход по дереву и в каждом узле проверяем весь список правил на предмет, подходит ли это правило этому узлу. Тоже, скорее всего, будет долго и неэффективно.

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

Язык - java, хотя это дело второстепенное, речь про алгоритм.

2
  • Возможно стоит сгруппировать список на подсписки по имени узла А, и проверять их по подгруппам? Для определенного узла находим соответствующую ему подгруппу правил и проверяем все правила из этой подгруппы.
    – user218976
    Commented 16 авг. 2018 в 9:20
  • Если каждый узел (лист дерева) должен быть проверен по каждому правилу, то перебор все-все упростить не получится (порядок перебора, скорее всего, роль тоже играть не будет). Если к-то узлы, очевидно, не нужно на ч-то проверять -- упрощение возможно, но это надо уточнять...
    – DNS
    Commented 16 авг. 2018 в 15:26

2 ответа 2

1

Видится, что обход по списку + по дереву придется делать в любом случае. Т.е. сложность алгоритма будет O((n + m) * k), где n - количество вершин, m - кол-во ребер, а k длина списка. Оптимизации могут быть только если есть связь между правилами и узлами. Например, если у этого узла выполнилось первое условие, то у всех его детей не выполнятся какие-то еще. Если такая связь есть, то, возможно, стоит как-то перестроить дерево. Короче, нужно больше информации по вашей конкретной задаче.

Еще один способ ускориться - распараллелить обход как по списку, так и по дереву.

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

0

Уже после публикации вопроса вчера понял, что раз структура исходного xml заранее известна, то можно в правило писать не только имя узла, но и полный путь от корня до этого узла. Написал вот такой рекурсивный обход:

import org.w3c.dom.Node;

private static List<Node> getNodesByPath(Node start, String patch) {
    List<Node> res = new ArrayList<Node>();
    String[] names = patch.split("/", 2);   //2 - означает, что строка будет поделена только на 2 части по первому разделителю
    String name = names[0];
    switch (names.length) {
        case 1:
            //в patch осталось только имя конечного узла
            if (start.getNodeName().equals(name)) {
                //добрались до пункта назначения, дальше идти не нужно
                res.add(start);
            }
            break;
        case 2:
             //мы на верном пути?
            if (!start.getNodeName().equals(name)) return res;  //нет, это не к нам
            patch = names[1];
            for (Node child = start.getFirstChild();
                    child != null;
                    child = child.getNextSibling()) {
                List<Node> childRes = getNodesByPath(child, patch);  //опросим всех потомков
                if (!childRes.isEmpty())
                    res.addAll(childRes);
            }
            break;
        default:
            break;
    }
    return res;
}

Возвращает целый список узлов - для случаев вроде "NODEA/NODEB/NODEC", при этом в NODEA есть несколько NODEB, в каждом из которых свой NODEC и нам нужен каждый из них.

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

6
  • На сколько я понял - вы валидируете XML документ. В этом случае, я бы на вашем месте реализовал XSD схему со всеми правилами валидации XML документа и отдал эту задачу на откуп готовой библиотечной функции tutorialspoint.com/xsd/xsd_validation.htm
    – hwak
    Commented 22 июл. 2020 в 22:48
  • Вы не поняли суть задачи. XSD технически не сможет реализовать проверку вида "если узел А имеет такое-то значение, то соседний с ним узел Б должен быть таким-то". XSD может проверить строки на длину, а также наличие или отсутствие тэгов. Commented 24 июл. 2020 в 6:06
  • Кстати, у готовой библиотечной функции валидации XML есть фатальный недостаток: она находит первую ошибку, рапортует "ну всё, документ невалиден" и на этом останавливается. Тому, кто этот XML потом будет исправлять, мало удовольствия отлавливать ошибки по одной. Commented 24 июл. 2020 в 6:08
  • находит первую ошибку, рапортует "ну всё, документ невалиден" и на этом останавливается - Да, проблема известная и уже давно решена - есть готовые решения, которые позволяют получить все ошибки документа списком.
    – hwak
    Commented 28 июл. 2020 в 14:41
  • XSD технически не сможет реализовать проверку вида "если узел А имеет такое-то значение, то соседний с ним узел Б должен быть таким-то" не согласен: я знаю несколько вариантов решения этой задачи на XSD. К слову, подавляющее большинство проверок XML документов реализуемо XSD схемой. Прикладной язык программирования необходим, как правило, для более сложных и высокоуровневых вещей - коммуникация с внешними системами, СУБД и пр.
    – hwak
    Commented 28 июл. 2020 в 14:55

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.