Taking baby-developer steps
22.04.29. push_swap - 정렬 알고리즘 최적화-1 본문
236 line을 조금 수정해서, 초기상태에서 ㄹ구간만 a_stack에 남겼다.
그런데, 스택 출력을 통해, b스택의 바닥쪽 부분이 현재 ㄴ구간이 아니라는 것을 발견했고, 다시 239 line을 수정해, 다음과 같이 스택의 구간을 다시 나눴다.
a_stack에 모아둔 ㄹ구간을 기존의 정렬 함수로 정렬해 봤다.
a_stack 내 14개의 input을 정렬하는데 104개의 명령어가 소요되었다. 현재 정렬함수는, 정렬이 이미 된 부분을 b_stack에 잠시 보관했다가 다시 a_stack으로 가져오는 부분이 있는데, 이 부분에서 명령어의 소모가 심하다고 생각이 되었다.
현재 sort_a_stack() 함수가 정렬완료된 부분을 계속해서 b_stack에 옮겼다가 다시 계속 a_stack으로 가져오기 때문에 명령어의 낭비가 상당하다는 생각이 들었다. 그 다음 정렬할 자리로 넘어갈 때 정렬완료된 부분을 다시 a_stack으로 모두 옮기지 않고, 계속 b_stack에 가지고 있다가, a_stack이 모두 정렬이 완료되면 그때만 다시 a_stack에 위쪽 정렬완료된 부분을 가져와야겠다는 생각이 들었다.
기존에 이용하고 있던 k 인덱스를 활용해, sorted 된 부분(이전 반복문에서 찾아내서 정렬완료 된 부분)을 한번씩만 pb로 옮겨두고, 정렬을 위한 반복문이 모두 끝나고 나서 k 인덱스 값을 활용해, k 만큼 pb를 하게 하는 방법으로 코드를 개선 했고, 그 결과,
50개에서 1/4 정렬하는데에 168개의 명령어가 필요했던 기존 모습에서, 60개를 줄여 108개의 명령어로 실행되는 모습을 볼 수 있었다. 이제 앞서 구상한 것에 의하면 ㄷ구간을 a_stack으로 옮기면서 섞여있던 ㄱ구간의 값은 rb로 b_stack의 바닥 부분으로 두는 부분을 구현할 차례이다.
그런데, a_stack에서 ㄹ구간의 정렬된 상태를 a_stack에 둔 채로 ㄷ구간만 정렬하는 것이 가능한지에 대한 의구심이 들었다.
그리고 이를 해결하려하자 두가지 생각이 떠올랐다.
1. 어차피 ra,rra 연산만으로는 ㄹ구간의 순서를 바꾸지 못한다. 따라서 ㄹ구간을 정렬했던 것과 같은 로직으로 정렬해도 문제 없다.
2. ㄷ구간은 ㄹ구간과는 다르게 정렬해야한다.
2번 생각에 대한 설명을 좀 더 붙인다.
기존에는 b_stack의 바닥에 ㄴ구간을 몰아 두고, ㄷ, ㄱ 구간이 합쳐진 부분에서 ㄷ구간은 a스택으로 넘겨서 정렬하고, ㄱ구간을 모두 b_stack의 바닥으로 넘겨버릴 생각이었다, 그런데 현재 정렬 방법에 의하면, 찾는 수가 탑이나 바닥 중 어느 한부분에 몰려 있는 것 보다는, 탑과 바닥으로 두개 구간으로 나누어져 있을 때 오히려 최소의 명령어를 써서 정렬 할 수 있는 편이라고 생각한다. 따라서 오히려 처음에 b_stack의 바닥으로 넘기는 구간을 ㄴ구간이 아닌, ㄱ구간으로 하고, ㄷ구간을 a_stack으로 옮기고 정렬하는 것이 아닌, b_stack에서 그냥 최대값을 찾아서 a_stack으로 넘기는 식으로 정렬 하는 것이 더 효율적 일 수 있겠다는 생각이 들었다. (이번 과제에서 명령어를 낭비하게 되는 경우는 정렬할 차례가 아닌 값을 ra나 rra 로 top에서 밀어 내는 경우이기 때문)
두가지 생각을 모두 고려해서 일단 초기상태에서 pb할 때, ㄱ구간이 b스택의 바닥에 가깝게 위치하게 하고, ㄹ을 a스택에서 정렬하는 것이 끝나면, ㄷ과 ㄱ을 구분해가면서 분리한 후 a_stack에서 ㄷ을 정렬해 보는 방법을 먼저 시도해 보려고 한다.
기존에 만들어 뒀던 a스택 ㄹ구간 정렬 함수를 조금 고쳤는데, a스택에 ㄷ구간을 옮긴후 또 정렬하는 것보다, ㄷ 구간에서 최댓값을 찾아 a_stack으로 넘기고, 도중에 만나게 되는 ㄴ구간 값들은 rb및 rrb 처리 하는 식으로 코드를 작성했다.
이제 b스택에 남아있는 모든 수를 내림차순으로 a스택에 보내기만 하면 된다.
위의 모습 처럼 51개의 인풋을 정렬 완료 시키는 데 사용한 명령어의 수는 193개인 것이 확인 되었다.
총 658개의 명령어가 감소 되었고, 이는 명령어 갯수가 77% 감소 된 것이다.
어제와 동일한 102개의 input을 정렬한 결과는 다음과 같다.
1566개의 명령어가 감소 되었고, 이는 약 73%의 감소 효과를 가진다.
다만, 작은 볼륨의 인풋값들을 넣었을때, 현재 알고리즘이 작동하지 않거나 최적화가 되어있지 않음으로, 5~6개 이하인 input이 들어왔을 경우를 따로 처리해야 하는 필요성이 있다.
int MIN~MAX 값 사이의 난수 발생기를 활용해 만든 인풋 500개에 대한 결과는 다음과 같았다.
목표는 500개 이하의 input이 들어올 경우, 5500개 미만의 명령어로 정렬 하는 것이므로, 조금 더 최적화가 필요하다는 판단이 들었다.
먼저, 몇개 이상의 input에서 부터 최적화가 필요할지(현재의 로직이 가지는 이점을 가질 수 없어지는 지) 확인 하기 위해, 난수 생성기를 활용해서 input을 넣어봤다.
현재 최선의 목표는 500개 이하 input에서 명령어 5500개 이하이므로, 인풋 260개 이상에서 부터 한번 더 최적화를 진행하기로 결정했다.
260개 이상 부터는 각 구간이 60개 이상을 넘어가기 때문에 구간을 나눴을 때 가질 수 있었던 이점들이 없어진다는 판단이 들었다.
각 구간을 최대 60개의 구간으로 잡고 정렬을 하게 되면, 500개 이하 input이 들어올 경우, sort_big 함수에서 나눌 구간은 5개~9개구간이 된다.
결국 첫 sort_big 함수의 구상은 다음과 같이 했다.
위와 같은 구상으로 sort_big 함수를 구상해서 275개의 input으로 정렬을 실행해 본 결과는 다음과 같았다.
sort_big함수를 만들기 이전, 5816개 명령어에서 4903개로 줄은 것은 꽤 큰 변화이기는 하나, 500개 인풋을 넣었을 때 의미있는 변화를 기대하기는 조금 어려울 것 같다.
위의 test에서 썼던 500개 인풋을 저장해 두지 않아서, 난수 생성기로 새로운 500개 인풋을 만들어 돌린 결과는 다음과 같다.
동일한 input 값이 아니라 효율이 떨어졌다고 말하기는 힘들지만, 확실한 것은 500개 인풋에 대해서는 최적화가 더 필요하다.
몇개의 구간(5~9개 구간)부터 5500개를 만족하지 못하는 지를 확인 해보려고 한다.
각 구간에 해당하는 input의 갯수를 한번 바꿔보았다.
내 생각에, 각 구간의 크기가 너무 커져서도 안되지만, 구간이 너무 많아져서도 필요없는 비용이 늘어나는 것 같다.
input 값에 따라 각 구간의 크기를 다르게 설정해서 최적화를 노려 볼 수 있을 것 같고, 현재 sort_big은 5개 구간으로 나뉘어 졌을때 정도가 가장 효율적(명령어를 최소화)으로 작동하는 것으로 보여진다. 이를 고려해서 sort_big 함수를 최적화 해봐야겠다.
'Logs > 학습 log' 카테고리의 다른 글
| 22.05.03.push_swap - 정렬 알고리즘 최적화-3 (0) | 2022.05.03 |
|---|---|
| 22.04.30. push_swap - 정렬 알고리즘 최적화-2 (0) | 2022.04.30 |
| 22.04.28. push_swap - 정렬 알고리즘 최적화 (0) | 2022.04.28 |
| 22.04.26. push_swap - 정렬부 구현-5, a_stack 오름차순 정렬하기-3=> 정렬 알고리즘 검토, b_stack 내림차순 정렬하기 (0) | 2022.04.26 |
| 2022.04.19. push_swap - 정렬부 구현-4, a_stack 오름차순 정렬하기-2 => 정렬 알고리즘 검토 (0) | 2022.04.19 |
