Форум Flasher.ru - contains vs. parent

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

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

- - contains vs. parent (http://www.flasher.ru/forum/showthread.php?t=128903)

contains vs. parent

oParent - это DisplayObjectContainer
oChild - это DisplayObject

Что если вместо oParent.contains(oChild) использовать oChild.parent == oParent?
По моему должно быстрее работать или нет?

Код AS3:

oParent.contains(oChild) //есть ли в oParent oChild ?

oChild.parent == oParent // родитель oChild равен oParent?

Это немного разные вещи, но в любом случае oParent.contains(oChild) быстрее.

Цитата:

любом случае oParent.contains(oChild) быстрее

почему так категорично? наоборот
скорее всего в методе contains идет цикл по всем содержащимся объектам, и если объект найден возвращается true.
oChild.parent == oParent - это обычное сравнение

contains рекурсивный.

Цитата:

contains рекурсивный.

а, теперь понял в чем отличие между этими способами.
Но так и не понял почему contains быстрее?
Если он рекурсивный то он вообще должен быть очень медленным по сравнению oChild.parent == oParent

Он нативный потому что.

Все ясно, спасибо)

а если там сто тыщ миллионов объектов вложеных. он тоже быстрее будет? просто если он рекурсивный, значит зависимость логарифмическая, а у parent - линейная. значит при определенных условиях он обгонит contains.

хотя, это я так, мысли вслух.

Пора закончить спор.

mc2 находится в mc, изменение количества вложенных обьектов на результат практически не влияет.

Код AS3:

import flash.utils.getTimer;

 

var time:Number = getTimer();

 

function runContainsTest():void

{

 

        time = getTimer();

        for(var i:Number=0;i<20000000;i++)

        {

                if(parentMc.contains(childMc)){ }

        }

        trace("ContainsTest: ", (getTimer()-time));   //  1530

}

 

function runParentTest():void

{

        time = getTimer();

        for(var i:Number=0;i<20000000;i++)

        {

                if(childMc.parent == parentMc){ }

        }

        trace("ParentTest: ", (getTimer()-time));  // 1936

}

 

 

var parentMc:MovieClip = mc;

var childMc:MovieClip = mc.mc2;

runContainsTest();

runParentTest();

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

прошу прощения описался. не линейная, а константная (линейная на самом деле еще хуже логарифмической)

Вы уверены, что понимаете как работает contains? мне кажется, что код с поразительной точностью выглядит так ( только написан на Си ):

Код AS3:

public function contains(child:DisplayObject):Boolean {

        do {

                if ( child === this ) return true;

        } while ( child = child.parent );

        return false;

}

но как говорит товарищ etc

Цитата:

contains рекурсивный.

хотя это бессмысленный спор

UPD: но он же ходит и по всем детишкам наверно?

Felicast, внимательно изучите мой код. он рекурсивно проверяет.

Цитата:

Сообщение от BlooDHounD (Сообщение 844320)

Felicast, внимательно изучите мой код. он рекурсивно проверяет.

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

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

Рекурсия подразумевалась в том, что проверяется наличие ребенка в дочерних клипах, а не вызов всё того же contains у детей.

incoob, как ни странно, но википедия и со мной согласна

BlooDHounD, я не совсем понял, в чем с вами согласна википедия.
Вроде рекуррентные последовательности тут совсем не причем...

Все же вы используете не рекурсивные вызовы, а выполняете вычисления в цикле

С использованием рекурсии ваш код на AS3 выглядел бы примерно так:

Код AS3:

                public function contains(child:DisplayObject):Boolean

                {

                        return child != null && (child.parent === this || contains(child.parent))

                }

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

Ого, оказывается циклы - это не пример итерации!:eek:
Сильно сказано.
Что же тогда у нас будет итерацией и чем оно отличается от рекурсии в вашем понимании?

Скажите, в чем я не прав:
1) рекурсия ~~в программировании~~ - явный или неявный вызов функции из самой себя
2) итерация - повторения ряда действий, использующих результаты предыдущей аналогичной операции
3) цикл - набор итераций
4) ~~практически~~ каждый рекурсивный алгоритм может быть представлен в виде итерационного (что я, собственно, вам и продемонстрировал)

мдя ... я же говорил: каша.

а ещё "рекурсией" в программировании, называют ряд вещей:
1. ошибка
2. перебор деревьев
3. порождающие друг друга конструкции
и ещё целая куча вещей, которые я не успел вспомнить за 40 секунд.

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

p.s.: посетите первый курс университета.

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

Вы сами пробовали почитать текст по ссылкам, что приводились выше?

"В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия)"© wikipedia.org
"Итерация - это организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя." © wikipedia.org
"Последовательность инструкций, предназначенная для многократного исполнения, называется телом цикла. Однократное выполнение тела цикла называется итерацией." © wikipedia.org
Надеюсь вы не будете отрицать, что while - это цикл и нигде не производится явных или неявных вызовов вашего метода (contains)?

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

Код AS3:

child

на основании

Код AS3:

child.parent

Рассмотрим один из наиболее распространенных циклов:

Код AS3:

for (var i:int = 0; i <= n; i++){}

На каждой итерации происходит вычисление

Код AS3:

i

на основе уже вычисленного значения

Код AS3:

i

. По сути тот же случай, что и у вас. Полностью попадает под определение. Для большей наглядности рассмотрим пример. Возмем элементарный класс

Код AS3:

        public class Integer 

        {

                private var _value:int

                public function Integer(value:int)

                {

                        _value = value

                }

 

                public function get increment():Integer

                {

                        return new Integer(++_value)

                }

 

                public function get isMaxValue():Boolean

                {

                        return _value > 5

                }

        }

и используем его в цикле:

Код AS3:

                        var i:Integer = new Integer(0);

                        for (; !i.isMaxValue; i = i.increment ) { }

ну или, для наглядности

Код AS3:

                        var i:Integer = new Integer(0);

                        do {} while (!(i = i.increment).isMaxValue)

. Код конечно несколько избыточен, но, по сути, абсолютно идентичен вашему.

Итак, повторю, что уже давно говорил: в приведенном вами коде рекурсий нет.

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

PPS в принципе понятно, что под рекурсией подразумевал etc: последовательно опускаемся по дереву объектов. Но формально это рекурсией не является. Пример рекурсивного кода я уже писал.

мдя ... не понятно почему Вы говорите о тёплом, когда я говорю об мягком?
ждёте ответов?

Цитата:

1) рекурсия в программировании - явный или неявный вызов функции из самой себя

ответ дал выше, что в информатике называют рекурсией.

Цитата:

итерация - повторения ряда действий, использующих результаты предыдущей аналогичной операции

практически всё правильно, кроме того что статья не закончена. в моём понимании, итерациия - это процесс, повторяемый несколько раз и используемый предыдущие вычисления, с целью приближения к результату. тело цикла я даже никогда не думал называть итерацией. слышали когда-нить выражение "количество итераций"? обычно оно обозначает глубины вычислений. в обычном цикле такой операцией является приближение числа i к l.

Цитата:

3) цикл - набор итераций

иногда - да. иногда - нет.

Цитата:

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

опять же странная фраза. зависит от того, как Вы трактуете рекурсию.

p.s.: ошибка "рекурсия" - это исключение ( во АС3 StackOverflowError, кажется ), которое возникает, в процессе переполнения стека программы за счёт (не)явного вызова метода самого себя или типа того. грубо говоря "бесконечная рекурсия", как бывает бесконечный цикл, который в АС3 приводит к ScriptTimeoutError.