Форум Flasher.ru - Задачка из серии "для экзаменаторов"

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

- Флейм (http://www.flasher.ru/forum/forumdisplay.php?f=53)

- - Задачка из серии "для экзаменаторов" (http://www.flasher.ru/forum/showthread.php?t=160508)

Код AS3:

function reverse(item:Object):void

{

    if(item.next)

    {

        reverse(item.next);

        item.next.next = item;

    }

    else

    {

        listRoot = item;

    }

}

 

reverse(listRoot);

Код AS3:

function reverse(list:List):List {

        while(list) {

                var tmp:List = list.next;

                list.next = list.prev;

                list = list.prev = tmp;

        }

        return list;

}

Dukobpa3, список однонаправленный.

ОК, вот ожидаемый вариант, с объяснением:

Код AS3:

package tests.random

{

        import flash.display.Sprite;

 

        public class ReverseListExample extends Sprite

        {

                private var _stack:Array = [];

 

                public function ReverseListExample()

                {

                        super();

                        this.test();

                }

 

                private function test():void

                {

                        var list:Object;

                        for (var i:int = 10; i; i--) list = this.cons(i, list);

                        trace(this.listToString(list));

                        list = this.reverse(list);

                        trace(this.listToString(list));

                }

 

                private function reverse(list:Object):Object

                {

                        var result:Object;

 

                        while (list.next)

                        {

                                this._stack.push(list);

                                list = list.next;

                        }

                        result = list;

                        while (this._stack[0]) list = list.next = this._stack.pop();

                        list.next = null;

                        return newList;

                }

 

                private function cons(car:Object, cdr:Object):Object

                {

                        return { value: car, next: cdr };

                }

 

                private function listToString(list:Object):String

                {

                        var result:String = "(" + list.value;

                        if (list.next != null)

                                result += " " + this.listToString(list.next).substr(1);

                        else result += ")";

                        return result;

                }

        }

}

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

Та блин, в два прохода неинтересно)) Пыжились ведь сделать "за раз":)

Цитата:

Сообщение от wvxvw (Сообщение 1011460)

Нет, я видимо не правильно объяснил. Список уже есть, готовый, его нужно развернуть, т.е. чтобы последний элемент списка стал первым, предпоследний - вторым и т.д.

Котяра: а проверка зачем? :)

Ну вообще "развернуть" - это иногда подразумевает "создать".. типа развернуть сервер..
а проверка реально не нужно.. просто для первого элемента ещё prev нет.. ну и типа фиг с ним - и так и так null

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

ЗЫ. А как тогда правильно перевести reverse?

EDIT:
Да, кстати, другие (мои варианты) которые я предлагал (если кому интересно)

Код:

(defun reverse-list-1 (head &rest tail)

  (if head

      (reverse-list (cdr head)

                    (cons (car head) (car tail)))

      (car tail)))



(reverse-list-1 '(1 2 3 4 5 6 7 8 9 10))



(defun reverse-list-2 (input)

  (do ((eax (cons (car input) nil) (cdr ecx))

       (ebx)

       (ecx input (cdr ecx)))

      ((null ecx) ebx)

    (setf ebx (cons (car eax) ebx))))



(reverse-list-2 '(1 2 3 4 5 6 7 8 9 10))

4 присваивания, два оператора "." и одна проверка на 0 (в цикле) - на одну итерацию (у меня).
против
Трёх присваивания, двух операторов ".", двух проверок на 0, push и pop - на одну итерацию (у вас). +дополнительно O(n) жрём память. Сильно простая задача, чтоб что-то сложное городить, по-моему %)

а чем моя рекурсия не понравилась?

Не-не, вы не совсем так меня поняли: я же написал, что во флеше в силу множества особенностей (отсутствие связных списков, массивы, которые по-сути являются хеш-таблицами, отсутствует специальная структура для стека и т.д.). Кроме того Array.push() возвращает не то, что ожидалось бы от стека, т.е. ожидалось бы что a.push(b) == b, а не a[a.push(b)] == b, но даже используя последнее можно было бы более "оптимально" с точки зрения AS3 переписать мой код.
Существует общее правило, которое можно вывести из поведения двух структур данных, и его можно вывести вне зависимости от языка реализации. Рекурсивное решение, в том числе, является одной из реализаций этого правила, т.как что оно по-сути делает: когда функция начинает выполнение, она оставляет первый элемент списка на стеке (вызова), а когда возвращаетса, то забирает первый элемент со стека - т.е. фактически использует стек вызова для того самого стека из "правила".
Собственно, от отвечающего ожидалось не столько предложить конкретное решение для конкретного языка (а вдруг вам прийдется писать на языке, который не поддерживает рекурсии, или рекурсии в нем очень ресурсозатратны / есть жесткие ограничения на длину стака вызовов), сколько объяснить взаимосвязь между структурами данных.