일반적인 합병정렬(:12)을 이용하면 문제를 해결할 수 있을 것이다. 하지만 중간값을 찾는다고 한다면, 완전한 합병정렬을 할 필요가 없을 것이다. 그렇다면 어딘가에 성능을 개선할 여지가 있을 것이다.
일반적인 합병정렬
전형적인 합병정렬이다. 이미 만들어진 코드를 참고하기 바란다. 일반적이지만 성능개선은 기대할 수 없다.
성능 개선
중간값이 필요하다면, 굳이 완전한 합병정렬의 필요가 없을 것이다. 일부분에 대한 합병정렬만으로도 원하는 값을 찾아낼 수 있다.
+---------------------------------------+
| Array A |
+---------------------------------------+
+---------+ | +--+
| | | | | Array B
+---------+ | +--+
|
<---| 이동
다음과 같은 방법을 이용할 수 있을 것이다.
Array A의 중간값을 찾는다.
Array A와 Array B를 비교한다. 그러면 새로 추가될 원소의 갯수를 파악할 수 있을 것이다.
Array A의 중간값을 기준으로 좌 우 각각 어느쪽에 몇개의 원소가 추가되었는지 확인할 수 있을 것이다.
만약 좌에 5개 우에 1개의 원소가 추가되었다면, Array A의 중간값의 위치를 왼쪽으로 2만큼 이동시키면 된다.
이때 이동은 Array A와 Array B 모두를 고려해야 하므로 합병정렬에서의 비교연산이 들어가게 될 것이다.
아이디어 자체는 문제가 없을 거라 생각된다.
예외사항
이 예외 사항은 Array A와 Array B의 원소가 중복되지 않을 경우에 해당된다.
배열과 배열의 범위가 겹치지 않을 때
+----------++---------------------+
| Array B || Array A |
+----------++---------------------+
전체배열의 크기 / 2 만큼해서 이동시키면 되겠다.
Array B의 max를 기준으로 하면 앞뒤로 얼마만큼 이동해야 할지 결정할 수 있다.
예) Size B = 10, Size A = 20 이라면, A에서 5만큼 이동
윗 절의 성능개선방식을 적용해도 문제를 풀 수 있다.
새로 추가되는 원소가 10 이므로 index를 기준으로 해서 앞으로 5 (10/5)만큼 이동시키면 된다. 결국 A[5]를 읽어들이게 될 것이다.
C++/C 코드
아직 완성된 코드는 아니다. 아마 제대로 돌아가지 않을 것이지만 대략 방법은 알 수 있을 것 같다. 어떻게 구현될 수 있는지만 신경썼다. 깔끔하게 만드는건 내일쯤 해볼 생각이다.
#include <stdio.h>
#include <vector>
using namespace std;
int find_middle(int *a, int size_a, int *b, int size_b);
void show_array(int *a, int size_a, int *b, int size_b);
int lsearch(int *sp, int size_sp, int search_n);
int main(int argc, char **argv)
{
int a[] = {5, 8, 10, 14, 19, 20, 25, 30, 33, 35, 39};
int b[] = {5, 8, 25};
show_array(a, sizeof(a)/4, b, sizeof(b)/4);
find_middle(a, sizeof(a)/4, b, sizeof(b)/4);
return 0;
}
int find_middle(int *a, int size_a, int *b, int size_b)
{
int *largep;
int *smallp;
int smallsize;
int largesize;
int idx;
if (size_a > size_b)
{
largep = a;
smallp = b;
idx = size_a/2;
smallsize = size_b;
largesize = size_a;
}
else
{
largep = b;
smallp = a;
smallsize = size_a;
largesize = size_b;
idx = size_b/2;
}
// large array의 중간값보다 작은 값의 범위에 대해서
int li = 0;
int si = 0;
int left_size=0;
int leftsame=0;
int same=0;
printf("pivot : %d %d\n", idx, largep[idx]);
printf("Large %d , Small %d\n", largesize, smallsize);
while(1)
{
if (li == largesize-1 && si == smallsize-1) break;
printf("%d %d\n", largep[li], smallp[si]);
if (largep[li] == smallp[si])
{
same++;
if (li < idx) leftsame++;
if (li < largesize-1)
li++;
if (si < smallsize-1)
si++;
}
else if(largep[li] > smallp[si])
{
if (si < smallsize-1)
si++;
else
li++;
}
else
{
if (li < largesize-1)
li++;
}
sleep(1);
}
printf("Small Insert Size %d %d\n", leftsame, same);
// large array의 중간값보다 큰것들 비교
int right_size = 0;
same = 0;
int small_center = si;
printf("small Center : %d\n", si);
printf("Center %d\n", largep[li]);
right_size -= same;
printf("Large insert %d\n", right_size);
int offset = (right_size - left_size)/2;
// 대략 idx를 기준으로 앞으로 2만큼 이동시킨게 중간값임을 알 수 있다.
// 이제 실제 idx를 이동시키면서 원하는 값을 찾아보자.
printf("Offset is %d\n", offset);
int big_center = size_a/2;
int value;
if (offset > 0)
{
while(offset)
{
if (largep[big_center] > smallp[small_center])
{
big_center --;
offset --;
value = largep[big_center];
}
else if (largep[big_center] < smallp[small_center])
{
small_center --;
offset --;
value = smallp[small_center];
}
else
{
small_center --;
big_center --;
value = smallp[small_center];
}
}
printf("[1] middle Value : %d \n", value);
}
else
{
value = largep[big_center];
while(offset)
{
if (largep[big_center] < smallp[small_center])
{
big_center ++;
offset ++;
value = largep[big_center];
}
else if (largep[big_center] > smallp[small_center])
{
small_center ++;
offset ++;
value = smallp[small_center];
}
else
{
small_center ++;
big_center ++;
value = smallp[small_center];
}
}
printf("[2] middle Value : %d\n", value);
}
return 0;
}
// 경우에 따라서 binary 검색으로 할 수 있다.
int lsearch(int *sp, int size_sp, int search_n)
{
int i = 0;
while(i < size_sp)
{
if ( *(sp+i) > search_n)
return i;
i++;
}
return 0;
}
void show_array(int *a, int size_a, int *b, int size_b)
{
int i = 0;
printf("[ ");
for(i = 0; i < size_a; i++)
{
printf("%d ",a[i]);
}
printf("]\n");
printf("[ ");
for(i = 0; i < size_b; i++)
{
printf("%d ",b[i]);
}
printf("]\n");
}
해야할일
위의 개선사항을 코드화해서 테스트해본다.
잘 돌아가는 가 ?
잘 돌아가지 않는다면, 문제점을 찾아본다. 혹은 방식자체가 잘못되었을 수도 있다.
잘 돌아간다면, 왜 잘 돌아가는지 (직관이 아닌)증명할 수 있는가 ?
그렇다면 위치를 인자로 받아서, 해당 위치의 값을 얻어올 수 있도록 코드를 수정할 수 있을까 ?
문제
문제에 의견
일반적인 합병정렬
성능 개선
예외사항
배열과 배열의 범위가 겹치지 않을 때
C++/C 코드
해야할일
Recent Posts
Archive Posts
Tags