Войти
В компьютерном программировании под заменой двух переменных подразумевается взаимный обмен значениями переменных. Обычно это делается с данными в памяти. Например, в программе две переменные могут быть определены таким образом (в псевдокоде ):
data_item x := 1 data_item y := 0 swap (x, y);
После выполнения swap () x будет содержать значение 0, а y будет содержать 1; их ценности были обменены. Эта операция может быть обобщена для других типов значений, таких как строки и агрегированные типы данных. Сортировки сравнения используют свопы для изменения положения данных.
Во многих языках программирования функция подкачки встроена. В C ++, перегруженные которые при условии, что позволяет станд:: подкачки для обмена некоторых больших структур в O (1) времени.
Самый простой и, вероятно, наиболее широко используемый метод замены двух переменных - это использовать третью временную переменную :
define swap (x, y) temp := x x := y y := temp
Хотя это концептуально простой и во многих случаях единственный удобный способ поменять местами две переменные, он требует дополнительной памяти. Хотя это не должно быть проблемой для большинства приложений, размеры заменяемых значений могут быть огромными (что означает, что временная переменная также может занимать много памяти), или операция подкачки может потребоваться выполнить много раз, так как в алгоритмах сортировки.
Кроме того, замена двух переменных в объектно-ориентированных языках, таких как C ++, может включать один вызов конструктора класса и деструктора для временной переменной и три вызова конструктора копирования. Некоторые классы могут выделять память в конструкторе и освобождать ее в деструкторе, тем самым создавая дорогостоящие вызовы системы. Конструкторам копирования для классов, содержащих много данных, например в массиве, может даже потребоваться копирование данных вручную.
Обмен XOR использует операцию XOR, чтобы поменять местами две числовые переменные. Обычно он рекламируется как более быстрый, чем упомянутый выше наивный метод; однако у него есть недостатки. Замена XOR обычно используется для обмена низкоуровневыми типами данных, такими как целые числа. Однако теоретически он может менять местами любые два значения, которые могут быть представлены строками битов фиксированной длины.
Этот метод меняет местами две переменные, складывая и вычитая их значения. Это редко используется в практических приложениях, в основном потому, что:
Контейнеры, которые выделяют память из кучи с помощью указателей, можно поменять местами за одну операцию, поменяв местами только указатели. Обычно это встречается в языках программирования, поддерживающих указатели, таких как C или C ++. Standard Template Library перегружает его встроенная функцию подкачки для эффективного обмена содержимого контейнеров таким образом.
Поскольку переменные-указатели обычно имеют фиксированный размер (например, большинство настольных компьютеров имеют указатели длиной 64 бита ) и являются числовыми, их можно быстро поменять местами с помощью замены XOR.
Некоторые языки, такие как Ruby или Python, поддерживают параллельные присваивания, что упрощает нотацию для обмена двумя переменными:
a, b = b, a
Это сокращение для операции с промежуточной структурой данных: в Python - кортеж; в Ruby - массив.
Javascript 6+ поддерживает операторы деструктуризации, которые делают то же самое:
[a, b] = [b, a];
Здесь две глобальные переменные передаются по значению через функцию, что устраняет необходимость во временной переменной хранения.
x = 1; y = 2; console.log(x + " " + y); // outputs 1 2 function swap(a, b) { x = b; y = a; } swap(x, y); console.log(x + " " + y); // outputs 2 1 Из-за множества приложений обмена данными в компьютерах большинство процессоров теперь предоставляют возможность обмена переменными напрямую с помощью встроенных инструкций. Процессоры x86, например, включают инструкцию XCHG для прямого обмена двумя регистрами, не требуя использования третьего временного регистра. В некоторых архитектурах процессоров даже предусмотрена инструкция сравнения и замены, которая сравнивает и меняет местами два регистра по условию. Это используется для поддержки методов взаимного исключения.
XCHG может быть не таким эффективным, как кажется. Например, в процессорах x86 XCHG неявно блокирует доступ к любым операндам в памяти, чтобы гарантировать, что операция является атомарной, и поэтому может быть неэффективным при подкачке памяти. Такая блокировка важна, когда она используется для реализации потоковой синхронизации, например, в мьютексах. Однако XCHG обычно является самым быстрым способом поменять местами два машинных слова, находящихся в регистрах. Переименование регистров также может использоваться для эффективной замены регистров.
С появлением конвейерной обработки команд в современных компьютерах и многоядерных процессорах, облегчающих параллельные вычисления, две или более операции могут выполняться одновременно. Это может ускорить обмен с использованием временных переменных и дать ему преимущество перед другими алгоритмами. Например, алгоритм обмена XOR требует последовательного выполнения трех инструкций. Однако, используя два временных регистра, два процессора, выполняющиеся параллельно, могут поменять местами две переменные за два такта:
Step 1 Processor 1: temp_1 := X Processor 2: temp_2 := Y Step 2 Processor 1: X := temp_2 Processor 2: Y := temp_1
Это требует меньше инструкций; но могут использоваться и другие временные регистры, и вместо трех требуются четыре инструкции. В любом случае на практике это не могло быть реализовано в отдельных процессорах, так как это нарушает условия Бернштейна для параллельных вычислений. Было бы невозможно поддерживать процессоры в достаточной степени синхронизированными друг с другом, чтобы этот обмен имел какое-либо существенное преимущество перед традиционными версиями. Однако его можно использовать для оптимизации подкачки для одного процессора с несколькими модулями загрузки / хранения.
