3

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

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

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

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

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

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

2
  • Возможно стоит сгруппировать список на подсписки по имени узла А, и проверять их по подгруппам? Для определенного узла находим соответствующую ему подгруппу правил и проверяем все правила из этой подгруппы.
    – user218976
    16 авг 2018 в 9:20
  • Если каждый узел (лист дерева) должен быть проверен по каждому правилу, то перебор все-все упростить не получится (порядок перебора, скорее всего, роль тоже играть не будет). Если к-то узлы, очевидно, не нужно на ч-то проверять -- упрощение возможно, но это надо уточнять...
    – DNS
    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
    22 июл 2020 в 22:48
  • Вы не поняли суть задачи. XSD технически не сможет реализовать проверку вида "если узел А имеет такое-то значение, то соседний с ним узел Б должен быть таким-то". XSD может проверить строки на длину, а также наличие или отсутствие тэгов. 24 июл 2020 в 6:06
  • Кстати, у готовой библиотечной функции валидации XML есть фатальный недостаток: она находит первую ошибку, рапортует "ну всё, документ невалиден" и на этом останавливается. Тому, кто этот XML потом будет исправлять, мало удовольствия отлавливать ошибки по одной. 24 июл 2020 в 6:08
  • находит первую ошибку, рапортует "ну всё, документ невалиден" и на этом останавливается - Да, проблема известная и уже давно решена - есть готовые решения, которые позволяют получить все ошибки документа списком.
    – hwak
    28 июл 2020 в 14:41
  • XSD технически не сможет реализовать проверку вида "если узел А имеет такое-то значение, то соседний с ним узел Б должен быть таким-то" не согласен: я знаю несколько вариантов решения этой задачи на XSD. К слову, подавляющее большинство проверок XML документов реализуемо XSD схемой. Прикладной язык программирования необходим, как правило, для более сложных и высокоуровневых вещей - коммуникация с внешними системами, СУБД и пр.
    – hwak
    28 июл 2020 в 14:55

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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