Массив - Форум «Всё о Паскале»

Правила форума :: Скачать Pascal :: FAQ // Ада–2020 :: Скачать GNAT :: OEM–2015 :: Ada -> C/C++

Сайт «Всё о Паскале» > Форум > Pascal, Object Pascal > Теоретические вопросы

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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

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

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

Опции

Тём@	16.12.2006 12:44 Сообщение #1
Новичок Группа: Пользователи Сообщений: 13 Пол: Мужской Реальное имя: Тимур Репутация: 0	Слышал, есть быстрый способ сдвинуть элементы массива. Какие-то манипуляции с самой памятью. Может кто знает как это сделать?

Ответов

volvo	16.12.2006 18:52 Сообщение #2
Гость	Она ОЧЕНЬ быстро работает - если надо именно сдвигать ВСЕ данные каждый раз, то быстрей, чем Move ты не сдвинешь. Только вот не всегда надо двигать все элементы. Если ты работаешь со списком, иногда достаточно один раз найти позицию, и потом в нее "положить" подряд, скажем, 10 элементов (каждая операция вставки - смена нескольких указателей, каждый сдвиг через Move - десятки тысяч перемещений, что быстрее?) Все зависит от задачи, которую ты решаешь. Кстати, на олимпиаде использование Move могут и запретить...

Ozzя	16.12.2006 19:47 Сообщение #3
Гуру Группа: Пользователи Сообщений: 1 220 Пол: Мужской Репутация: 16	Цитата(volvo @ 16.12.2006 15:52) Кстати, на олимпиаде использование Move могут и запретить... Обязательно. И снимут очки с этой задачи.

Michael_Rybak	16.12.2006 23:53 Сообщение #4
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32	Цитата(Ozzя @ 16.12.2006 14:47) Обязательно. И снимут очки с этой задачи. Мувом пользовался постоянно, пока не перешел на си++ (и на memcpy соответственно : ) ; никогда не запрещали нигде С чего это вдруг; запрещены только ассемблерные вставки. 2 Тём@: настоятельно рекомендую ознакомиться с лекциями белоруса Ивана Метельского, золотого медалиста на студенческой 2004 года. Там очень классно написано об очень классных структурах данных. Бесценное чтиво для олимпиад и вообще. Что касается твоего вопроса конкретно, есть такая прикольная стуктура, в которой операции выполняются за корень. Смотри, пусть тебе надо оперировать с массивом длиной 10000 элементов. Заводим 100 массивов, по 200 элементов в каждом. Первые 100 элементов помещаем в первый массив, вторые 100 - во второй, и т.д. Таким образом, каждый из массивов заполнен наполовину. Теперь чтобы что-то куда-то вставить, работаем только с тем из малых массивов, в котором находится место, в которое надо вставлять/удалять. Каждый раз, когда какой-то из малых массивов заполняется полностью (200), мы сливаем всё обратно в большой массив, и перераспределяем, как в начале. Перераспределение выполняется за O(n), но делать его придется не чаще, чем каждые sqrt(n) операций. Поэтому все действия выполняеются за O(sqrt(n)). P.S. извините за doc ссылку, вирусов там нет; ссылке несколько лет уже Могу залить в пдф.