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

[Sherman]

2dimagolov
BTW, непрерывный место в памяти гарантируется только под массивы.

 

[dimagolov]

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

это для статики. а еще malloc выделяет непрерывное место в памяти, а какую структуру ты там разместишь, это твое личное дело.

 

[Sherman]

2dimagolov

Можно пруфлинк на то, что гарантируется, что "malloc выделяет непрерывное место в памяти" произвольного размера ?

И причем тут статическое выделение памяти? По-моему вы все напутали.

 

[Вурдалак]

offtopic:

Sherman
А ты на каком факультете учился?

 

[dimagolov]

Sherman, какой кафиг пруфлинк? ты вообще представить можешь, как можно запросить N байт, получить на них указатель и при этом выделено будет не одним непрерывным блоком?

 

[phprus]

Sherman

Можно пруфлинк на то, что гарантируется, что "malloc выделяет непрерывное место в памяти" произвольного размера ?

А это что (man malloc):

malloc() allocates size bytes and returns a pointer to the allocated memory.

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

И причем тут статическое выделение памяти? По-моему вы все напутали.

При том, что объявление переменных в виде:

void foo() {
    any_type a,b;
}

НЕ гарантирует, что а и b будут находиться в памяти друг за другом (из-за выравнивания между ними может быть промежуток).
А вот объявление вида:

void foo() {
    any_type bar[N];
}

Гарантирует, что сразу после bar[0] начнется bar[1] без всяких промежутков.

 

[Вурдалак]

Кстати, если кого-то интересует как устроена malloc(), то см. K&R, «8.7 Пример распределения памяти»

 

[.des.]

Автор оригинала: Sherman
2dimagolov

Можно пруфлинк на то, что гарантируется, что "malloc выделяет непрерывное место в памяти" произвольного размера ?

И причем тут статическое выделение памяти? По-моему вы все напутали.

А как вы представляете реализацию если malloc не будет выделять непрерывный участок памяти?
Другое дело что по стандарту последовательные вызовы malloc не гарантируют какое либо порядок взаимного расположения выделенных участков.

 

[Sherman]

2dimagolov
Не забывайте про контекст обсуждения(решение задачи)

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

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

Если вы именно это и имели в виду, тогда я просто не понял этого из вашего описания решения.

-~{}~ 28.02.10 23:03:

2phprus
Ровно об этом и написал(причем пару раз уже).
Про статическое выделение памяти. Это же просто память выделенная для переменных с ключевым словом static. И она не имеет никакого отношения к непрерывности выделения памяти. Оно влияет только на время жизни и на физ. размещение данных.

2all
Тем не менее, есть ли еще какие-то интересные решения этой задачки, без помощи массива, или будем и далее читать маны вслух ? ;-)

 

[dimagolov]

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

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

 

[Sherman]

2dimagolov
Да могли бы просто написать. Размещаем все элементы списка в массиве, да и все

 

[dimagolov]

термин "статическое" был применено в смысле "не динамическое", то есть выделение памяти под массив не malloc-ом, а декларацией массива (не указателя). те, кто внимательно читал тему это поняли

-~{}~ 28.02.10 16:15:

чтобы объявить массив нужно заранее знать его размер, а этого мы не знаем

 

[Adelf]

dimagolov
один проход по списку и мы знаем размер массива.

 

[dimagolov]

Adelf, ты мой пост весь читал? или только последнюю фразу? давайте завязывать с флудом.

 

[Sherman]

Мой вариант решения. 3 итерации на алгоритм.

http://hpaste.org/fastcgi/hpaste.fcgi/view?id=23108#a23109

Мне пришлось жульничать немного. Я добавил еще одну переменную tail для того, чтобы хранить хвост списка, иначе нельзя было бы сделать вставку нового элемента в список за время O(1). Поле length используется __только__ для генерации random.

p.s. Интересно решение на си.

-~{}~ 01.03.10 03:39:

2dimagolov
>термин "статическое" был применено в смысле "не динамическое"
Я не гуру си, но статическое выделение памяти отличается от выделения памяти в стеке(то что вы имели в виду). Причем, на некоторых устройствах, думаю, существенно.

 

[Вурдалак]

Sherman
Там не должно быть генерации псевдослучайных чисел.

 

[Sherman]

2Вурдалак
Генерация используется только для заполнения поля random у элементов первоначального списка.

 

[Adelf]

Sherman
Так ты же двойной обьем памяти использовал
Так нельзя.

 

[Sherman]

2Adelf

По-моему это уже выяснили. Памяти можно использовать ровно на еще один список, иначе как ты собираешься сделать _копию_?

 

[Adelf]

Sherman
Но ты выделяешь дополнительной памяти не на один список, а на два(это в дополнение к существующему). А потом удаляешь дополнительные элементы.