반전 알고리즘

문제 : n개의 원소를 가지는 벡터 x를 i만큼 왼쪽으로 회전시키기
        즉, ab => ba

예제> n = 8, i = 3 인 경우에 a = 1 2 3, b = 4 5 6 7 8 가 된다.
 
입력 : 1 2 3   4 5 6 7 8
출력 : 4 5 6 7 8   1 2 3 

======================================< 풀     이 >==========================================

private static final int N = 1000000; -> 샘플 길이

private static final int SHIFT = 1000; -> 왼쪽으로 shift 하는 횟수

reverse 알고리즘
- swap 횟수 : N번
- 수행시간 : 약 10밀리세컨드

int[] result = getSample(N);

reverse(0, SHIFT-1, result);

reverse(SHIFT, N-1, result);

reverse(0, N-1, result);

배열을 거꾸로 뒤집는다.

private void reverse(int i, int j, int[] input){

while(i < j) {

int temp = input[j];

input[j] = input[i];

input[i] = temp;

i++;

j--;

}

} 

juggling action 알고리즘 

- swap 횟수 : N번
- 수행 시간 : 약 50 밀리세컨드

int[] result = getSample(N);

for(int i = 0; i < getGCD(N, SHIFT); ++i) {

int t = result[i];

int k = getGCD(N,SHIFT) + i;

for(int j = i; j < result.length; j += getGCD(N, SHIFT)){

if(k < result.length){

result[j] = result[k];

k += getGCD(N, SHIFT);

}else{

result[j] = t;

}

}

}

최대공약수(Greatest Common Divisor)를 찾는다.

private static int getGCD(int a, int b){

while(0 != b){

int temp = a % b;

a = b;

b = temp;

}

return Math.abs(a);

}

shift 알고리즘
- swap 횟수 : (N-1)*SHIFT
- 수행 시간 : 약 3500밀리세컨드

int[] result = getSample(N);

for(int i = 0; i < SHIFT; ++i){

for(int j = 1; j < result.length; ++j){

int t = result[j];

result[j] = result[j-1];

result[j-1] = t;

}

} 

INPUT을 생성한다.

private int[] getSample(int length) {

int[] result = new int[length];

for (int i = 0; i < result.length; i++) {

result[i] = i;

}

return result;

}

실험>

조건 1> N = 1000000(백만), SHIFT = 1000
 - reverse : 10ms
 - juggling action : 52ms
 - shift : 3640ms

조건 2> N = 1000000(백만), SHIFT = 10
 - reverse : 10ms
 - juggling action : 47ms
 - shift : 43ms

조건 3> N = 1000000(백만), SHIFT = 5
 - reverse : 10ms
 - juggling action : 45ms
 - shift : 24ms

조건 4> N = 1000000(백만), SHIFT = 1
 - reverse : 10ms
 - juggling action : 45ms
 - shift : 10ms

 
결과>

reverse 알고리즘은 꾸준한 성능을 보여준다. 
jugging action 알고리즘은 꾸준한 성능을 보여주지만 조건에 따라 shift알고리즘보다 성능이 낮기도 한다.
세가지 알고리즘 모두 제한된 메모리를 갖고 있다는 전제조건에서 구상했다.

만일, i만큼의 벡터를 임시변수에 옮긴 후, n-i개의 원소를 i만큼 왼쪽으로 옮긴다음에 x의 뒤쪽에 임시변수를 
복사해야 한다면 i만큼의 메모리를 필요로 하게 된다. 

 
reverse알고리즘 동작 원리>

a` = a의 reverse, b` = b의 reverse

(ab)` = b`a`  <= 이 법칙은 중고등학교 수학시간에 배웠다.

a b => a` b` => (a` b`)` = ba

 

참고자료 : 생각하는 프로그래밍 칼럼2