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

 
1 2 3 4 5 6 7 8
+
-
edit
 

Mishka

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

Kernel3

аксакал

Mishka> Т.е. отличия от орграфа без циклов с точки зрения копирования нет.
Ага. Я ж говорю: не я это придумал :) Видимо, автары это задание придумали разбирая некий конкретный метод, требовавший (или являющийся оптимальным с) списки с пропусками.
Broken Windows® cures my ills and makes me feel alright... ©  
+
-
edit
 

Mishka

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

Mishka

модератор
★★☆
Кстати, вот тут можно поизвращаться над частично асинхронным копирование. Поскольку элемент верхнего списка гарантированно входит в нижний, то задав копирование элемента верхнего списка, надо остановится и ждать, пока в нижнем списке не будет скопирован такой же, чтобы получить ссылку на него и завершить копирование. Этакое рекурсивное рандеву. При последовательном копировании надо делать рекурсию с отложенным завершением и приостановкой в момент копирования найденного элемента из верхнего списка. Хм, это даже рекурсией назвать сложно. :) Этакое сохранение контекста подзадачи до тех пор, пока копирование не завершено с синхронизацией по заданному элементу от верхнего списка. :F Зато за один проход завершается. :F
 
US Сергей-4030 #26.08.2008 18:08  @Mishka#26.08.2008 16:51
+
-
edit
 

Сергей-4030

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

Это было бы прикольно, но во-первых - велика вероятность того, что в интернете есть, а во-вторых - больно уж частная задачка, элемент случайности будет слишком велик. Парсер таки лучше в свете конкурса, имхо. Тем более, что Реконструктор изначально полагал, что на Java писать парсеры невозможно.
 
US Mishka #26.08.2008 18:26  @Сергей-4030#26.08.2008 18:08
+
-
edit
 

Mishka

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

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

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru