Форум 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)

wvxvw 13.07.2011 15:12
Задачка из серии "для экзаменаторов"
 
Вот пришел к нам работать новый человек и поделился задачкой (я запостю пару моих решений, но позже). Вопрос который ему задали на каком-то собеседовании (он вообще сам пишет на Яве, поэтому во Флеше может показаться немного надумано, но в общем вопрос, можно сказать, агностически-программистсткий).

Собственно задача: Нужно развернуть однонаправленный связанный список за O(n) время, естесственно минимальным n. Во Флеше это конечно немного усложняется тем, что нет канонической реализации связного списка, но для задачи, предположим, что он у вас есть :) Если хочется предложить свои варианты реализации - я бы смотрел в сторону HaXe, т.как там есть стандартный List, ну или вы можете воспользоваться FD + моим шаблоном (как-бы нет в нем ничего особенного, и сейчас я начинаю понимать, что можно было бы по-другому... и ах... но для этой задачи не принципиально http://code.google.com/p/e4xu/source...es/List.as.fdt ).

terbooter 13.07.2011 15:32
А в чем подвох?
Обычным for 0..n создаем список.

Котяра 13.07.2011 16:33
Код AS3:
var prev:Element;

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

{

        var element:Element = new Element();

        if(prev)

                element.prev = prev;

        prev = element;        

 

}
не? если нужен next сделаем список от n до 0

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

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

CrazyFlasher 13.07.2011 16:59
Array#reverse() ? :)

iNils 13.07.2011 17:14
Сменить ссылку с последующего элемента на предыдущий и сделать последний элемент первым.

Bgg 13.07.2011 17:22
Цитата:
Сообщение от CrazyFlasher (Сообщение 1011463)
Array#reverse() ? :)
Хрен там, обычно просят накалякать код на бумажке без использования стандартных методов сортировки.
Код AS3:
var a:Array = [1,2,3,4,5];

 

for(var i:int = 0; i < a.length; i++){

        var f:int = a[i];

        var l:int = a[Math.abs(a.length - 1 - i)];

        a[i] = l;

        a[Math.abs(a.length-1 - i)] = f;

 

        var b:int = Math.round((a.length-1)/2);

        if(i+1 == b)break;

}

 

trace(a);

-De- 13.07.2011 17:34
чото такое, что-ли
Код AS3:
function reverse(list:List):List {

        var l0:List = list;

        var l1:List = null;

        while(l0) {

                var tmpList:List= l1;

                l1 = l0;

                l0 = l0.next;

                l1.next = tmpList;

        }

        return l1;

}
извините, как переменные назвать - не придумал просто %)

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

-De- - пока что ближе всех, но решение может быть меньшей алгоритмической сложности.

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

nuToH 13.07.2011 18:02
Мой, "пазорный" вариант)

Код AS3:
//создаём список

var a:Object = {i:0};

var first:Object = a;

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

        var next:Object = {i:i};

        a.link = next;

        a = next;

}

 

first = reverse(first);

//трейсим результат

while (first.link) {

        trace(first.i);

        first = first.link;        

}

trace(first.i);

 

 

function reverse(first:Object, next:Object = null) {

        if(next == null) {

                next = first.link;

                first.link = null;

        }

 

        var successor:Object = next.link;

        next.link = first;

 

        if(successor)

                return reverse(next, successor);

        else

                return next;

}

GBee 13.07.2011 18:16
Код AS3:
function reverse(item:Object):void

{

    if(item.next)

    {

        reverse(item.next);

        item.next.next = item;

    }

    else

    {

        listRoot = item;

    }

}

 

reverse(listRoot);

Dukobpa3 13.07.2011 18:23
Код AS3:
function reverse(list:List):List {

        while(list) {

                var tmp:List = list.next;

                list.next = list.prev;

                list = list.prev = tmp;

        }

        return list;

}

GBee 13.07.2011 18:27
Dukobpa3, список однонаправленный.

wvxvw 13.07.2011 19:21
ОК, вот ожидаемый вариант, с объяснением:
Код 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 действия: первое, пройти по всему списку и сложить его в стек, второе - забрать из стека.
Внимание: во Флеше это не будет самым оптимальным вариантом, в виду того, что во флеше с коллекциями есть, скажем так... недопонимание... но в теории это самое простое, что можно сделать (и если пойти дальше и разобрать ситуацию на уровне регистров / директив процессора такой подход был бы действительно самым оптимальным).

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

Котяра 13.07.2011 19:59
Цитата:
Сообщение от wvxvw (Сообщение 1011460)
Нет, я видимо не правильно объяснил. Список уже есть, готовый, его нужно развернуть, т.е. чтобы последний элемент списка стал первым, предпоследний - вторым и т.д.

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

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

ЗЫ. А как тогда правильно перевести 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))

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

GBee 13.07.2011 22:52
а чем моя рекурсия не понравилась?

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

-De- 14.07.2011 11:34
Ну смотрите, что вам по минимуму нужно:
на первом проходе:
загнать в стек, достать след. элемент (не лучше 2-х присваиваний)
на втором проходе:
достать из стека (и присвоить текущий элемент тому, что достали), присвоить след. элемент (не лучше 2-х присваиваний).
Т.е. по сути то же + работа со стеком и два прохода зачем-то.

alatar 14.07.2011 13:47
Реализация и тесты двунаправленного списка
http://jacksondunstan.com/articles/1288

arkadattx 14.07.2011 14:39
alatar, означает ли это, что в некоторых случаях есть смысл преобразовать Vector в Array (в зависимости от предполагаемого действия)? Или я не уловил мысль?

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

alatar 14.07.2011 14:54
При чем тут вектор и массив? связанный список != Vector.
В любом случаe, смысла в замене нет.

wvxvw 14.07.2011 19:07
-De- Да ну блин, смысл в том, что ответ на вопрос предполагал более абстрактное мышление (моя реализация только попытка показать, что имелось в виду, я же сразу же написал, что во флеше она не будет наверняка самой оптимальной). Смысл в том, что у задачи есть универсальное решение не привязаное к конкретному языку. Т.е. переносимое между языками - вот уже подробности реализации экзаменирующийся / экзаменатор мог бы даже и не знать. Наверное лучше было изначально задать вопрос типа "объясните без того, чтобы писать код"...

Там тест не отражает реальное положение вещей. Главная разница между вектором и массивом заключается в том, что вектор, это "настоящий" массив. Т.е. если вы создали его длины 100, то он и выделил под 100 элементов 100 * sizeof ( тип массива ). А массив во флеше, это очень такой загадочный зверь, т.е. если вы, например будете заполнять индексы массива не с 0 а с 1, то вы по факту будете делать то же самое, что и
Код AS3:
var o:Object = { }; o["1"] = 1, o["2"] = 2;
. Соответственно, в зависимости от ситуации выделение памяти может сильно отличаться для обоих типов при в принципе похожих исходных значениях. Кроме того, естественно что скорость доступа / чтения / записи будет отличаться ну и т.п.

-De- 14.07.2011 23:03
Я писал про максимально абстрактный вариант в #25
Какого из действий не будет в максимально абстрактном варианте?
1) пуш в стэк
2) поп из стэка
3) шаг по "старому" списку
4) установка следующего элемента в новом списке
Или какое-то из них не будет вызывать присваивание? Или какие-то можно обьединить, не добавив при этом ещё одного присваивания?
Или моё решение не переносится на какой-то язык?

wvxvw 15.07.2011 00:05
Да, не переносится, например функциональные языки без побочных эффектов не разрешают разрушающее присваивание (Scheme / ML / Erlang). Но не в этом же суть... абстракция - это когда вы множество разнообразных явлений объединяете по какому-то сходному для всех принципу, и этот же принцип можно назвать абстракцией. Тоесть, ответ заключался в том, что нужно список положить в стек, а потом оттуда забрать. Как именно вы это будете делать - это конкретика (т.е. противоположность абстракции). Кроме того, любое конкретное оптимальное решение будет реализацией единственного абстрактного решения.

-De- 15.07.2011 03:06
А сделать новый список, цепляя в его начало элементы старого по порядку (такая вот абстракция) - можно на функциональщине?
Ну блин, не нужен стэк. О(1) оно должно памяти жрать. Иначе как-то стыдно про оптимальность говорить.

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

Sintesis 16.07.2011 16:09
Вот есть несколько задач с АСМ ICPC 2011. Как можно такое решать, ещё и за короткое время.


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

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