WikiDer > Своп (компьютерное программирование)

Swap (computer programming)
Не путать с Виртуальная память, известный в некоторых операционных системах как «своп».

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

data_item x: = 1data_item y: = 0swap (x, y);

После выполнения swap () Икс будет содержать значение 0 и у будет содержать 1; их ценности были обменены. Эта операция может быть обобщена для других типов значений, таких как струны и агрегированные типы данных. Сортировки сравнения используйте свопы для изменения положения данных.

Во многих языки программирования своп функция встроен. В C ++, перегрузки предоставляются, позволяя std :: swap обмениваться некоторыми большими структурами за время O (1).

Использование временной переменной

Смотрите также: Кэш процессора

Самый простой и, вероятно, наиболее широко используемый способ поменять местами две переменные - использовать третью временная переменная:

определить swap (x, y) temp: = x x: = y y: = temp

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

Кроме того, замена двух переменных в объектно-ориентированный языки, такие как C ++ может включать один звонок в учебный класс конструктор и деструктор для временной переменной и три вызова конструктор копирования. Некоторые классы могут выделять память в конструкторе и освобождать ее в деструкторе, тем самым создавая дорогостоящие вызовы системы. Конструкторы копирования для классов, содержащих много данных, например в множество, может даже потребоваться скопировать данные вручную.

Замена XOR

Основная статья: Алгоритм обмена XOR

Своп XOR использует XOR операция по замене двух числовых переменных. Обычно он рекламируется как более быстрый, чем упомянутый выше наивный метод; однако у него есть недостатки. Обмен XOR обычно используется для обмена низкоуровневыми типами данных, например целые числа. Однако теоретически он может поменять местами любые два значения, которые могут быть представлены фиксированной длиной биты.

Замена четырех

Квадратный своп, используемый quadsort, требует четырех переменных и четырех временных переменных. Переменные частично сортируются во временные переменные, затем они полностью сортируются обратно в исходные переменные. Это дает потенциальное вычислительное преимущество, хотя для выполнения одной четырехъядерной замены требуется более 40 строк кода.

Менять местами сложение и вычитание

Основная статья: Поменять местами сложением и вычитанием

Этот метод меняет местами две переменные, складывая и вычитая их значения. Это редко используется в практических приложениях, в основном потому, что:

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

Обмен контейнеров

Контейнеры которые выделяют память из куча с помощью указатели можно поменять местами за одну операцию, просто поменяв местами указатели. Обычно это встречается в языках программирования, поддерживающих указатели, например C или же C ++. В Стандартная библиотека шаблонов перегружает свою встроенную функцию подкачки для эффективного обмена содержимым контейнеров таким образом.[1]

Поскольку переменные-указатели обычно имеют фиксированный размер (например, большинство настольных компьютеров имеют указатели 64 биты long), и они числовые, их можно быстро поменять местами с помощью Замена XOR.

Параллельное задание

Некоторые языки, например Рубин или же Python поддерживать параллельные задания, что упрощает обозначение замены двух переменных:

а, б = б, а

Это сокращение для операции с промежуточной структурой данных: в Python - кортеж; в Ruby - массив.

Javascript 6+ поддерживает операторы деструктуризации, которые делают то же самое:

[а, б] = [б, а];

Облегчение замены в современных компьютерах

Специальные инструкции

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

XCHG может быть не таким эффективным, как кажется. Например, в x86 процессоры, XCHG неявно заблокирует доступ к любым операндам в объем памяти чтобы гарантировать, что операция атомный, и поэтому может быть неэффективным при подкачке памяти. Такая блокировка важна, когда она используется для реализации потоковобезопасной синхронизации, как в мьютексы. Однако XCHG обычно это самый быстрый способ поменять местами два машинных слова, находящихся в регистры. Регистрация переименования также может использоваться для эффективной замены регистров.

Параллельное исполнение

С появлением конвейерная обработка инструкций в современных компьютерах и многоядерные процессоры облегчение параллельные вычисления, одновременно могут выполняться две или более операций. Это может ускорить обмен с использованием временных переменных и дать ему преимущество перед другими алгоритмами. Например, Алгоритм обмена XOR требует последовательного выполнения трех инструкций. Однако, используя два временных регистра, два процессора, выполняющиеся параллельно, могут менять местами две переменные за два такта:

Шаг 1 Процессор 1: temp_1: = X Процессор 2: temp_2: = YШаг 2 Процессор 1: X: = temp_2 Процессор 2: Y: = temp_1

Это требует меньше инструкций; но могут использоваться и другие временные регистры, и вместо трех требуются четыре инструкции. В любом случае, на практике это не могло быть реализовано в отдельных процессорах, так как это нарушает условия Бернштейна для параллельных вычислений. Было бы невозможно поддерживать достаточную синхронизацию процессоров друг с другом, чтобы этот обмен имел какое-либо существенное преимущество перед традиционными версиями. Однако его можно использовать для оптимизации подкачки для одного процессора с несколькими модулями загрузки / сохранения.

Рекомендации

  1. ^ [1]