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

[-De-]

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

[alatar]

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

[arkadattx]

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

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

[alatar]

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

[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. Как можно такое решать, ещё и за короткое время.