Разница между шаблоном дизайна посетителя и глубиной первого поиска?

Question

Похоже, что поиск в глубину может выполнять те же функции, что и шаблон проектирования посетителя. Посетитель позволяет вам определять некоторые структуры данных и добавлять операции над этими структурами (в форме нескольких посетителей) по мере необходимости, не изменяя сами структуры. Описание шаблона посетителя приведено в wikipedia . Если мы выполняем поиск в глубину (или любой другой алгоритм поиска по графику, например, поиск в ширину) по структуре данных, и каждый раз, когда обнаруживается элемент структуры, мы запускаем желаемую операцию, тогда, похоже, она выполняет ту же функцию, что и посетитель. Например, рассмотрим дерево. Даже если некоторые узлы дерева имеют разные типы, мы все равно можем проверять типы узлов при выполнении DFS, а затем выполнять различные операции в зависимости от типа узла.

Answer 1

Поиск в глубину - это просто поиск. Шаблон посетителя ортогонален поиску в глубину, в том смысле, что посетителю не обязательно все равно как обходится дерево; он просто знает, что ему нужно делать на / с / с каждым узлом.

Answer 2

Вы можете иметь реализацию Visitor без DFS.Точно так же вы можете сделать DFS без использования шаблона Visitor.Они совершенно разные.

Я согласен с тем, что их можно элегантно использовать вместе.

В качестве примечания, для канонического паттерна "Посетитель" объекты, которые посещаются, должны реализовывать какой-то вид AcceptVisitor interface - предложение «без изменения самих структур» в вашем вопросе приводит меня к вопросу, делаете ли вы это.

Answer 3

Позвольте мне ответить на вопрос в коде:

/**
 * This method makes it easier for a class to process all
 * the nodes in an item. The class should implement
 * the NodeVisitor interface. This method will cause the 
 * NodeVisitor.processNode() method to be called once for each
 * node in this item. 
 * @param visitor the class that will visit each node
 * @throws PipelineException some recoverable exception
 */
public void visitNodes(NodeVisitor visitor) throws PipelineException {
    visitNodes(visitor, root);
}

private void visitNodes(NodeVisitor visitor, Node node) throws PipelineException {
    visitor.processNode(node);
    if (node.hasChildren()) {
        int childCount = node.getChildCount();
        NodeList children = node.getChildren();
        for (int i = 0; i < childCount; i++) {
            visitNodes(visitor, children.get(i));
        }
    }
}

/**
 * Classes that implement this interface can be used with
 * Item.visitNodes(). This method provides a convenient
 * way to iterate over all the nodes in an item.
 */
public interface NodeVisitor {
        public void processNode(Node node) throws PipelineException;
}

В этом случае метод visitNodes () реализует поиск в глубину, но это не обязательно. Он может реализовать любой поиск, который поражает все узлы. Это комбинация метода visitNodes () и интерфейса NodeVisitor, которые составляют «шаблон посетителя» (или одно его конкретное проявление).

Нет никакого компромисса между шаблоном проектирования и алгоритмом поиска. Шаблон проектирования просто облегчает использование алгоритма.

Answer 4

Шаблон посетителя, как (первый?) Описан в «Шаблонах проектирования» Эриха Гамма и др. и др. не обязательно включает обход структуры данных в методе accept. Хотя это очень удобная комбинация, в конце главы «Пример кода» в книге приведен явный пример для внешней итерации.

Таким образом, как уже говорили другие, обход в глубину, реализованный вне метода accept, все еще может реализовать шаблон посетителя. Тогда возникает вопрос, в чем разница между вызовом element.accept (посетитель), который, в свою очередь, напрямую вызывает visitor.visitElement (me) по сравнению с прямым вызовом visitor.visitElement (элемент)? Я вижу только две причины, по которым можно это сделать:

1. Вы не можете или не хотите узнать конкретный класс элемента, и просто тупо вызывая element.accept (посетитель), сам элемент должен решить, является ли visitor.visitElement или, например, visitor.visitAnotherElement - правильная операция для вызова.

2. Некоторые элементы являются композиционными и не имеют внешнего доступа к содержащимся внутренним элементам, а операции посетителя определены для внутренних элементов. Таким образом, метод accept будет зацикливаться на внутренних элементах и ​​будет вызывать visitor.visitInnerElement (innerElement). И так как вы не получаете внутренние элементы извне, вы также не можете вызвать visitor.visitInnerElememt (innerElement) извне.

В итоге: если у вас есть хорошо инкапсулированный алгоритм обхода, в котором вы можете передать класс, похожий на «Visitor», и который может отправлять соответствующие методы посещения в зависимости от типа объекта, обнаруженного во время обхода, вы делаете не надо беспокоиться о приеме-методах. Вы по-прежнему сможете добавлять новые операции, просто добавляя новые реализации Visitor и не затрагивая ни структуру данных, ни алгоритм обхода. Должно ли это все еще называться Шаблон посетителя - довольно академическая дискуссия. Я думаю, что в большинстве случаев использование метода accept имеет смысл только в том случае, если реализация метода accept также включает обход.

Answer 5

Я тоже согласен с ответом NRITH, поскольку шаблон посетителя знает 'только то, что делать с узлом' поверх этого посетителя, позволяет вам 'определить новую операцию без изменения классов элементовна котором он работает ' и DFS говорит о том, как выполняется поиск узла.Но для выполнения обхода глубины и обхода короткого замыкания мы используем Иерархический шаблон посетителя (http://c2.com/cgi/wiki?HierarchicalVisitorPattern).

. Вы также можете посмотреть Когда мне следует использовать шаблон проектирования посетителя? , который говорит о связи между шаблоном посетителя / DFS / иерархическим шаблоном посетителя.

Answer 6

Экземпляр visitor может выбрать посещение своих дочерних узлов, как ему угодно, и он не связан порядком обхода поиска в глубину. (Например, он может использовать Breath First Search)

Еще одна вещь, о которой следует упомянуть, это то, что структура, которую нужно пройти, не обязательно должна быть явным деревом. Я реализовал посетителей, которые перебирают структурированные данные, которые совсем не похожи на дерево. В этом случае я использовал посетителя, потому что мог скрыть сложный двоичный формат файла, который я анализировал, и позволить клиентам контролировать, какие части структуры они хотели бы проанализировать, не требуя, чтобы они знали спецификацию формата файла.

Answer 7

Глубина первого поиска - это «алгоритм», а шаблон посетителей - это способ забыть о проблемах алгоритма и сосредоточиться на действиях, которые необходимо выполнить.

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

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

В некоторых случаях вы можете выполнить поиск в глубину с помощью шаблон посетителя , но это не является целью этого шаблона.

Использование шаблона посетителя не зависит от того, какой тип анализа вы используете, но какой анализ должен быть выполнендля .

Answer 8

В теории графов вы можете построить граф таким образом, чтобы минимальное остовное дерево не было путем поиска в глубину, а точнее это не путь: https://cs.stackexchange.com/questions/6749/depth-first-search-to-find-minimum-spanning-tree. Я думаю, вы не можете применить это к дизайну шаблон.