Форум Flasher.ru - Глубина стека

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Глубина стека (http://www.flasher.ru/forum/showthread.php?t=150058)

semenyakinVS

05.02.2011 16:24

Глубина стека

Есть алгоритм создания дерева. Произвольного.
Возникла необходимость вложености больше 255 на ветках.

Как я понял, максимальная глубина стека в AS3 255...

Как можно управлять стеком виртуальной машины и вообще, можно ли это?

Добавлено через 2 минуты
Вложеность может быть больше 255 - проверил. Но какая тогда максимальная глубина?

samana

05.02.2011 16:43

Цитата:

Сообщение от semenyakinVS (Сообщение 970628)

Но какая тогда максимальная глубина?

Не стоит заморачиваться на пустом месте. Глубины вам хватит в любом случае.

КорДум

05.02.2011 19:14

Имеется в виду какой-нибудь факториал от 300? Я бы посоветовал вам разделить все это дело на несколько частей, каждая из которых не выходит за пределы стека. Мол, посчитать от 1 до 255, затем от 256 до 300 и перемножить эти результаты.

i.o.	05.02.2011 19:27

Цитата:

Как я понял, максимальная глубина стека в AS3 255...

ответ отрицательный. Можно задать свою глубину, если верить докам

expl	05.02.2011 19:27

Вообще где-то было изменение максимального размера стека (что-то плохо гуглится), по крайней мере через изменение пары байт в скомпилированной swf-ке.

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

mikhailk

05.02.2011 19:40

Цитата:

Не стоит заморачиваться на пустом месте. Глубины вам хватит в любом случае.

У меня был один рекурсивный механизм расчета баттла, базирующийся на вероятности. Иногда, когда встречались два косых, но супер-защищенных противника, дно достигалось. :D
Пришлось ставить ограничитель. Типа, если за столько-то ходов никто никого не убил, сворачиваем баттл за отсутствием явного преимущества одной из сторон.

samana

05.02.2011 19:49

Оказывается я не понял вопроса. Я почему-то подумал о вложенности объектов в DisplayList. Извините меня пожалуйста. )

Psycho Tiger

05.02.2011 20:21

Flash IDE вроде давал ввести свою глубину. Значит, можно.

semenyakinVS

06.02.2011 00:18

Спасибо за ответы

Цитата:

Сообщение от Psycho Tiger (Сообщение 970716)

Flash IDE вроде давал ввести свою глубину. Значит, можно.

Ух ты! Где давал? Я что-то пропустил?

Цитата:

Сообщение от КорДум (Сообщение 970697)

Сарказм?.. Нет, факториал я не считал.

Цитата:

Сообщение от expl (Сообщение 970703)

А вообще любой рекурсивный алгоритм можно свести к нерекурсивному.

Cвести задачу к итерации, увы не получится. Это именно дерево, причём произвольной конфигурации.

Но за совет спасибо, хотя такой способ знал и сам. В крайнем случаи прибегну к нему…

expl	06.02.2011 00:21

Цитата:

Cвести задачу к итерации, увы не получится. Это именно дерево, причём произвольной конфигурации.

Вы не поверите, но дерево можно обойти нерекурсивно. И даже произвольной конфигурации
http://www.petrsu.ru/Chairs/IMO/pasc...part2_1_7.html

Цитата:

Ух ты! Где давал? Я что-то пропустил?

В параметрах публикации, наверное.

Psycho Tiger

06.02.2011 00:24

Цитата:

Ух ты! Где давал? Я что-то пропустил?

Гм, действительно нету. Видимо, пропустил я.

КорДум

06.02.2011 00:25

Цитата:

Сарказм?.. Нет, факториал я не считал.

С чего бы? В расчете факториала тоже используется рекурсия.
Дерево тоже можно на части порубить и пробегаться кусками.

expl	06.02.2011 00:39

Цитата:

Сообщение от Psycho Tiger (Сообщение 970774)

Гм, действительно нету. Видимо, пропустил я.

Зато в доках по mxmlc есть:
http://help.adobe.com/en_US/flex/usi...9084-7a92.html

Цитата:

default-script-limits max-recursion-depth max-execution-time

The max-recursion-depth value specifies the maximum depth of Adobe Flash Player call stack before Flash Player stops. This is essentially the stack overflow limit. The default value is 1000.

Цитата:

С чего бы? В расчете факториала тоже используется рекурсия.

Это только в книжках чтобы показать для чего она нужна - на практике ни одна сволочь так писать не будет

P.S. В стеке вызовов насчитал 500 функций до падения - странно, но и что по умолчанию стоит на 255 не похоже

semenyakinVS

06.02.2011 00:47

Цитата:

Сообщение от КорДум (Сообщение 970775)

Смысла нету. Факториал считается динамическим програмированием. Пишется рекурентная формула, и всё очень хорошо выходит.

a0 = 1
a(n+1) = a(n)*(n+1)

Считать её деревом - безумие...

Добавлено через 1 минуту
Хотя нет, почти безумие. Для указанного в вашем комментарии факториала от 300 дерево может понадобиться для хранения результата. Тогда может быть нужным считать результат по веткам и суммировать в конце. Вы это имели в виду?

Добавлено через 3 минуты

Цитата:

но и что по умолчанию стоит на 255 не похоже

Я ж написал потом (в первом посте) - не 255, я проверил дальше, оно прошло.

Причем, в один из запусков глубина была 1302... Запуски, правда, были линейными. Неужели сама виртуалка разварачивает... По коду она этого понять не могла бы: там стоит цикл по кол-ву веток, просто в моём случаи ветка одна была для каждого уровня.

i.o.	06.02.2011 00:52

Цитата:

P.S. В стеке вызовов насчитал 500 функций до падения - странно, но и что по умолчанию стоит на 255 не похоже

Если сменить лимит времени выполнения скрипта, с 15 дефолтных на свои скажем 25 сек, и написать "тяжелый расчет", то после 25 сек, плеер любезно сообщит про превышение 15 сек лимита.

expl	06.02.2011 00:54

Вообще не понимаю, откуда легенда, что факториал считается рекурсией - в бывшей моей конторе на собеседовании чел тоже что-то про факториал и рекурсию плёл

Код AS3:

function fuctorial(x:int):int

{

    var a:int = 1;

    for (var i:int = 1; i <= x; i++)

    {

         a *= i;

    }

    return a;

}

Какая рекурсия может быть проще этого? (про производительность молчу)

i.o.	06.02.2011 00:58

Если это не обход дисплей-листа или прочих деревьев (хотя и их можно развернуть в цикл, просто не так элегантно будет выглядеть), то

Цитата:

Любую рекурсивную функцию можно заменить циклом и стеком.

вот вам источник

mikhailk

06.02.2011 00:59

Цитата:

Вообще не понимаю, откуда легенда, что факториал считается рекурсией

на самом деле это классика

Код AS3:

function factorial(n:uint) : uint

{

   if (n==1) return 1;

   else return n*factorial(n-1);

}

и рекурсией на самом деле многие вещи считать не в пример проще, нежели итерацией

КорДум

06.02.2011 01:04

Цитата:

Сообщение от mikhailk (Сообщение 970789)

на самом деле это классика

Код AS3:

function factorial(n:uint) : uint

{

   if (n==1) return 1;

   else return n*factorial(n-1);

}

и рекурсией на самом деле многие вещи считать не в пример проще, нежели итерацией

Ага, а-ля лабораторные в универе.

А вообще, вот я писал рекурсивный обход дерева: http://www.flasher.ru/forum/showthread.php?t=147050 )

expl	06.02.2011 01:07

Цитата:

и рекурсией на самом деле многие вещи считать не в пример проще, нежели итерацией

С этим не поспоришь - конечно никто не будет её разворачивать без острой необходимости.
В узких местах только от нее приходится избавляться.

Про фаториал:
Всётки эта классика не выглядит интуитивно понятной, но это ИМХО

semenyakinVS

06.02.2011 01:14

В случаи с факториалом использование итерации это не решение университетской задачи. От вопрос быстродействия.

И, по-моему, код приведённый expl более понятен, чем рекурсивное решение.

Цитата:

А вообще, вот я писал рекурсивный обход дерева

Это хорошо, но у меня проблема в глубокой степени вложености.

mikhailk

06.02.2011 01:15

Цитата:

А вообще, вот я писал рекурсивный обход дерева

Для меня, применительно к AS3, обход деревьев - процесс изначально абсолютно непонятный. В других языках он был нужен для парсинга xml-данных, но в AS3... Не, реально не понимаю.

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

КорДум

06.02.2011 01:19

Писал обход для построения вывода структуры трейсами. Без него тоже можно, я в теме той писал, как это делается. AS3 представляет уже готовые средства для всего этого, это понятно.

expl	06.02.2011 02:01

Цитата:

Это хорошо, но у меня проблема в глубокой степени вложености.

С параметром компиляции default-script-limits не прокатило?

Котяра

06.02.2011 02:29

Про факториал и рекурсии/выход из неё.
http://www.flasher.ru/forum/showpost...62&postcount=9

semenyakinVS

06.02.2011 02:50

Цитата:

Сообщение от Котяра (Сообщение 970822)

Про факториал и рекурсии/выход из неё.
http://www.flasher.ru/forum/showpost...62&postcount=9

ОМГ... Где вы думали хранить результат?

Добавлено через 1 минуту

Цитата:

Сообщение от expl (Сообщение 970811)

С параметром компиляции default-script-limits не прокатило?

Честно говоря - мне безумно стыдно - но я не знаю, что такое параметры компиляции и где их выставлять. Подскажете? Они помогут?

derhab

06.02.2011 10:26

Вложений: 1

В FD, к примеру
Вложение 25935
compiler options:
http://livedocs.adobe.com/flex/3/htm...pilers_14.html

expl	06.02.2011 14:30

Вложений: 1

Во FlashBuilder, до кучи:
Вложение 25936

semenyakinVS

06.02.2011 15:08

Цитата:

Сообщение от derhab (Сообщение 970862)

В FD, к примеру

Цитата:

Сообщение от expl (Сообщение 970879)

Во FlashBuilder, до кучи

Спасибо. Намотал на ус. А в CS5 IDE?

//-----------------------------------------------

По поводу сабжа... Проблему решил. Развернул рекурсию в итерацию, эмулировав стек.

Глянул вот это сегодня (странно, что пропустил до этого):

Цитата:

Сообщение от expl (Сообщение 970773)

За ссылку спасибо, но там дерево всё-таки бинарное. Под произвольной конфигурацией я имел в виду небинарное дерево, с произвольным числом веток.

Задачу решил вчера ночью и хотя решение, можно сказать, является обобщением алгоритма, ссылку на который дал expl, но было придумано независимо от него:

1. Заходим в узел.
2. Если из него одна ветка, то идём по ней и ничего больше не делаем.
3. Если больше одной, то заносим узел в свой "стек" + заносим номер следующей ветки, по которой будем идти из этого узла, когда вернёмся в него (в начале =2).
4. Движемся вглубь дерева, пока ветки не null для очередного узла. Если null, то мы добрались до конца - возвращаемся к верхнему элементу стека. Берём из него следующий индекс (если в начале был 2, то теперь 3). Если он больше кол-ва веток для данного узла, вытесняем элемент из стека. После этого идём по ветке с индексом, который был до инкремента.
5. Делаем так пока, при необходимости возврата, не обнаружим, что "стек" пуст.

Алгоритм работает как для формирования дерева по какому-либо правилу (функции: дерево поиска, дерево геометрических разбиений), так и для обхода уже готового дерева. Разница лишь в том, что для первого случая мы будем формировать ветки по направлению, а во втором – идти по ним.

derhab

06.02.2011 16:31

Цитата:

Сообщение от semenyakinVS (Сообщение 970882)

А в CS5 IDE?

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

i.o.	06.02.2011 17:11

а вот и нет, а вот и нет :)
можно написать для главного класса в метатеге [SWF] все параметры, какие нужно, включая ширину, высоту, фпс, цвет фона, лимит по времени и лимит по стеку.
Возможно это не все, но я пока только про такие знаю.

Добавлено через 5 минут
http://help.adobe.com/en_US/flex/usi...19d46bcb4-8000

derhab

06.02.2011 17:20

да, но вопрос был про CS5 IDE:)

i.o.	06.02.2011 17:36

И что? Вы имеете ввиду как это "в кадре" написать, а не в классе?

i.o.	06.02.2011 18:24

главное, что можно, а не то, что нет такой вкладки :)

derhab

06.02.2011 18:25

да и вообще речь шла о CS5 IDE и я так понял, что интересует вариант компиляции родным флэшевским компилятором и управление его параметрами, так что метатеги тут не катят

блин, случайно удалил предыдущее свое сообщение)
но неважно, и так все понятно вроде с этим..

alatar

06.02.2011 18:55

Цитата:

да и вообще речь шла о CS5 IDE и я так понял, что интересует вариант компиляции родным флэшевским компилятором и управление его параметрами, так что метатеги тут не катят

Если не ошибаюсь, компилятор в CS5 IDE поддерживает метатеги. Вопрос, правда, какие. Давно с ним не сталкивался.

i.o.	06.02.2011 19:16

[SWF] метатег он прекрасно поддерживает. Если б это было не так, то я бы тут не писал.

derhab

06.02.2011 19:33

странно, не ругается, но и изменений никаких... что я делаю не так?

Код AS3:

package

{ 

        import flash.display.MovieClip;

        [SWF(width="800", height="600", backgroundColor="#000000")];

 

        public class Test extends MovieClip

        {

                public function Test() {

                        trace(this)

                }

        }

}

в результате свф-ка по умолчанию..

Добавлено через 2 минуты
все, отбой, получилось, был неправ)
точка с запятой после тэга)

Часовой пояс GMT +4, время: 02:52.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.