Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Теоретические вопросы _ Массив
Автор: Тём@ 16.12.2006 12:44
Слышал, есть быстрый способ сдвинуть элементы массива. Какие-то манипуляции с самой памятью. Может кто знает как это сделать?
Автор: Ozzя 16.12.2006 14:02
Если непрерывную последовательность элементов массива, то move
Автор: Тём@ 16.12.2006 17:38
move это на ассемблере?
Можно подробнее? Как реализуется?
Для примера: в массив состоящий из 100 элементов, между 10-ым и 11-ым вставить ещё одно.
То есть нужно сдвинуть все элементы с одиннадцатого.
Если нельзя часть сдвинуть, то как все?
Я ассемблера не знаю. Пишу в среде паскаля
Автор: volvo 16.12.2006 18:02
Move - это встроенная процедура Паскаля:
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, которая одинаково корректно работает и с перекрывающимися, и с неперекрывающимися фрагментами массивов...
Автор: Тём@ 16.12.2006 18:36
Она быстро работает (в отличии от алгоритма)? Например, если необходимо так сдвинуть 10000 тысяч элементов?
Дело в том, что на олимпиаде мне будет дорога каждая мс.
Если она действительно шустрая, то легче ей пользоваться, чем списками 
Автор: volvo 16.12.2006 18:52
Она ОЧЕНЬ быстро работает - если надо именно сдвигать ВСЕ данные каждый раз, то быстрей, чем Move ты не сдвинешь.
Только вот не всегда надо двигать все элементы. Если ты работаешь со списком, иногда достаточно один раз найти позицию, и потом в нее "положить" подряд, скажем, 10 элементов (каждая операция вставки - смена нескольких указателей, каждый сдвиг через Move - десятки тысяч перемещений, что быстрее?)
Все зависит от задачи, которую ты решаешь. Кстати, на олимпиаде использование Move могут и запретить...
Автор: Ozzя 16.12.2006 19:47
Кстати, на олимпиаде использование Move могут и запретить...
Обязательно.
И снимут очки с этой задачи.
Автор: Тём@ 16.12.2006 22:30
Обязательно.
И снимут очки с этой задачи.
Ну это врядли
. В исходник жюри не лезут (по правилам), а чекер не настолько умный, обычно...Ну вроде вопросов боле нет, пока
Спасибо
Автор: Michael_Rybak 16.12.2006 23:53
Обязательно.
И снимут очки с этой задачи.
Мувом пользовался постоянно, пока не перешел на си++ (и на memcpy соответственно : ) ; никогда не запрещали нигде
С чего это вдруг; запрещены только ассемблерные вставки.2 Тём@: настоятельно рекомендую ознакомиться с http://byoi.narod.ru/lecture.doc белоруса Ивана Метельского, золотого медалиста на студенческой 2004 года. Там очень классно написано об очень классных структурах данных. Бесценное чтиво для олимпиад и вообще.
Что касается твоего вопроса конкретно, есть такая прикольная стуктура, в которой операции выполняются за корень.
Смотри, пусть тебе надо оперировать с массивом длиной 10000 элементов. Заводим 100 массивов, по 200 элементов в каждом. Первые 100 элементов помещаем в первый массив, вторые 100 - во второй, и т.д. Таким образом, каждый из массивов заполнен наполовину. Теперь чтобы что-то куда-то вставить, работаем только с тем из малых массивов, в котором находится место, в которое надо вставлять/удалять. Каждый раз, когда какой-то из малых массивов заполняется полностью (200), мы сливаем всё обратно в большой массив, и перераспределяем, как в начале.
Перераспределение выполняется за O(n), но делать его придется не чаще, чем каждые sqrt(n) операций. Поэтому все действия выполняеются за O(sqrt(n)).
P.S. извините за doc ссылку, вирусов там нет; ссылке несколько лет уже
Могу залить в пдф.