алгоритмическая задачка

[Alexandre]

алгоритмическая задачка

вот столкнулся с задачкой:

Есть многосвязный список‚ заданный следующим образом:

struct list_item
{
     list_item *next; // указатель на следующий элемент списка   
     list_item *rand; // указатель на произвольный элемент списка 
};

и указатель на первый элемент списка

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

PS: у меня получилось 3 прохода (итерации).

 

[cDLEON]

memcpy(new_buffer,start_list_item,start_list_item+items_count*sizeof(list_item))?
хотя... Это всего-лишь вариант...наверняка у тебя список заполняется динамически....

 

[dimagolov]

cDLEON, это был стеб или ты серьезно?

Alexandre, не совсем понятно, в "копии" указатели на "случайный" элемент должны схранить порядок исходного списка или нет?

 

[Adelf]

dimagolov
скорее всего(хотя конечно указывать это надо в тексте задачи, тоже сомнения были). Иначе задачи просто нет.

 

[dimagolov]

Иначе задачи просто нет.

один раз построив список потом можно пройти и присвоить ссылку на случайный элемент в новом массиве. но при этом на каждом шаге нужно будет делать от 0 до N шагов по цепочке, вспомогательный массив-то сделать нельзя, то есть уже получается O(N^2) даже в таком упрощенном случае.

-~{}~ 27.02.10 22:18:

аналогично легко и копию случайной ссылки делать: запоминаем ссылку на случайный в оригинале, делаем параллельно проход по оригиналу в поисках запомненной ссылки и по копии, найдя запомненную ссылку в оригинале получаем нужную нам ссылку в копии. но это O(n^2)

 

[Alexandre]

не совсем понятно, в "копии" указатели на "случайный" элемент должны схранить порядок исходного списка или нет

есть список 10 элементов: (вместо id адреса памяти)
{7 2} {5 3} {1 4} {1 5} {5 6} {1 7} {3 8} {8 9} {1 0}
нужно создать его копию, так чтоб в новом списке указатель 2 указвал на 2й элемент нового списка, а 7 на 7й элемент этого же списка:
{7 2} {5 3} {1 4} {1 5} {5 6} {1 7} {3 8} {8 9} {1 0}.

то есть уже получается O(N^2) даже в таком упрощенном случае.

у меня получилось О(3n)

 

[Adelf]

>> у меня получилось О(3n)
Так не пишут Это O(n)

-~{}~ 28.02.10 14:48:

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

 

[dimagolov]

Alexandre, может я чего не понял? судя по твоему примеру у тебя не список а массив структур с указателями? если так, то задача резко упрощается. или это ты фигню в примере написал, где там линейная связанность по первому параметру?

 

[Вурдалак]

Автор оригинала: dimagolov
может я чего не понял? судя по твоему примеру у тебя не список а массив структур с указателями?

— неа, не понял. Списки — как раз-таки альтернатива массивам.

P.S. Интересно получается, что на PHP-форуме вопрос стоит в понимании условия

 

[dimagolov]

Вурдалак, а теперь посмотри на пример, который выложил Alexandre и покажи где там связанный список по первому указателю:

есть список 10 элементов: (вместо id адреса памяти)
{7 2} {5 3} {1 4} {1 5} {5 6} {1 7} {3 8} {8 9} {1 0}
нужно создать его копию, так чтоб в новом списке указатель 2 указвал на 2й элемент нового списка, а 7 на 7й элемент этого же списка:
{7 2} {5 3} {1 4} {1 5} {5 6} {1 7} {3 8} {8 9} {1 0}.

 

[Вурдалак]

Ну он, очевидно, просто сначала писал значение rand-указателя, а затем — на следующий элемент списка.

 

[dimagolov]

все равно, вопрос о том расположены структуры в непрерывном фрагменте памяти и упорядоченно или случайным образом критичен для подходов к решению задачи.

-~{}~ 28.02.10 10:12:

хотя, если оно в непрерывном фрагменте памяти, то все решается в один проход.

-~{}~ 28.02.10 10:14:

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

 

[baev]

Увидел вот это:
http://yandex.ru/yandsearch?text=struct+list_item+{++++++list_item+*next;+++++++++list_item+*rand;+++}
— сразу весь интерес пропал…

 

[TutanXamoN]

Ну с O(3*n) эту задачку думаю каждый сделает, а вот с O(n)...
У самого рациональных мыслей ноль.
Есть только иррациональная идея - если эл-ты первого списка расположены в памяти строго друг за другом то создавая последовательно копию ел-тов мы получим последовательность той же длинны, отсюда для установки правильных значений адреса list_rand в копии нам нужно взять адрес текущего ел-та оригинального списка отнять от него list_rand эл-та оригинального списка и полученное прибавить к адресу текущего эл-та копии.

Бред. Согласен. Сейчас буду думать.

 

[Вурдалак]

Автор оригинала: TutanXamoN
Ну с O(3*n) эту задачку думаю каждый сделает, а вот с O(n)...

— это одно и то же.

-~{}~ 28.02.10 19:21:

http://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое

 

[dr-sm]

по идее это односвязный список все-таки.

 

[Alexandre]

хотя, если оно в непрерывном фрагменте памяти, то все решается в один проход.

не факт что списки расположены в одном фрагменте памяти,

видел вот это:
http://yandex.ru/yandsearch?text=st...em+*rand;+++}
— сразу весь интерес пропал…

из http://www.sql.ru/forum/actualthread.aspx?tid=696706
сделано в 6 проходов у меня в 3!
а также

	// выделяем область памяти для копии списка длиной lenght,
	// таким образом, его элементы становятся проиндексированными 
	list_item *newList = new list_item[lenght];

нельзя что либо дополнительно выделять
Это одно из основных условий!

-~{}~ 28.02.10 20:22:

по идее это односвязный список все-таки.

так и есть - односвязанный список с элементом данных!

 

[Sherman]

А на 5 можно попросить написать thread safe версию ;-)

>нельзя что либо дополнительно выделять

А я понял условие так, что нельзя выделять памяти более, чем n*sizeof(elt). А у вас решение, требующее константного размера памяти?

 

[phprus]

Alexandre

нельзя что либо дополнительно выделять
Это одно из основных условий!

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

Sherman

А у вас решение, требующее константного размера памяти?

Если это так, то тут надо нобелевку давать за архивацию любого объема данных в блок памяти константного размера

 

[dimagolov]

Alexandre, в том решении память выделяется не дополнительно, а под новый список. Собственно там решение в ключе моей идеи:

хотя, если оно в непрерывном фрагменте памяти, то все решается в один проход.

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