[конкурс] Формирование условий

Kernel3> Напишите копирование списка с пропусками, оптимизированное по потреблению памяти (это не я придумал, в Гугле на собеседовании такую задачку дают, среди прочих) Это не на денёк, правда, а на полчасика-часик где-то, ну так тем быстрее результат будет
Меня интересует — а в чём отличие от копирования орграфа без циклов (леса деревьев)? И почему сразе не предложить скопировать просто граф (произвольный)? Список с пропусками имеет смысл только с присвоенной ему семантикой, которая копируется структурой (частично) и совсем не копируется в том смысле, как алгорит построения. Т.е. отличия от орграфа без циклов с точки зрения копирования нет.

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

Kernel3> Ага. Я ж говорю: не я это придумал Видимо, автары это задание придумали разбирая некий конкретный метод, требовавший (или являющийся оптимальным с) списки с пропусками.
Дык, семантика внешняя — только вероятность. Копируется на раз. Остальное — орграф без циклов.

Mishka> Кстати, вот тут можно поизвращаться над частично асинхронным копирование. Поскольку элемент верхнего списка гарантированно входит в нижний, то задав копирование элемента верхнего списка, надо остановится и ждать, пока в нижнем списке не будет скопирован такой же, чтобы получить ссылку на него и завершить копирование. Этакое рекурсивное рандеву. При последовательном копировании надо делать рекурсию с отложенным завершением и приостановкой в момент копирования найденного элемента из верхнего списка. Хм, это даже рекурсией назвать сложно. Этакое сохранение контекста подзадачи до тех пор, пока копирование не завершено с синхронизацией по заданному элементу от верхнего списка. Зато за один проход завершается.

Это было бы прикольно, но во-первых - велика вероятность того, что в интернете есть, а во-вторых - больно уж частная задачка, элемент случайности будет слишком велик. Парсер таки лучше в свете конкурса, имхо. Тем более, что Реконструктор изначально полагал, что на Java писать парсеры невозможно.

Сергей-4030> Это было бы прикольно, но во-первых - велика вероятность того, что в интернете есть, а во-вторых - больно уж частная задачка, элемент случайности будет слишком велик. Парсер таки лучше в свете конкурса, имхо. Тем более, что Реконструктор изначально полагал, что на Java писать парсеры невозможно.

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