Обмін (інформатика)
Перейти до навігації
Перейти до пошуку
О́бмін (англ. swap), в інформатиці — операція для обміну значень аргументів.
Наприклад, якщо маємо дві змінні A та B, і стан пам'яті: A=1, B=2, то після виконання операції swap(A,B) стан пам'яті змінюється на такий: A=2, B=1.
Реалізації[ред. | ред. код]
Очевидна реалізація використовує тимчасову змінну:
- TMP = A
- A = B
- B = TMP
Існують реалізації без використання додаткової змінної, наприклад Алгоритм обміну XOR, або за допомогою арифметики:
- A = A + B
- B = A - B
- A = A - B
В архітектурі x86 замість трьох інструкцій ассемблера MOV можна використовувати одну XCHG[1]. Існує також додаткова інструкція CMPXCHG, яка атомарно виконує дві дії (порівняти і обміняти) і використовується для реалізації мютексів.[2]
Застосування[ред. | ред. код]
- В алгоритмах сортування, наприклад сортування обміном.
- В алгоритмах генерації всіх чи випадкових перестановок[3]
Див. також[ред. | ред. код]
Зноски[ред. | ред. код]
- ↑ intel1, с. 7.3.1.2 Exchange Instructions.
- ↑ Rostedt, Steven (2006). RT-mutex implementation design — The Linux Kernel documentation. www.kernel.org. Процитовано 23 січня 2024.
- ↑ Skiena, 2008, с. 450.
Література[ред. | ред. код]
- The Intel Architecture Software Developer’s Manual, Volume 1: Basic Architecture (Order Number 243190) (PDF).
- Skiena, Steven S. (2008). The algorithm design manual (вид. 2nd). London: Springer. ISBN 978-1-84800-069-8.
|
Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її. |