Массив, Манипуляции с памятью Опции

[Тём@]

Слышал, есть быстрый способ сдвинуть элементы массива. Какие-то манипуляции с самой памятью. Может кто знает как это сделать?

[Ozzя]

Если непрерывную последовательность элементов массива, то move

Сообщение отредактировано: Ozzя - 16.12.2006 14:03

[Тём@]

move это на ассемблере?
Можно подробнее? Как реализуется?
Для примера: в массив состоящий из 100 элементов, между 10-ым и 11-ым вставить ещё одно.
То есть нужно сдвинуть все элементы с одиннадцатого.
Если нельзя часть сдвинуть, то как все?
Я ассемблера не знаю. Пишу в среде паскаля

[volvo]

Move - это встроенная процедура Паскаля:

Move (procedure)
Copies bytes from source to dest.
Declaration:
procedure Move(var Source, Dest; Count: Word);
Remarks: Copies a specified number of contiguous bytes (Count) from a source range to a destination range. No range-checking is performed. Whenever possible, use SizeOf to determine the count.

, то есть для того, чтобы вот в таком массиве:

Var arr: array[1 .. 100] of integer;

передвинуть все элементы с 11-го до конца массива на одно значение вправо, достаточно сделать:

Move(a[10], a[11], (100 - 10) * sizeof(integer));

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

[Тём@]

Она быстро работает (в отличии от алгоритма)? Например, если необходимо так сдвинуть 10000 тысяч элементов?
Дело в том, что на олимпиаде мне будет дорога каждая мс.
Если она действительно шустрая, то легче ей пользоваться, чем списками

[volvo]

Она ОЧЕНЬ быстро работает - если надо именно сдвигать ВСЕ данные каждый раз, то быстрей, чем Move ты не сдвинешь.

Только вот не всегда надо двигать все элементы. Если ты работаешь со списком, иногда достаточно один раз найти позицию, и потом в нее "положить" подряд, скажем, 10 элементов (каждая операция вставки - смена нескольких указателей, каждый сдвиг через Move - десятки тысяч перемещений, что быстрее?)

Все зависит от задачи, которую ты решаешь. Кстати, на олимпиаде использование Move могут и запретить...

[Ozzя]

Кстати, на олимпиаде использование Move могут и запретить...

Обязательно.
И снимут очки с этой задачи.

[Тём@]

Обязательно.
И снимут очки с этой задачи.

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

Ну вроде вопросов боле нет, пока
Спасибо

[Michael_Rybak]

Обязательно.
И снимут очки с этой задачи.

Мувом пользовался постоянно, пока не перешел на си++ (и на memcpy соответственно : ) ; никогда не запрещали нигде С чего это вдруг; запрещены только ассемблерные вставки.

2 Тём@: настоятельно рекомендую ознакомиться с лекциями белоруса Ивана Метельского, золотого медалиста на студенческой 2004 года. Там очень классно написано об очень классных структурах данных. Бесценное чтиво для олимпиад и вообще.

Что касается твоего вопроса конкретно, есть такая прикольная стуктура, в которой операции выполняются за корень.

Смотри, пусть тебе надо оперировать с массивом длиной 10000 элементов. Заводим 100 массивов, по 200 элементов в каждом. Первые 100 элементов помещаем в первый массив, вторые 100 - во второй, и т.д. Таким образом, каждый из массивов заполнен наполовину. Теперь чтобы что-то куда-то вставить, работаем только с тем из малых массивов, в котором находится место, в которое надо вставлять/удалять. Каждый раз, когда какой-то из малых массивов заполняется полностью (200), мы сливаем всё обратно в большой массив, и перераспределяем, как в начале.

Перераспределение выполняется за O(n), но делать его придется не чаще, чем каждые sqrt(n) операций. Поэтому все действия выполняеются за O(sqrt(n)).

P.S. извините за doc ссылку, вирусов там нет; ссылке несколько лет уже Могу залить в пдф.