IPB
ЛогинПароль:

> Правила раздела!

1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!

 
 Ответить  Открыть новую тему 
> Массив, Манипуляции с памятью
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 13
Пол: Мужской
Реальное имя: Тимур

Репутация: -  0  +


Слышал, есть быстрый способ сдвинуть элементы массива. Какие-то манипуляции с самой памятью. Может кто знает как это сделать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гуру
*****

Группа: Пользователи
Сообщений: 1 220
Пол: Мужской

Репутация: -  16  +


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

Сообщение отредактировано: Ozzя -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 13
Пол: Мужской
Реальное имя: Тимур

Репутация: -  0  +


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


Гость






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

Цитата(TP Help)
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, которая одинаково корректно работает и с перекрывающимися, и с неперекрывающимися фрагментами массивов...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 13
Пол: Мужской
Реальное имя: Тимур

Репутация: -  0  +


Она быстро работает (в отличии от алгоритма)? Например, если необходимо так сдвинуть 10000 тысяч элементов?
Дело в том, что на олимпиаде мне будет дорога каждая мс.
Если она действительно шустрая, то легче ей пользоваться, чем списками rolleyes.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






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

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

Все зависит от задачи, которую ты решаешь. Кстати, на олимпиаде использование Move могут и запретить...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гуру
*****

Группа: Пользователи
Сообщений: 1 220
Пол: Мужской

Репутация: -  16  +


Цитата(volvo @ 16.12.2006 15:52) *

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

Обязательно. yes2.gif
И снимут очки с этой задачи.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 13
Пол: Мужской
Реальное имя: Тимур

Репутация: -  0  +


Цитата(Ozzя @ 16.12.2006 14:47) *

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

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

Ну вроде вопросов боле нет, пока
Спасибо
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Ozzя @ 16.12.2006 14:47) *

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


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

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

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

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

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

P.S. извините за doc ссылку, вирусов там нет; ссылке несколько лет уже smile.gif Могу залить в пдф.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 21.09.2020 19:40
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name