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