Цитата(GoldFinch @ 1.6.2009, 18:20  ) |
| КА будет использовать свой стек в отличие от аппаратного при рекурсии, вот и вся разница |
А почему КА не может использовать рекурсивные вызовы ?!
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Конечный автомат вместо рекурсии |
| Автор: SABROG 1.6.2009, 18:05 |
| Вопрос теоретический. Предположим есть дерево основанное на указателях. По сути динамический список (list, array). Каждый элемент этого списка - указатель или объект содержащий ссылку на другие такие списки. Есть функция, которая должна обходить это дерево (как дерево файлов). Напрашивается естественное решение использовать рекурсию. Но хочется использовать Конечный Автомат для этой задачи, как более правильное и безопасное решение. Проблема в том, что я плохо понимаю как это работает. Можете мне это разжевать? |
| Автор: cardinal 1.6.2009, 18:41 |
| SABROG, если ты знаешь глубину (по крайней мере максимальное значение) дерева, то можешь использовать конечный автомат. Если не знаешь глубину, то без рекурсии не обойтись. Рекурсия является точно таким же безопасным решением, если условия выхода из рекурсии правильно. А какое решение правильно это вообще непонятный вопрос. Оба решения правильны, если работают правильно. А то, что ты имеешь в виду это эффективность. Рекурсия зачастую работает медленнее (из-за стэка). |
| Автор: SABROG 1.6.2009, 18:56 |
| Максимальное значение что-то типа типа -1 или 4294967295, по размеру регистра. Этого, по идее, должно хватить. Главное при этом, чтобы от этого значения скорость или время выполнения цикла не зависило. |
| Автор: GoldFinch 1.6.2009, 19:20 |
| SABROG, если ты не знаешь как работает КА , то с чего ты решил что он подходит? КА будет использовать свой стек в отличие от аппаратного при рекурсии, вот и вся разница. |
| Автор: mes 1.6.2009, 20:30 | ||
А почему КА не может использовать рекурсивные вызовы ?! |
| Автор: SABROG 1.6.2009, 20:54 |
| А почему КА не может скакать уровень за уровнем очищая при этом каждый раз результаты от предыдущего уровня? |
| Автор: GoldFinch 1.6.2009, 21:13 |
| mes, смотря какой КА и как он реализован %) |
| Автор: mes 1.6.2009, 22:00 | ||||
Что Вы подразумеваете под понятием "конечный автомат" ? Добавлено @ 22:03
 в этом то и дело, что рекурсивное перемещение по дереву и выполнение работы КА вполне могут использоваться в комплекте.поэтому чего добивается автор не вполне понятно.  |
| Автор: SABROG 1.6.2009, 22:06 | ||
Цикл while с некоторым условием для выхода, а внутри цикла switch..case где выполняется разный код в зависимости от состояний  |
| Автор: mes 1.6.2009, 22:12 | ||||
интересно а чем тогда по Вашему цикл по while правильней и безопасней рекурсивного цикла ? |
| Автор: SABROG 1.6.2009, 22:23 | ||||||
Стек не резиновый, а джампы могут быть бесконечные. |
| Автор: GoldFinch 1.6.2009, 22:47 |
| SABROG, у тя либо будет автомат с магазинной памятью - своим стеком либо вложенные автоматы - та же рекурсия либо конечное число однотипных состояний и конечная глубина дерева |
| Автор: SABROG 1.6.2009, 23:14 | ||
А если представить, что есть некое громадное дерево настолько большое, что занимает тысячи серверов, как у гугля. Программа будет являться чем-то вроде клиента и её возможности ограниченны. Как решают подобные задачи? Рекурсия естественно уже не подходит. Это получается деревья надо как-то обрезать до некоторого уровня, обрабатывать кусок, затем обрезать следующий и так далее. |
| Автор: cardinal 1.6.2009, 23:28 |
| SABROG, почитай и подумай над тем, что происходит вообще в рекурсии (во время вызова процедурой саму себя) http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F и поймешь как "обрезать" ее до некоторого уровня... |
| Автор: mes 1.6.2009, 23:58 | ||
Но это никакого отношения к конечному автомату не имеет. Поэтому прежде всего необходимо перефразировать ту цель, которой добиваетесь, чтоб искать для нее решение. Иначе Вы и сами запутаетесь и других запутаете. |
| Автор: math64 2.6.2009, 09:16 | ||
А как конкретно организовано дерево?
|
| Автор: SABROG 2.6.2009, 10:53 | ||
Что-то типа std::vector<std::vector> |
| Автор: xvr 2.6.2009, 11:05 | ||||
Это 'что то типа' больше похоже на 2х мерный массив, а никоим образом не на дерево. Для его обхода достаточно 2х вложенных циклов |
| Автор: SABROG 2.6.2009, 11:25 | ||||||
Неудачно значит привел пример Тогда такое. Есть некий объект класса Object. У этого объекта есть метод childs(), который возвращает std::vector<Object *>. |
| Автор: xvr 2.6.2009, 11:41 | ||
Угу, это уже дерево При обходе любого дерева на каждом шаге существует текущая вершина и путь от корня до нее. Набор текущих вершин и составляет результат обхода, а путь служит для управления процессом обхода. Максимальная длинна пути равна глубине дерева. Этот путь существует при ЛЮБОЙ реализации обхода: для рекурсивного обхода он неявно выражен в стеке вызовов рекурсивной процедуры обхода, при нерекурсивном обходе он должен быть выражен явно. Здесь есть 2 возможности - явный массив (причем заранее неизвестной длинны) или использование самого дерева для хранения пути. Во 2м случае в КАЖДОМ узле придется добавить указатель на родителя (для перемещения по пути назад) и индекс текущего потомка (для перемещения вперед). Затраты на рекурсию будут меньше (IMHO) |
| Автор: SABROG 2.6.2009, 12:12 |
| А если рассматривать такой вариант. Выше cardinal сказал, что возможно "обрезать" дерево для рекурсии таким образом, чтобы её сворачивание и разворачивание происходило при некотором значении уровня. По идее это должно предотвратить перезапись стека при громадных деревьях. Если это возможно, то значит и возможно сделать и конечный автомат с такой предустановленной глубиной магазина? Тем более мне сейчас интересен альтернативный вариант рекурсии, циклами и т.п. Только хочу ввести дополнительное ограничение. Экземпляр объекта класса Object - класс чужой библиотеки и я не могу поменять его. В нем есть метод типа parent() и children(). Соответственно parent() возвращает Object *, а children() - std::vector<Object *>. Уровень вложения при этом не известен. А нужно ли ему быть в каждом члене или достаточно просто инкрементировать некую переменную на 1 при каждом проходе? |
| Автор: math64 2.6.2009, 12:51 | ||
| Если нет метода Object::getIndex(); придётся вводить vector<int> indices; для хранения индексов или при каждом возврате к родителю определять индекс дочернего объекта, от которого вернулись. Если не использовать рекурсию, путь к текущему элементу можно хранить так:
Метод Object::parent() использоваться не будет, childs храним чтобы не вызывать повторно Object::children() |
| Автор: mes 2.6.2009, 13:31 | ||
Ну а какая примерно максимальная глубина дерева ? |
| Автор: SABROG 2.6.2009, 14:21 | ||||
Неизвестно Давайте представим, что это stream tree, которое качается через интернет и ни конца ни края не видно. |
| Автор: xvr 2.6.2009, 15:06 | ||||||||||
Это можно, но для такого 'обрезания' нужно все же рекурсивно часть дерева обойти. После чего сохранить необойденные линки в массив. После чего нужно повторить обход по линкам из этого массива. Т.е. это получается некоторая комбинация стека и массива
 |
| Автор: SABROG 2.6.2009, 15:12 | ||||||
А давай представим, что метод children() отсылает запрос на сервер, который возвращает список с детьми для этого объекта.
Ну хорошо, давай обойдем, только скажем <= 3 уровня.
А нельзя ли сделать какой-нибудь pop(), чтобы тупо выкинуть пройденные узлы, вместо того, чтобы создавать новый список? |
| Автор: cardinal 2.6.2009, 17:15 | ||
Зачем стэк, если его можно заменить массивом? |
| Автор: xvr 2.6.2009, 18:52 | ||||||||||||||
Значит эти дети уже 'обойдены', раз их возвратили в потоке. Для следующих узлов вернут еще пакет 'детей'
Огласите пожалуста задачу полностью, а то мы тут пока пытаемся построить модель 'сферического коня в ваккуме'  Добавлено через 5 минут и 56 секунд
Это вопрос к автору топика - ему надо что то большое, но маленькое и синего цвета, но красное. Еще ему надо обойти дерево не расходуя памяти, а само дерево находится неизвестно где и доставляется для обхода исключительно неизвестно какими кусками неизвестно откуда. Для обхода ему нужен нерекурсивный автомат (или пулемет, я уже и не знаю), и еще ему кажется (IMHO), что если удасться скрестить ежа с ужом (т.е. стек с массивом), то все получится автоматом (или гранотометом)  |
| Автор: cardinal 2.6.2009, 19:59 |
| xvr, я понял... |
| Автор: SABROG 2.6.2009, 22:28 |
| xvr, хорош прикалываться, я в Ховрино живу если че, не далеко от тебя Попробую поставить тогда задачу таким образом. У меня есть объект, реализация которого скрыта внутри сторонней библиотеки (т.е. я не могу изменить класс этого объекта как мне хочется). Этот объект является родителем остальных таких же объектов. Чтобы достучаться до детей этого объекта мне надо использовать метод children(). Я не знаю глубины, ничего вообще кроме того, что это дерево. Моя цель - обезопасить программу от возможных падений путем "обрезания" дерева таким образом, чтобы при достижении некоторой его глубины итеративный цикл разворачивался в обратную сторону, запоминал на каком узле он остановился и начинал итерацию снова. Таким образом график уменьшения стека должен напоминать зубья пилы или американские горки. В качестве подзадачи (академический интерес) хотелось бы реализовать это в виде конечного автомата, если такое вообще возможно. Если для конечного автомата нужно некоторое ограничение, то пусть им будет глубина дерева после которого автомат вернется обратно в основной цикл while(1) и начнет снова обрабатывать дерево с заранее запомненной позиции. |
| Автор: xvr 2.6.2009, 23:31 | ||||||
| Конечный автомат тут совершенно не при чем. Что касается собственно обхода - его можно сделать без стека (с массивом). Увы необходимый размер массива статически задать невозможно. Более того, в принципе невозможно сделать возобновляемый обход дерева, при условии что:
Еще уточнение - даже за линейное можно Основная идея - путь от вершины дерева до текущего узла хранится в массиве структур вида
Теперь про ограничение на размер - при выполнении path.push_back можно контролировать размер массива, и если он превышает установленный предел - стирать элемент в начале (кстати, лучше взять не vector а deque) При path.pop_back нужно проверить не удаляется ли из массива последний элемент и не является ли он корнем дерева (tree_root). Если элемент последний и он не корень, то надо восстановить предыдущий элемент (он был стерт из массива из за ограничения по размеру).
|