Циклический сдвиг вектора c (2 видео) | Курс школьной геометрии

Содержание

Циклический сдвиг вектора c
Рекомендации по циклическим сдвигам (поворот) в С++
ОТВЕТЫ
Ответ 1
Ответ 2
Ответ 3
Циклический сдвиг вектора c
Вступление
Алгоритм #1: последовательный обмен
Алгоритм #2: перестановка блоков
Алгоритм #3: переворотами
📸 Видео

Видео:Копирование массива, реверс циклический сдвиг на СиСкачать

Циклический сдвиг вектора c

Пример. Циклический сдвиг. При циклическом сдвиге (вправо) первый элемент переходит на место второго, второй на место третьего и т.д., а последний элемент — на место первого.

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

Видео:Программирование на С++. Урок 33. Циклический сдвиг элементов массиваСкачать

ОТВЕТЫ

Ответ 1

См. также более раннюю версию этого ответа на другой вопрос поворота с более подробной информацией о том, что asm gcc/clang создает для x86.

Наиболее удобным для компилятора способом выражения поворота в C и C++, позволяющим избежать любого неопределенного поведения, является реализация Джона Рейгера. Я адаптировал его для поворота по ширине шрифта (используя типы с фиксированной шириной, такие как uint32_t ).

Работает для любого целого типа без знака, не только uint32_t , поэтому вы можете создавать версии для других размеров.

См. также шаблонную версию C++ 11 со множеством проверок безопасности (включая static_assert , в котором ширина типа равна степени 2), чего нет в некоторых 24- битные DSP или 36-битные мэйнфреймы, например.

Я бы рекомендовал использовать шаблон только в качестве серверной части для упаковщиков с именами, в которых явно указана ширина поворота. Правила продвижения целых чисел означают, что rotl_template(u16 & 0x11UL, 7) будет выполнять 32- или 64-разрядное вращение, а не 16 (в зависимости от ширины unsigned long ). Даже uint16_t & uint16_t повышается до signed int по правилам целочисленного продвижения C++, за исключением платформ, где int не шире, чем uint16_t .

В x86 эта версия встроена в один rol r32, cl (или rol r32, imm8 ) с компиляторами, которые его обманывают, потому что компилятор знает, что x86 маскирует инструкции поворота и сдвига число сдвигов точно так же, как это делает источник C.

Поддержка компилятора для этой идиомы избегания UB на x86, для uint32_t x и unsigned int n для сдвигов с переменным числом:

clang: распознается для поворотов с переменным числом, начиная с clang3.5, с несколькими сменами + или insns до этого.
gcc: распознается для поворотов с переменным числом, начиная с gcc4.9, с несколькими сменами + или insns до этого. gcc5 и более поздние версии оптимизируют удаление ветки и маски в версии википедии, используя только инструкцию ror или rol для подсчета переменных.
icc: поддерживается для поворота с переменным числом, начиная с ICC13 или более ранней версии. Вращающиеся с постоянным счетом используют shld edi,edi,7 , который медленнее и занимает больше байтов, чем rol edi,7 на некоторых процессорах (особенно AMD, но также и на некоторых Intel), когда BMI2 недоступен для rorx eax,edi,25 для сохранения MOV.
MSVC: x86-64 CL19: распознается только при поворотах с постоянным счетом. (Идиома википедии распознается, но ветвь и AND не оптимизированы). Используйте встроенные функции _rotl / _rotr из в x86 (включая x86-64).

gcc для ARM использует and r1, r1, #31 для поворота с переменным счетом, но все еще выполняет фактическое вращение с помощью одной инструкции: ror r0, r0, r1 . Таким образом, gcc не понимает, что число поворотов является модульным. Как сказано в документации ARM, «ROR с длиной смещения, n , более 32 — это то же самое, что ROR с длиной смещения n-32 «. Я думаю, что gcc здесь запутался, потому что сдвиги влево/вправо на ARM насыщают счет, поэтому сдвиг на 32 или больше очистит регистр. (В отличие от x86, где сдвиги маскируют счет так же, как и вращение). Вероятно, он решает, что ему нужна инструкция AND перед распознаванием идиомы поворота, из-за того, как некруглые сдвиги работают на этой цели.

Текущие x86-компиляторы все еще используют дополнительную инструкцию для маскирования счетчика переменных для 8- и 16-битных поворотов, вероятно, по той же причине, по которой они не избегают AND на ARM. Это пропущенная оптимизация, поскольку производительность не зависит от числа оборотов на любом процессоре x86-64. (Маскирование счетчиков было введено с 286 по соображениям производительности, потому что оно обрабатывает сдвиги итеративно, а не с постоянной задержкой, как современные процессоры.)

Кстати, предпочитайте rotate-right для переменных с переменным числом, чтобы не заставлять компилятор делать 32-n для реализации левого поворота на архитектурах, таких как ARM и MIPS, которые предоставляют только rotate-right. (Это оптимизирует счетчик времени компиляции.)

Интересный факт: ARM на самом деле не имеет специальных команд сдвига/поворота, это просто MOV с операндом источника , проходящим через бочкообразный переключатель в режиме ROR: mov r0, r0, ror r1 . Таким образом, вращение может сложиться в операнд источника-регистра для инструкции EOR или чего-то еще.

Убедитесь, что вы используете беззнаковые типы для n и возвращаемого значения, иначе это не будет поворот. (gcc для целей x86 выполняет арифметическое смещение вправо, смещение копий знака-знака, а не нуля, что приводит к проблеме, когда вы OR смещаете два сдвинутых значения вместе. Сдвиг вправо отрицательных целых чисел со знаком — это поведение, определяемое реализацией в C)

Кроме того, убедитесь, что счетчик сдвига относится к типу без знака, потому что (-n)&31 со типом со знаком может быть одним дополнением или знаком/величиной, а не тем же модульным 2 ^ n, который вы получаете с помощью без знака или два дополнения. (См. комментарии к сообщению в блоге Regehr). unsigned int хорошо работает на каждом компиляторе, на который я смотрел, для любой ширины x . Некоторые другие типы фактически игнорируют распознавание идиомы для некоторых компиляторов, поэтому не просто используйте тот же тип, что и x .

Некоторые компиляторы предоставляют встроенные функции для поворота, что намного лучше, чем inline-asm, если переносимая версия не генерирует хороший код на компиляторе, на который вы ориентируетесь. Не существует кроссплатформенных встроенных функций для каких-либо известных мне компиляторов. Вот некоторые из вариантов x86:

Документы Intel, которые предоставляют встроенные функции _rotl и _rotl64 , и то же самое для сдвига вправо. MSVC требует , в то время как gcc требует . #ifdef заботится о gcc против icc, но, похоже, clang их нигде не предоставляет, кроме режима совместимости MSVC с -fms-extensions -fms-compatibility -fms-compatibility-version=17.00 . И asm, который он испускает для них, — отстой (дополнительная маскировка и CMOV).
MSVC: _rotr8 и _rotr16 .
gcc и icc (не clang): также предоставляет __rolb / __rorb для 8-битного поворота влево/вправо, __rolw / __rorw (16-бит), __rold / __rord ( 32-битный), __rolq / __rorq (64-битный, определен только для 64-битных целей). Для узких поворотов реализация использует __builtin_ia32_rolhi или . qi , но 32- и 64-разрядные повороты определяются с помощью shift/или (без защиты от UB, потому что код только в ia32intrin.h должен работать на gcc для x86). Похоже, что GNU C не имеет кроссплатформенных функций __builtin_rotate , как для __builtin_popcount (которые расширяются до оптимального уровня на целевой платформе, даже если это не единственная инструкция). Большую часть времени вы получаете хороший код от распознавания идиом.

Предположительно, некоторые не x86-компиляторы тоже имеют встроенные функции, но давайте не будем расширять этот вики-ответ сообщества, чтобы включить их все. (Возможно, сделайте это в существующем ответе о встроенных функциях).

(В старой версии этого ответа предлагался встроенный asm для MSVC (который работает только для 32-битного кода x86), или http://www.devx.com/tips/Tip/14043 для версии C. На это отвечают комментарии.)

Встроенный asm побеждает многие оптимизации, , особенно в стиле MSVC, поскольку он заставляет входные данные быть сохраненными/перезагруженными. Тщательно написанное вращение in-asm в GNU C позволило бы счету быть непосредственным операндом для счетчиков смещения во время компиляции, но он все равно не мог оптимизировать полностью, если значение, которое должно быть смещено, также является константой времени компиляции после встраивания. https://gcc.gnu.org/wiki/DontUseInlineAsm.

Ответ 2

Так как это С++, используйте встроенную функцию:

Ответ 3

Большинство компиляторов имеют для этого встроенные функции. Visual Studio, например _ rotr8, _rotr16

Видео:Циклический сдвиг в одномерном массивеСкачать

Циклический сдвиг вектора c

Главная >> Каталог задач >> Последовательности >> Массивы >> Циклический сдвиг одномерного массива или строки, 3 уникальных алгоритма

Вступление

Задача циклического сдвига одномерного массива из n элементов на i позиций влево. Например, если n=8, a i=3, вектор «abcdefgh» должен будет превратиться в «defghabc». Дело в том, что алгоритм решения такой казалось бы ничем не выдающейся задачки играет большую роль, например, во всяческих различного рода текстовых редакторах, в каждом из которых сейчас уже обязательно присутствует такая возможность, как выделение мышкой текста и последующего его перемещения как есть в любое другое место редактируемого файла.

И вот если использовать очевидное решение в лоб: использовать n-элементный вспомогательный массив и сделав n шагов завершить всю перестановку — мы натыкаемся на дополнительный расход памяти, пропорционально растущий от объема этого выделенного, перемещаемого текста. Представьте себе, если выделяется текст большого объема, например, в миллион символов и перемещается. В этом случае весь этот миллион символов(байт) — а это уже мегабайт, будет занимать ценное место в оперативной памяти.

Поэтому было бы неплохо найти решение, которое осуществляло бы эту перестановку без дополнительного расхода памяти, по-крайней мере, чтобы этот расход не рос пропорционально объему сдвигаемого фрагмента.

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

По книге Джона Бентли:
«Жемчужины программирования»

«. В некоторых языках программирования операция циклического сдвига является элементарной (то есть выполняется одним оператором). Для нас важно, что циклический сдвиг соответствует обмену соседних блоков памяти разного размера: при перемещении фрагмента текста с помощью мыши из одного места файла в другое осуществляется именно эта операция. Ограничения по времени и объему памяти существенны для многих подобных приложений.

Можно попытаться решить задачу, копируя первые i элементов массива х во временный массив, сдвигая оставшиеся n-i элементов влево на i позиций, а затем копируя данные из временного массива обратно в основной массив на последние i позиций. Однако данная схема использует i дополнительных переменных, что требует дополнительной памяти. Другой подход заключается в том, чтобы определить функцию, сдвигающую массив влево на один элемент (за время, пропорциональное n), а потом вызывать ее i раз, но такой алгоритм будет отнимать слишком много времени.

Алгоритм #1: последовательный обмен

Решение проблемы с указанными ограничениями на использование ресурсов потребует написания более сложной программы. Одним из вариантов решения будет введение дополнительной переменной. Элемент х[0] помещается во временную переменную t, затем x[i] помещается в x[0],x[2*i] — в х[1] и так далее (перебираются все элементы массива х с индексом по модулю n), пока мы не возвращаемся к элементу х [0], вместо которого записывается содержимое переменной t, после чего процесс завершается. Если i = 3, а n = 12, этот этап проходит следующим образом (рис. 2.2):

Если при этом не были переставлены все имеющиеся элементы, процедура повторяется, начиная с х[1] и так далее, до достижения конечного результата:

Алгоритм #2: перестановка блоков

Можно предложить и другой алгоритм, который возникает из рассмотрения задачи с другой точки зрения. Циклический сдвиг массива х сводится фактически к замене ab на bа, где а — первые i элементов х, a b — оставшиеся элементы. Предположим, что а короче b. Разобьем b на b_left и b_right, где b_right содержит i элементов (столько же, сколько и а). Поменяем местами а и b_right, получим b_rightb_leftа. При этом а окажется в конце массива — там, где и полагается. Поэтому можно сосредоточиться на перестановке b_right и b_left. Эта задача сводится к начальной, поэтому алгоритм можно вызывать рекурсивно. Программа, реализующая этот алгоритм, будет достаточно красивой , но она требует аккуратного написания кода, а оценить ее эффективность непросто:

Алгоритм #3: переворотами

Задача кажется сложной, пока вас не осенит озарение («ага!»): итак, нужно преобразовать массив ab в bа. Предположим, что у нас есть функция reverse, переставляющая элементы некоторой части массива в противоположном порядке. В исходном состоянии массив имеет вид ab. Вызвав эту функцию для первой части, получим а r b (прим. редактора:а r — это модифицированная часть a, к которой применили фукнцию перестановки reverse). Затем вызовем ее для второй части: получим а r b r . Затем вызовем функцию для всего массива, что даст (а r b r ) r , а это в точности соответствует bа. Посмотрим, как будет такая функция действовать на массив abcdefgh, который нужно сдвинуть влево на три элемента:

Дуг Макилрой (Doug Mcllroy) предложил наглядную иллюстрацию циклического сдвига массива из десяти элементов вверх на пять позиций (рис. 2.3); начальное положение: обе руки ладонями к себе, левая над правой:

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

Б. Керниган и П. Дж. Плоджер пользовались именно этим методом для перемещения строк в текстовом редакторе в своей книге (В. Kernighan, P. J. Plauger, Software Tools in Pascal, 1981). Керниган пишет, что эта функция заработала правильно с первого же запуска, тогда как их предыдущая версия, использовавшая связный список, содержала несколько ошибок. Этот же код используется в некоторых текстовых редакторах, включая тот, в котором я впервые набрал настоящую главу. Кен Томпсон (Ken Thompson) написал этот редактор с функцией reverse в 1971 году, и он утверждает, что она уже тогда была легендарной.