스왑(컴퓨터 프로그래밍)
Swap (computer programming) |
컴퓨터 프로그래밍에서 두 변수를 교환하는 행위는 변수의 값을 서로 교환하는 것을 말합니다.통상, 이것은 메모리내의 데이터를 사용해 행해집니다.예를 들어 프로그램에서는 다음과 같이2개의 변수를 정의할 수 있습니다(의사코드).
data_item x := 1 data_item y := 0 스왑(x, y);
swap()이 실행된 후 x에는 값 0, y에는 값 1이 포함됩니다.이것들의 값은 교환되었습니다.이 작업은 문자열 및 집계된 데이터 유형과 같은 다른 유형의 값으로 일반화할 수 있습니다.비교 정렬에서는 스왑을 사용하여 데이터 위치를 변경합니다.
많은 프로그래밍 언어에는 스왑 기능이 내장되어 있습니다.C++에서는 과부하가 제공되므로 std::swap이 O(1) 시간 내에 몇 가지 큰 구조를 교환할 수 있습니다.
임시 변수 사용
두 변수를 스왑하는 가장 간단하고 널리 사용되는 방법은 세 번째 임시 변수를 사용하는 것입니다.
swap (x, y) temp : = x : = y : = temp 정의
이 방법은 개념적으로 단순하고 많은 경우 두 변수를 교환할 수 있는 유일한 편리한 방법이지만 추가 메모리를 사용합니다.대부분의 어플리케이션에서는 이것이 문제가 되지 않지만 스왑되는 값의 사이즈가 크거나(즉, 일시 변수도 메모리를 많이 사용하는 경우가 있습니다), 정렬 알고리즘과 같이 스왑 조작을 여러 번 실행해야 하는 경우가 있습니다.
또한 C++와 같은 객체 지향 언어에서 2개의 변수를 스왑하는 것은 클래스 컨스트럭터 및 디스트럭터에 대한 1개의 콜과 복사 컨스트럭터에 대한 3개의 콜을 포함할 수 있습니다.일부 클래스는 컨스트럭터에 메모리를 할당하고 디스트럭터에 메모리를 할당 해제하여 시스템에 고가의 콜을 생성할 수 있습니다.예를 들어 배열에 많은 데이터가 포함된 클래스의 복사 생성자는 데이터를 수동으로 복사해야 할 수도 있습니다.
XOR 스왑
XOR 스왑은 XOR 연산을 사용하여 두 숫자 변수를 스왑합니다.일반적으로 위의 순진한 방법보다 빠르다고 알려져 있지만 단점도 있습니다.XOR 스왑은 일반적으로 정수와 같은 낮은 수준의 데이터 유형을 스왑하는 데 사용됩니다.단, 이론적으로는 고정길이 비트스트링으로 나타낼 수 있는2개의 값을 교환할 수 있습니다.
덧셈과 뺄셈을 교환하다
이 방법에서는 값을 더하고 빼서 두 변수를 스왑합니다.이는 주로 다음과 같은 이유로 실제 적용에서는 거의 사용되지 않습니다.
- 숫자 변수만 스왑할 수 있습니다. 컨테이너와 같은 복잡한 데이터 유형을 추가하거나 빼는 것은 불가능하거나 논리적일 수 있습니다.
- 고정 크기의 변수를 스왑할 때 산술 오버플로가 문제가 됩니다.
- 부동소수점 산술은 비관련성이기 때문에 부동소수점 값에는 일반적으로 작동하지 않습니다.
컨테이너 교환
포인터를 사용하여 힙에서 메모리를 할당하는 컨테이너는 포인터만 스왑하여 한 번의 작업으로 스왑할 수 있습니다.이것은 보통 C나 C++와 같은 포인터를 지원하는 프로그래밍 언어에서 볼 수 있습니다.표준 템플릿 라이브러리는 이러한 [1]방식으로 컨테이너의 내용을 효율적으로 교환하기 위해 내장된 스왑 기능을 오버로드합니다.
포인터 변수는 일반적으로 고정 크기(예: 대부분의 데스크톱 컴퓨터에는 64비트 길이의 포인터가 있음)이며 숫자이므로 XOR 스왑을 사용하여 빠르게 스왑할 수 있습니다.
병렬 할당
Ruby 또는 Python과 같은 일부 언어는 병렬 할당을 지원하므로 두 변수 스왑을 위한 표기법이 단순해집니다.
a, b = b, a
이것은 중간 데이터 구조를 포함하는 작업의 줄임말입니다. Python에서는 튜플, Ruby에서는 어레이입니다.
Javascript 6+는 동일한 작업을 수행하는 운영자를 파괴하는 기능을 지원합니다.
[a, b] = [b, a];
함수 스왑
여기서는 2개의 글로벌 범위 변수가 함수를 통해 값별로 전달되므로 임시 스토리지 변수가 필요하지 않습니다.
x = 1, y = 2; console.log(x + " + y), // 출력 1 2 함수 스왑(a, b) { x = b; y = a; } 스왑(x, y), console.log(x + " + y), // 출력 2 1
최신 컴퓨터에서의 스와핑 촉진
전용 명령
컴퓨터에는 데이터 스와핑이 많이 적용되어 있기 때문에 대부분의 프로세서는 내장된 명령을 통해 직접 변수를 스와핑할 수 있습니다.예를 들어 x86 프로세서는 세 번째 임시 레지스터를 사용하지 않고 두 개의 레지스터를 직접 교환하는 XCHG 명령을 포함합니다.일부 프로세서 아키텍처에서는 2개의 레지스터를 비교 및 조건부로 스왑하는 비교 및 스왑 명령도 제공됩니다.이는 상호 제외 기술을 지원하기 위해 사용됩니다.
XCHG는 보기만큼 효율적이지 않을 수 있습니다.예를 들어 x86 프로세서에서 XCHG는 메모리 내의 오퍼랜드에 대한 접근을 암묵적으로 잠그고 동작이 원자성이라는 것을 보증하기 때문에 메모리를 스왑할 때는 효율적이지 않을 수 있습니다.이러한 잠금은 뮤텍스와 같이 스레드 세이프 동기화를 구현하기 위해 사용되는 경우 중요합니다.그러나 XCHG는 보통 레지스터에 있는 두 개의 기계 크기 워드를 교환하는 가장 빠른 방법입니다.레지스터 이름 변경은 레지스터를 효율적으로 스왑하기 위해 사용할 수도 있습니다.
병렬 실행
병렬 컴퓨팅을 용이하게 하는 최신 컴퓨터와 멀티코어 프로세서의 명령 파이프라이닝이 등장함에 따라 두 가지 이상의 작업을 동시에 수행할 수 있습니다.이를 통해 임시 변수를 사용하여 스왑 속도를 높이고 다른 알고리즘에 비해 우위를 확보할 수 있습니다.예를 들어 XOR 스왑 알고리즘에서는 세 가지 명령을 순차적으로 실행해야 합니다.그러나 2개의 임시 레지스터를 사용하여 병렬로 실행되는 2개의 프로세서가 2개의 클럭 사이클로 2개의 변수를 스왑할 수 있습니다.
스텝 1 프로세서1 : temp_1 : = X 프로세서2 : temp_2 : = Y 스텝2 프로세서1 : X : = temp _ 2 프로세서2 : Y : = temp _ 1
임시 레지스터가 더 많이 사용되며, 세 가지 명령이 아닌 네 가지 명령이 필요합니다.어느 경우든 병렬 컴퓨팅에 관한 Bernstein의 조건을 위반하기 때문에 실제로는 별도의 프로세서에 구현할 수 없었습니다.이 스왑이 기존 버전보다 훨씬 유리하도록 프로세서를 서로 충분히 동기화하는 것은 불가능합니다.다만, 복수의 로드/스토어 유닛이 있는 단일 프로세서의 스왑을 최적화하기 위해서 사용할 수 있습니다.
