Задачка из серии "для экзаменаторов"

[wvxvw]

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

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

[terbooter]

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

[Котяра]

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]

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

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

[CrazyFlasher]

Array#reverse() ? :)

[iNils]

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

[Bgg]

Array#reverse() ? :)

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

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-]

чото такое, что-ли
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]

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

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

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

[nuToH]

Мой, "пазорный" вариант)


//создаём список
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]

function reverse(item:Object):void
{
if(item.next)
{
reverse(item.next);
item.next.next = item;
}
else
{
listRoot = item;
}
}

reverse(listRoot);

[Dukobpa3]

function reverse(list:List):List {
while(list) {
var tmp:List = list.next;
list.next = list.prev;
list = list.prev = tmp;
}
return list;
}

[GBee]

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

[wvxvw]

ОК, вот ожидаемый вариант, с объяснением:
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]

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

[Котяра]

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

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

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

[wvxvw]

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

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

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

[GBee]

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

[wvxvw]

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

[-De-]

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

[alatar]

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

[arkadattx]

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

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

[alatar]

При чем тут вектор и массив? связанный список != Vector.
В любом случаe, смысла в замене нет (http://jacksondunstan.com/articles/636).

[wvxvw]

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

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

[-De-]

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

[wvxvw]

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

[-De-]

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

[wvxvw]

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

[Sintesis]

Вот есть несколько задач с АСМ ICPC 2011 (http://cm.baylor.edu/digital/icpc2011.pdf). Как можно такое решать, ещё и за короткое время.