|
|
« Предыдущая тема | Следующая тема » |
Опции темы | Опции просмотра |
|
|
|||||
__________________
Чтобы доказать, что вы не робот, причините вред другому человеку. Последний раз редактировалось GBee; 13.07.2011 в 18:24. |
|
|||||
__________________
Кто к нам с чем для чего - тот у нас того от того. Последний раз редактировалось Dukobpa3; 13.07.2011 в 18:29. |
|
|||||
Modus ponens
|
ОК, вот ожидаемый вариант, с объяснением:
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; } } } Внимание: во Флеше это не будет самым оптимальным вариантом, в виду того, что во флеше с коллекциями есть, скажем так... недопонимание... но в теории это самое простое, что можно сделать (и если пойти дальше и разобрать ситуацию на уровне регистров / директив процессора такой подход был бы действительно самым оптимальным).
__________________
Hell is the possibility of sanity |
|
|||||
буду краток
модератор форума
Регистрация: Sep 2003
Адрес: Ближайшее Замкадье
Сообщений: 3,110
Записей в блоге: 28
|
Цитата:
а проверка реально не нужно.. просто для первого элемента ещё prev нет.. ну и типа фиг с ним - и так и так null
__________________
Отряд Котовскага |
|
|||||
Modus ponens
|
Так фишка то в том как раз, что за два прохода будет в общем случае эффективнее (потому что это очень простой код, там почти ничего делать не нужно).
Т.е. тут скорее нужно было объяснить глобально причину: одна структура данных устроена именно таким образом, а другая таким, что при создании одной из другой мы получим нужный результат. Т.е. то же решение с тремя переменными - это своего рода реализация этой же задумки, и рекурсивное решение - тоже (рекурсивная функция помещает первый элемент списка на стек вызовов, а когда возвращается - первый же и забирает). Три переменные создают "очень короткий" стек из двух элементов, но это решение алгоритмически более сложное т.как нужна дополнительная переменная которая все время хранит промежуточный результат. ЗЫ. А как тогда правильно перевести 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))
__________________
Hell is the possibility of sanity Последний раз редактировалось wvxvw; 13.07.2011 в 20:22. |
|
|||||
блогер
Регистрация: Oct 2005
Адрес: Днепродзержинск - город Брежнева и других логопедов
Сообщений: 1,421
Записей в блоге: 4
|
4 присваивания, два оператора "." и одна проверка на 0 (в цикле) - на одну итерацию (у меня).
против Трёх присваивания, двух операторов ".", двух проверок на 0, push и pop - на одну итерацию (у вас). +дополнительно O(n) жрём память. Сильно простая задача, чтоб что-то сложное городить, по-моему %)
__________________
Бобры отвечают на вопросы не потому, что знают на них ответы; они отвечают потому, что их спрашивают. Последний раз редактировалось -De-; 13.07.2011 в 23:25. |
|
|||||
Modus ponens
|
Не-не, вы не совсем так меня поняли: я же написал, что во флеше в силу множества особенностей (отсутствие связных списков, массивы, которые по-сути являются хеш-таблицами, отсутствует специальная структура для стека и т.д.). Кроме того Array.push() возвращает не то, что ожидалось бы от стека, т.е. ожидалось бы что a.push(b) == b, а не a[a.push(b)] == b, но даже используя последнее можно было бы более "оптимально" с точки зрения AS3 переписать мой код.
Существует общее правило, которое можно вывести из поведения двух структур данных, и его можно вывести вне зависимости от языка реализации. Рекурсивное решение, в том числе, является одной из реализаций этого правила, т.как что оно по-сути делает: когда функция начинает выполнение, она оставляет первый элемент списка на стеке (вызова), а когда возвращаетса, то забирает первый элемент со стека - т.е. фактически использует стек вызова для того самого стека из "правила". Собственно, от отвечающего ожидалось не столько предложить конкретное решение для конкретного языка (а вдруг вам прийдется писать на языке, который не поддерживает рекурсии, или рекурсии в нем очень ресурсозатратны / есть жесткие ограничения на длину стака вызовов), сколько объяснить взаимосвязь между структурами данных.
__________________
Hell is the possibility of sanity Последний раз редактировалось wvxvw; 14.07.2011 в 11:21. |
Часовой пояс GMT +4, время: 19:11. |
|
« Предыдущая тема | Следующая тема » |
|
|