В компьютерном программировании действие обмена двух переменных относится к взаимному обмену значениями переменных. Обычно это делается с данными в памяти . Например, в программе две переменные могут быть определены следующим образом (в псевдокоде ):
элемент_данных x := 1data_item у := 0поменять местами (x, y);
После выполнения swap() x будет содержать значение 0, а y будет содержать 1; их значения поменялись местами. Эту операцию можно обобщить на другие типы значений, такие как строки и агрегированные типы данных . Сортировки сравнения используют обмены для изменения позиций данных.
Во многих языках программирования функция swap встроена. В C++ предусмотрены перегрузки, позволяющие std::swap обмениваться некоторыми большими структурами за время O(1).
Самый простой и, вероятно, наиболее широко используемый метод замены двух переменных — это использование третьей временной переменной :
определить обмен (x, y) темп := х х := у у := темп
Хотя это концептуально просто и во многих случаях является единственным удобным способом поменять две переменные, он использует дополнительную память. Хотя это не должно быть проблемой в большинстве приложений, размеры заменяемых значений могут быть огромными (что означает, что временная переменная также может занимать много памяти), или операцию по замене может потребоваться выполнить много раз, как в алгоритмах сортировки.
Кроме того, замена двух переменных в объектно-ориентированных языках, таких как C++, может включать один вызов конструктора класса и деструктора для временной переменной и три вызова конструктора копирования . Некоторые классы могут выделять память в конструкторе и освобождать ее в деструкторе, тем самым создавая дорогие вызовы к системе. Конструкторы копирования для классов, содержащих много данных, например, в массиве , могут даже потребовать копирования данных вручную.
XOR swap использует операцию XOR для обмена двух числовых переменных. Обычно его рекламируют как более быстрый, чем наивный метод, упомянутый выше; однако у него есть недостатки . XOR swap обычно используется для обмена низкоуровневых типов данных, таких как целые числа . Однако, теоретически, он способен менять местами любые два значения, которые могут быть представлены битовыми строками фиксированной длины .
Этот метод меняет местами две переменные, добавляя и вычитая их значения. Это редко используется в практических приложениях, в основном потому, что:
Контейнеры , которые выделяют память из кучи с помощью указателей , могут быть заменены одной операцией, путем замены только указателей. Это обычно встречается в языках программирования, поддерживающих указатели, таких как C или C++ . Стандартная библиотека шаблонов перегружает свою встроенную функцию подкачки для эффективного обмена содержимым контейнеров таким образом. [1]
Поскольку переменные указателя обычно имеют фиксированный размер (например, большинство настольных компьютеров имеют указатели длиной 64 бита ) и являются числовыми, их можно быстро поменять местами с помощью операции XOR.
Некоторые языки, такие как Ruby или Python, поддерживают параллельные присваивания , что упрощает запись для обмена двух переменных:
а, б = б, а
Это сокращение от операции, включающей промежуточную структуру данных: в Python — кортеж, в Ruby — массив.
Javascript 6+ поддерживает операторы деструктуризации, которые делают то же самое:
[а, б] = [б, а];
Здесь две переменные с глобальной областью действия передаются по значению через функцию, что устраняет необходимость во временной переменной хранения.
х = 1 ; у = 2 ; console.log ( x + "" + y ); // выводит 1 2 функция обмена ( a , b ) { x = b ; y = a ; } поменять местами ( x , y ); console.log ( x + "" + y ); // выводит 2 1 Из-за множества приложений обмена данными в компьютерах большинство процессоров теперь предоставляют возможность обменивать переменные напрямую через встроенные инструкции. Например, процессоры 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
Используется больше временных регистров, и вместо трех требуется четыре инструкции. В любом случае, на практике это не может быть реализовано в отдельных процессорах, поскольку это нарушает условия Бернштейна для параллельных вычислений. Было бы нецелесообразно поддерживать процессоры достаточно синхронизированными друг с другом, чтобы эта замена имела какое-либо существенное преимущество перед традиционными версиями. Однако ее можно использовать для оптимизации замены для одного процессора с несколькими блоками загрузки/хранения.