티스토리 뷰
들어가며
알고리듬을 공부했다면, swap 함수를 작성해본적이 있을 것이다. 정렬 알고리듬 또한 공부했을 것이다.
하지만, 공부했던 자료를 되돌아 보자.
int 타입 숫자들만 정렬해보지 않았는가?
실제 상황에서는 다양한 타입에 대해 대응해야 할 것이다!
타입에 얽매이지 않는 프로그래밍을 Generic 프로그래밍이라 한다. Generic 프로그래밍은 코드의 재사용성을 높이고, 다양한 데이터 타입을 지원하며, 타입 안정성을 유지할 수 있게 한다. 이를 통해 우리는 하나의 함수나 클래스로 다양한 데이터 타입을 처리할 수 있다.
본 글에서는 특정 타입에 대한 swap 함수부터 시작하여, Generic Swap 함수를 구현하고, Generic Sort 함수까지의 구현하는 여정을 담았다. 같이 따라가보며, 구현하기 위해서 어떤 아이디어가 필요할지 생각해보자!
Course
인프런 강의 - 오픈소스 자료구조 및 알고리즘 in C (https://inf.run/9yRvN) 중 섹션 7. Generic Sort 를 따라가며 작성했다.
사전지식
- C
- 포인터를 알아야 한다.
- 포인터 연산
- 포인터 캐스팅
- 함수 포인터
- 포인터를 알아야 한다.
능숙하진 않아도 개념만이라도 알고 있다면, 따라가기 어렵지 않을 것이다
개발환경
- Apple M1 pro
- macOS, Sonoma 14.3
- clang, version 16.0.6
- 기본적 문법의 단순한 컴파일만 하므로, 버전 의존적이지는 않다
Part1. Generic Swap
하드코딩 swap
swap1.c
#include <stdio.h>
int main()
{
int a = 3, b = 4;
int t;
t = a;
a = b;
b = t;
printf("a=%d, b=%d\n", a, b);
return 0;
}clang swap1.c
./a.out
a=4, b=3cf) 이후 내용에서 특별한 사항이 존재하지 않는다면, 출력문만 기입해 두겠다.
원하는 동작을 한 모습이다.
함수화
값으로 전달 (의도하지 않는 구현)
swap2.c
#include <stdio.h>
void swap(int a, int b)
{
int t;
t = a;
a = b;
b = t;
printf("swap : a=%d, b=%d\n", a, b);
}
int main()
{
int a = 3, b = 4;
swap(a, b);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}swap : a=4, b=3
main : a=3, b=4함수 스택으로 복사된 값만 변경하므로, 의도한 구현이 아니다.
주소로 전달 (의도한 구현)
swap3.c
#include <stdio.h>
void swap(int* a, int* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
int main()
{
int a = 3, b = 4;
swap(&a, &b);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}main : a=4, b=3call by address를 통해, 의도한 동작을 구현했다.
🤔 이제 생각해 보자. 현재 함수는 integer 형을 swap 할 수 있다.
하지만, double 형 또한 swap 하고 싶다면 어떻게 해야 할까?
#define을 이용한 꼼수
swap4.c
#include <stdio.h>
#define TYPE int
void swap(TYPE* a, TYPE* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
int main()
{
int a = 3, b = 4;
swap(&a, &b);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}main : a=4, b=3이때 TYPE을 double로 수정하고, 클라이언트 코드에서 double을 넣는 것이다.
swap5.c
#include <stdio.h>
#define TYPE double
void swap(TYPE* a, TYPE* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
int main()
{
double ad = 3., bd = 4.;
swap(&ad, &bd);
printf("main : ad=%lf, bd=%lf\n", ad, bd);
return 0;
}main : ad=4.000000, bd=3.000000괜찮아 보인다.
하지만, 결국 하나의 타입만 가능하다는 한계가 있다.
swap6.c
#include <stdio.h>
#define TYPE int
void swap(TYPE* a, TYPE* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
int main()
{
double ad = 3., bd = 4.;
int a = 3, b = 4;
swap(&ad, &bd);
swap(&a, &b);
printf("main : ad=%lf, bd=%lf\n", ad, bd);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}integer로 define 하면, double 쪽이 제대로 동작하지 않는다.
clang swap6.c
swap6.c:19:10: warning: incompatible pointer types passing 'double *' to parameter of type 'int *' [-Wincompatible-pointer-types]
swap(&ad, &bd);
^~~
swap6.c:5:17: note: passing argument to parameter 'a' here
void swap(TYPE* a, TYPE* b)
^
swap6.c:19:15: warning: incompatible pointer types passing 'double *' to parameter of type 'int *' [-Wincompatible-pointer-types]
swap(&ad, &bd);
^~~
swap6.c:5:26: note: passing argument to parameter 'b' here
void swap(TYPE* a, TYPE* b)
^
2 warnings generated.
./a.out
main : ad=3.000000, bd=4.000000
main : a=4, b=3반대의 상황 또한 마찬가지이다.
꼼수로 해결 가능 할 것 같았으나 불가능하고, 결국 각각의 버전을 짜야한다.
타입마다 함수 만들기 (feat. 함수 오버로딩)
C에서는 함수 오버로딩을 지원하지 않음
C에서는 함수 오버로딩을 지원하지 않는다. 따라서 아래와 같이 작성하면 C 컴파일러는 경고와 에러를 출력하며 컴파일조차 되지 않는다.
swap7.c
#include <stdio.h>
void swap(int* a, int* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
void swap(double* a, double* b)
{
double t;
t = *a;
*a = *b;
*b = t;
}
int main()
{
double ad = 3., bd = 4.;
int a = 3, b = 4;
swap(&a, &b);
swap(&ad, &bd);
printf("main : ad=%lf, bd=%lf\n", ad, bd);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}clang swap7.c
swap7.c:12:6: error: conflicting types for 'swap'
void swap(double* a, double* b)
^
swap7.c:3:6: note: previous definition is here
void swap(int* a, int* b)
^
swap7.c:27:10: warning: incompatible pointer types passing 'double *' to parameter of type 'int *' [-Wincompatible-pointer-types]
swap(&ad, &bd);
^~~
swap7.c:3:16: note: passing argument to parameter 'a' here
void swap(int* a, int* b)
^
swap7.c:27:15: warning: incompatible pointer types passing 'double *' to parameter of type 'int *' [-Wincompatible-pointer-types]
swap(&ad, &bd);
^~~
swap7.c:3:24: note: passing argument to parameter 'b' here
void swap(int* a, int* b)
^
2 warnings and 1 error generated.cf) C++에서는 함수 오버로딩을 지원한다.
C++ 컴파일러로 컴파일 후 objdump 해보면, 각 버전별로 함수명을 다르게 갖고 있음을 확인할 수 있다.
clang++ swap7.c
objdump -S a.out
a.out: file format mach-o arm64
Disassembly of section __TEXT,__text:
0000000100003e38 <__Z4swapPiS_>:
100003e38: d10083ff sub sp, sp, #32
100003e3c: f9000fe0 str x0, [sp, #24]
100003e40: f9000be1 str x1, [sp, #16]
100003e44: f9400fe8 ldr x8, [sp, #24]
100003e48: b9400108 ldr w8, [x8]
100003e4c: b9000fe8 str w8, [sp, #12]
100003e50: f9400be8 ldr x8, [sp, #16]
100003e54: b9400108 ldr w8, [x8]
100003e58: f9400fe9 ldr x9, [sp, #24]
100003e5c: b9000128 str w8, [x9]
100003e60: b9400fe8 ldr w8, [sp, #12]
100003e64: f9400be9 ldr x9, [sp, #16]
100003e68: b9000128 str w8, [x9]
100003e6c: 910083ff add sp, sp, #32
100003e70: d65f03c0 ret
0000000100003e74 <__Z4swapPdS_>:
100003e74: d10083ff sub sp, sp, #32
100003e78: f9000fe0 str x0, [sp, #24]
100003e7c: f9000be1 str x1, [sp, #16]
100003e80: f9400fe8 ldr x8, [sp, #24]
100003e84: f9400108 ldr x8, [x8]
100003e88: f90007e8 str x8, [sp, #8]
100003e8c: f9400be8 ldr x8, [sp, #16]
100003e90: f9400108 ldr x8, [x8]
100003e94: f9400fe9 ldr x9, [sp, #24]
100003e98: f9000128 str x8, [x9]
100003e9c: f94007e8 ldr x8, [sp, #8]
100003ea0: f9400be9 ldr x9, [sp, #16]
100003ea4: f9000128 str x8, [x9]
100003ea8: 910083ff add sp, sp, #32
100003eac: d65f03c0 ret
0000000100003eb0 <_main>:
100003eb0: d10183ff sub sp, sp, #96
100003eb4: a9057bfd stp x29, x30, [sp, #80]
100003eb8: 910143fd add x29, sp, #80
100003ebc: 52800008 mov w8, #0
100003ec0: b81dc3a8 stur w8, [x29, #-36]
100003ec4: b81fc3bf stur wzr, [x29, #-4]
100003ec8: d10043a8 sub x8, x29, #16
100003ecc: f9000fe8 str x8, [sp, #24]
100003ed0: 1e611000 fmov d0, #3.00000000
100003ed4: fc1f03a0 stur d0, [x29, #-16]
100003ed8: d10063a8 sub x8, x29, #24
100003edc: f90013e8 str x8, [sp, #32]
100003ee0: 1e621000 fmov d0, #4.00000000
100003ee4: fc1e83a0 stur d0, [x29, #-24]
100003ee8: d10073a0 sub x0, x29, #28
100003eec: 52800068 mov w8, #3
100003ef0: b81e43a8 stur w8, [x29, #-28]
100003ef4: d10083a1 sub x1, x29, #32
100003ef8: 52800088 mov w8, #4
100003efc: b81e03a8 stur w8, [x29, #-32]
100003f00: 97ffffce bl 0x100003e38 <__Z4swapPiS_>
100003f04: f9400fe0 ldr x0, [sp, #24]
100003f08: f94013e1 ldr x1, [sp, #32]
100003f0c: 97ffffda bl 0x100003e74 <__Z4swapPdS_>
100003f10: f85f03aa ldur x10, [x29, #-16]
100003f14: f85e83a8 ldur x8, [x29, #-24]
100003f18: 910003e9 mov x9, sp
100003f1c: f900012a str x10, [x9]
100003f20: f9000528 str x8, [x9, #8]
100003f24: 90000000 adrp x0, 0x100003000 <_main+0x74>
100003f28: 913dd000 add x0, x0, #3956
100003f2c: 9400000f bl 0x100003f68 <_printf+0x100003f68>
100003f30: b85e43a8 ldur w8, [x29, #-28]
100003f34: aa0803ea mov x10, x8
100003f38: b85e03a9 ldur w9, [x29, #-32]
100003f3c: aa0903e8 mov x8, x9
100003f40: 910003e9 mov x9, sp
100003f44: f900012a str x10, [x9]
100003f48: f9000528 str x8, [x9, #8]
100003f4c: 90000000 adrp x0, 0x100003000 <_main+0x9c>
100003f50: 913e2c00 add x0, x0, #3979
100003f54: 94000005 bl 0x100003f68 <_printf+0x100003f68>
100003f58: b85dc3a0 ldur w0, [x29, #-36]
100003f5c: a9457bfd ldp x29, x30, [sp, #80]
100003f60: 910183ff add sp, sp, #96
100003f64: d65f03c0 ret
Disassembly of section __TEXT,__stubs:
0000000100003f68 <__stubs>:
100003f68: b0000010 adrp x16, 0x100004000 <__stubs+0x4>
100003f6c: f9400210 ldr x16, [x16]
100003f70: d61f0200 br x16C++ 컴파일러가 함수 오버로딩된 두 버전을 각각 _Z4 swapPiS와 _Z4 swapPdS으로 컴파일한 것을 확인할 수 있다.
C에서는 함수 오버로딩을 지원하지 않으므로, 함수명을 다르게 작성해줘야 한다.
#include <stdio.h>
void swap_int(int* a, int* b)
{
int t;
t = *a;
*a = *b;
*b = t;
}
void swap_double(double* a, double* b)
{
double t;
t = *a;
*a = *b;
*b = t;
}
int main()
{
double ad = 3., bd = 4.;
int a = 3, b = 4;
swap_int(&a, &b);
swap_double(&ad, &bd);
printf("main : ad=%lf, bd=%lf\n", ad, bd);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}main : ad=4.000000, bd=3.000000
main : a=4, b=3하지만, 지원해야 할 타입이 2개뿐일까?
원시타입만 해도 여러 개이고, 사용자 정의 타입(구조체)이 있다면 모두 만들어야 할 것이다.
그렇다면 C에서 어떻게 처리해야 할까?
🚀 void * (void 포인터)
void 포인터의 필요성에 대한 설명이 먼저 필요하다.
1byte를 쓰기 위해 char타입을 사용하여 swap 해보자.
swap9.c
#include <stdio.h>
void swap(char* a, char* b) // 1byte를 쓰기 위해 char타입 사용
{
char t;
t = *a;
*a = *b;
*b = t;
}
int main()
{
double ad = 3., bd = 4.;
int a = 3, b = 4;
swap(&a, &b);
swap(&ad, &bd);
printf("main : ad=%lf, bd=%lf\n", ad, bd);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}clang swap9.c
swap9.c:17:10: warning: incompatible pointer types passing 'int *' to parameter of type 'char *' [-Wincompatible-pointer-types]
swap(&a, &b);
^~
swap9.c:3:17: note: passing argument to parameter 'a' here
void swap(char* a, char* b)
^
swap9.c:17:14: warning: incompatible pointer types passing 'int *' to parameter of type 'char *' [-Wincompatible-pointer-types]
swap(&a, &b);
^~
swap9.c:3:26: note: passing argument to parameter 'b' here
void swap(char* a, char* b)
^
swap9.c:18:10: warning: incompatible pointer types passing 'double *' to parameter of type 'char *' [-Wincompatible-pointer-types]
swap(&ad, &bd);
^~~
swap9.c:3:17: note: passing argument to parameter 'a' here
void swap(char* a, char* b)
^
swap9.c:18:15: warning: incompatible pointer types passing 'double *' to parameter of type 'char *' [-Wincompatible-pointer-types]
swap(&ad, &bd);
^~~
swap9.c:3:26: note: passing argument to parameter 'b' here
void swap(char* a, char* b)
^
4 warnings generated.
./a.out
main : ad=3.000000, bd=4.000000
main : a=4, b=3integer는 swap이 되었으나, double은 swap 되지 않았다.
integer가 4byte이고, double이 8byte로 해석하는 머신이라 가정할 때,
맨 앞의 1byte만 swap 한 것이다.
온전하게 swap 하려면, 넘기는 타입의 크기를 넘겨주어 처리하면 될 것이다.
#include <stdio.h>
void swap(char* a, char* b, int size)
{
char t;
int i;
for (i = 0; i < size; i++)
{
t = a[i];
a[i] = b[i];
b[i] = t;
}
}
int main()
{
double ad = 3., bd = 4.;
int a = 3, b = 4;
swap(&a, &b, sizeof(a));
swap(&ad, &bd, sizeof(ad));
printf("main : ad=%lf, bd=%lf\n", ad, bd);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}clang swap10.c
swap10.c:21:10: warning: incompatible pointer types passing 'int *' to parameter of type 'char *' [-Wincompatible-pointer-types]
swap(&a, &b, sizeof(a));
^~
swap10.c:3:17: note: passing argument to parameter 'a' here
void swap(char* a, char* b, int size)
^
swap10.c:21:14: warning: incompatible pointer types passing 'int *' to parameter of type 'char *' [-Wincompatible-pointer-types]
swap(&a, &b, sizeof(a));
^~
swap10.c:3:26: note: passing argument to parameter 'b' here
void swap(char* a, char* b, int size)
^
swap10.c:22:10: warning: incompatible pointer types passing 'double *' to parameter of type 'char *' [-Wincompatible-pointer-types]
swap(&ad, &bd, sizeof(ad));
^~~
swap10.c:3:17: note: passing argument to parameter 'a' here
void swap(char* a, char* b, int size)
^
swap10.c:22:15: warning: incompatible pointer types passing 'double *' to parameter of type 'char *' [-Wincompatible-pointer-types]
swap(&ad, &bd, sizeof(ad));
^~~
swap10.c:3:26: note: passing argument to parameter 'b' here
void swap(char* a, char* b, int size)
^
4 warnings generated.
./a.out
main : ad=4.000000, bd=3.000000
main : a=4, b=3경고문은 많이 생겼으나, swap이 되는 것을 확인할 수 있다.
호출자가 파라미터 타입에 맞게 형변환 하여 넘겨주면 경고문을 없앨 수 있다.
#include <stdio.h>
void swap(char* a, char* b, int size)
{
char t;
int i;
for (i = 0; i < size; i++)
{
t = a[i];
a[i] = b[i];
b[i] = t;
}
}
int main()
{
double ad = 3., bd = 4.;
int a = 3, b = 4;
swap((char*)&a, (char*)&b, sizeof(a));
swap((char*)&ad, (char*)&bd, sizeof(ad));
printf("main : ad=%lf, bd=%lf\n", ad, bd);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}main : ad=4.000000, bd=3.000000
main : a=4, b=3
🤔 생각해 보자.
사용자가 호출할 때마다 타입 캐스팅을 하는 것이 올바른 설계일까?
라이브러리는 편하게 구현되어 있고, 사용자가 불편하게 쓰는 상황인 것이다.
void 포인터를 이용할 시간이 왔다.
void 포인터는 캐스팅 없이 받아주는 포인터이다.
swap12.c
#include <stdio.h>
void swap(void* a, void* b, int size)
{
char t;
int i;
for (i = 0; i < size; i++)
{
t = a[i];
a[i] = b[i];
b[i] = t;
}
}
int main()
{
double ad = 3., bd = 4.;
int a = 3, b = 4;
swap(&a, &b, sizeof(a));
swap(&ad, &bd, sizeof(ad));
printf("main : ad=%lf, bd=%lf\n", ad, bd);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}호출자가 타입 캐스팅 하지 않아도 쓸 수 있는 모습이다.
🚨 하지만, “void 포인터를 직접 쓰는 것은 불법”이다. 따라서 컴파일해보면 에러가 발생하며 컴파일되지 않는다.
clang swap12.c
swap12.c:10:11: error: assigning to 'char' from incompatible type 'void'
t = a[i];
^ ~~~~
swap12.c:11:14: error: incomplete type 'void' is not assignable
a[i] = b[i];
~~~~ ^
swap12.c:12:14: error: incomplete type 'void' is not assignable
b[i] = t;
~~~~ ^
3 errors generated.
void 포인터로 받아온 포인터가 확인할 크기를 컴파일러에게 알려줘야 한다. 따라서, character 포인터로 캐스팅하자.
swap13.c
#include <stdio.h>
void swap(void* a, void* b, int size)
{
char t;
int i;
char* p = (char*)a;
char* q = (char*)b;
for (i = 0; i < size; i++)
{
t = p[i];
p[i] = q[i];
q[i] = t;
}
}
int main()
{
double ad = 3., bd = 4.;
int a = 3, b = 4;
swap(&a, &b, sizeof(a));
swap(&ad, &bd, sizeof(ad));
printf("main : ad=%lf, bd=%lf\n", ad, bd);
printf("main : a=%d, b=%d\n", a, b);
return 0;
}main : ad=4.000000, bd=3.000000
main : a=4, b=3사용자에게 편한 형태로 구현했다.
타입에 대한 캐스팅 에러가 없고, 스왑 로직이 동작하기 때문에 generic swap이라 할 수 있다.
커널에서의 generic swap
https://github.com/torvalds/linux/blob/v3.10/lib/sort.c#L19
static void generic_swap(void *a, void *b, int size)
{
char t;
do {
t = *(char *)a;
*(char *)a++ = *(char *)b;
*(char *)b++ = t;
} while (--size > 0);
}리눅스 커널에 작성되어 있는 generic_swap 함수이다.
최적화 포인트 3가지를 보자.
- 포인터 연산으로 인덱싱
- (포인터를 통한 오프셋 처리가 인덱스를 통한 접근보다 빠름)하고 있고,
- 반복문 루프를 도는 변수 최소화.
- —size > 0 은 0과의 비교를 하여 더 빠르다.
- size와 i 와의 동등 비교가 아닌, zero 와의 비교. 어셈블리 상에서 플래그가 더 줄음
테스트해보자.
swap13.c
#include <stdio.h>
void generic_swap(void *a, void *b, int size)
{
char t;
do {
t = *(char *)a;
*(char *)a++ = *(char *)b;
*(char *)b++ = t;
} while (--size > 0);
}
int main()
{
double ad=3., bd=4.;
int a=3, b=4;
generic_swap( &a, &b, sizeof(a) );
generic_swap( &ad,&bd, sizeof(ad) );
printf("main : ad=%lf, bd=%lf\n", ad, bd );
printf("main : a=%d, b=%d\n", a, b );
return 0;
}main : ad=4.000000, bd=3.000000
main : a=4, b=3Part2. Generic Sort
Generic swap을 이용하여, Generic sort를 구현하자.
정렬 알고리듬으로는 bubble sort 알고리듬을 적용한다.
Generic 하지 않은 sorting
sort1.c
#include <stdio.h>
void generic_swap(void* a, void* b, int size)
{
char t;
do {
t = *(char*)a;
*(char*)a++ = *(char*)b;
*(char*)b++ = t;
} while (--size > 0);
}
void bubble(int* a, int n)
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
generic_swap(a + j, a + j + 1, sizeof(a[0]));
}
}
}
}
int main()
{
int a[] = { 400, 300, 500, 200, 600, 100, 700 };
int i;
bubble(a, 7);
for (i = 0; i < 7; i++) {
printf("%4d", a[i]);
}
printf("\n");
return 0;
}clang sort1.c
./a.out
100 200 300 400 500 600 700cf) 이후 내용에서 특별한 사항이 존재하지 않는다면, 출력문만 기입해 두겠다.
bubble sort 알고리듬을 구현한 bubble 함수의 인자를 보면 integer로 고정이다.
👁️ void * (void 포인터)를 이용하자
sort2.c
#include <stdio.h>
void generic_swap(void* a, void* b, int size)
{
char t;
do {
t = *(char*)a;
*(char*)a++ = *(char*)b;
*(char*)b++ = t;
} while (--size > 0);
}
void bubble(void* a, int n, int size)
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (*((char*)a + j * size) > *((char*)a + (j + 1) * size)) {
generic_swap((char*)a + j * size,
(char*)a + (j + 1) * size,
size);
}
}
}
}
int main()
{
int a[] = { 400, 300, 500, 200, 600, 100, 700 };
int i;
bubble(a, 7, sizeof(a[0]));
for (i = 0; i < 7; i++) {
printf("%4d", a[i]);
}
printf("\n");
return 0;
}정렬 대상 a를 void 포인터로 받았다.
그로 인해 몇 가지 수정 사항이 있다.
- void 포인터는 직접 쓸 수 없기에, 사용 시 타입캐스팅을 해야 한다.
- 최소단위인 1byte씩 해석하기 위해, char 포인터로 캐스팅하며, 대상의 타입 size를 받아와서 해석한다.
하지만, 아직 수정할 부분이 있다.
위 코드를 컴파일 후, 실행하면 아래와 같은 출력이다.
400 700 200 500 300 600 100
sort3.c
#include <stdio.h>
void generic_swap(void* a, void* b, int size)
{
char t;
do {
t = *(char*)a;
*(char*)a++ = *(char*)b;
*(char*)b++ = t;
} while (--size > 0);
}
void bubble(void* a, int n, int size)
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (*(int*)((char*)a + j * size) > *(int*)((char*)a + (j + 1) * size)) {
generic_swap((char*)a + j * size,
(char*)a + (j + 1) * size,
size);
}
}
}
}
int main()
{
int a[] = { 400, 300, 500, 200, 600, 100, 700 };
int i;
bubble(a, 7, sizeof(a[0]));
for (i = 0; i < 7; i++) {
printf("%4d", a[i]);
}
printf("\n");
return 0;
}수정 부분은 아래와 같다.
void bubble(void* a, int n, int size)
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
- if (*((char*)a + j * size) > *((char*)a + (j + 1) * size)) {
+ if (*(int*)((char*)a + j * size) > *(int*)((char*)a + (j + 1) * size)) {
generic_swap((char*)a + j * size,
(char*)a + (j + 1) * size,
size);
}
}
}
}대소 비교 시, 포인터를 수동 계산으로 각 원소를 뽑아냈다.
char 타입: (char*)a
int 타입: j * size
두 타입의 연산에서 character 포인터가 더 상위 타입이므로, 프로모션으로 character 포인터가 된다.
따라서, 1byte만 CPU에 올리므로 올바른 동작이 아니다.
그래서 “우선적으로” integer 포인터로 캐스팅 한 모습이다.
컴파일 후, 실행하면 올바른 결과가 나오긴 한다.
100 200 300 400 500 600 700
🚨하지만, integer 타입 캐스팅을 하는 타입 의존성이 생겨버렸다.
🤔 상황을 정리해 보자
void 포인터로 받아왔지만, 값이 필요한 상황이다.
값이 필요하다는 것은 비교문이 있어야 한다는 것이다. 비교하려면 값을 꺼내야 하고, 값을 꺼내려면 타입이 필요하다.
따라서, “값이 필요한 알고리듬은, 일반화할 수 없다”라는 논리적 추론을 할 수 있다.
swap 은 어떻게 일반화가 가능했나 정리해 보자.
swap은 무조건 바꾸는 것이지, 값이 필요하지 않았고 비교도 없었다.
값이 필요한 알고리듬 (sorting, 검색, rb-tree 등)은 비교가 필요하기 때문에 일반화가 불가능하다.
⭐️ void 포인터 만으로는 불가능하다.
🚀 함수 포인터를 이용하여 사용자에게 정책 위임하기
다른 방법을 생각하자.
현 문제점은 “비교”를 하려면 추가적 정보가 필요한 것이다.
해결책으로 비교를 사용자에게 위임하는 것이다. 테크닉 적으로는 “함수 포인터”를 쓰는 것이다.
-void bubble(void* a, int n, int size)
+void bubble(void* a, int n, int size, int (* cmp)(const void*, const void*))
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
- if (*(int*)((char*)a + j * size) > *(int*)((char*)a + (j + 1) * size)) {
+ if (cmp((char*)a + j * size, (char*)a + (j + 1) * size)) {
generic_swap((char*)a + j * size,
(char*)a + (j + 1) * size,
size);
}
}
}
}- 함수포인터와
- void 포인터를 같이 사용하여
구현체에서 타입 정보 의존도를 없앴다.
결과를 확인해 보자
sort4.c
#include <stdio.h>
void generic_swap(void* a, void* b, int size)
{
char t;
do {
t = *(char*)a;
*(char*)a++ = *(char*)b;
*(char*)b++ = t;
} while (--size > 0);
}
void bubble(void* a, int n, int size, int (* cmp)(const void*, const void*))
{
int i, j;
for (i = 0; i < n - 1; i++) {
for (j = 0; j < n - 1 - i; j++) {
if (cmp((char*)a + j * size, (char*)a + (j + 1) * size)) {
generic_swap((char*)a + j * size,
(char*)a + (j + 1) * size,
size);
}
}
}
}
int int_cmp(const void* a, const void* b)
{
return (*(int*)a - *(int*)b) > 0;
}
int main()
{
int a[] = { 400, 300, 500, 200, 600, 100, 700 };
int i;
bubble(a, 7, sizeof(a[0]), int_cmp);
for (i = 0; i < 7; i++) {
printf("%4d", a[i]);
}
printf("\n");
return 0;
} 100 200 300 400 500 600 700🙌 generic sort를 구현한 것이다!
라이브러리에서 지원하는 형태 확인하기
다양한 정렬 알고리듬의 인터페이스를 지원한다.
각 인터페이스를 확인해 보자
man qsortQSORT(3) Library Functions Manual QSORT(3)
NAME
heapsort, heapsort_b, mergesort, mergesort_b, qsort, qsort_b, qsort_r – sort functions
SYNOPSIS
#include <stdlib.h>
int
heapsort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *));
int
heapsort_b(void *base, size_t nel, size_t width,
int (^compar)(const void *, const void *));
int
mergesort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *));
int
mergesort_b(void *base, size_t nel, size_t width,
int (^compar)(const void *, const void *));
void
qsort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *));
void
qsort_b(void *base, size_t nel, size_t width,
int (^compar)(const void *, const void *));
void
qsort_r(void *base, size_t nel, size_t width, void *thunk,
int (*compar)(void *, const void *, const void *));
// ...중략qsort의 시그니처를 보면, 동일한 아이디어임을 확인할 수 있다.
테스트해 보자.
sort5.c
#include <stdio.h>
#include <stdlib.h>
void generic_swap(void* a, void* b, int size)
{
char t;
do {
t = *(char*)a;
*(char*)a++ = *(char*)b;
*(char*)b++ = t;
} while (--size > 0);
}
int int_cmp(const void* a, const void* b)
{
return (*(int*)a - *(int*)b) > 0;
}
int main()
{
int a[] = { 400, 300, 500, 200, 600, 100, 700 };
int i;
qsort(a, 7, sizeof(a[0]), int_cmp);
for (i = 0; i < 7; i++) {
printf("%4d", a[i]);
}
printf("\n");
return 0;
}커널 소스코드
리눅스의 소스코드의 sort 부분을 확인해 보자.
https://github.com/torvalds/linux/blob/v3.10/lib/sort.c
짧으니 복사해 두겠다.
/*
* A fast, small, non-recursive O(nlog n) sort for the Linux kernel
*
* Jan 23 2005 Matt Mackall <mpm@selenic.com>
*/
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/sort.h>
#include <linux/slab.h>
static void u32_swap(void *a, void *b, int size)
{
u32 t = *(u32 *)a;
*(u32 *)a = *(u32 *)b;
*(u32 *)b = t;
}
static void generic_swap(void *a, void *b, int size)
{
char t;
do {
t = *(char *)a;
*(char *)a++ = *(char *)b;
*(char *)b++ = t;
} while (--size > 0);
}
/**
* sort - sort an array of elements
* @base: pointer to data to sort
* @num: number of elements
* @size: size of each element
* @cmp_func: pointer to comparison function
* @swap_func: pointer to swap function or NULL
*
* This function does a heapsort on the given array. You may provide a
* swap_func function optimized to your element type.
*
* Sorting time is O(n log n) both on average and worst-case. While
* qsort is about 20% faster on average, it suffers from exploitable
* O(n*n) worst-case behavior and extra memory requirements that make
* it less suitable for kernel use.
*/
void sort(void *base, size_t num, size_t size,
int (*cmp_func)(const void *, const void *),
void (*swap_func)(void *, void *, int size))
{
/* pre-scale counters for performance */
int i = (num/2 - 1) * size, n = num * size, c, r;
if (!swap_func)
swap_func = (size == 4 ? u32_swap : generic_swap);
/* heapify */
for ( ; i >= 0; i -= size) {
for (r = i; r * 2 + size < n; r = c) {
c = r * 2 + size;
if (c < n - size &&
cmp_func(base + c, base + c + size) < 0)
c += size;
if (cmp_func(base + r, base + c) >= 0)
break;
swap_func(base + r, base + c, size);
}
}
/* sort */
for (i = n - size; i > 0; i -= size) {
swap_func(base, base + i, size);
for (r = 0; r * 2 + size < i; r = c) {
c = r * 2 + size;
if (c < i - size &&
cmp_func(base + c, base + c + size) < 0)
c += size;
if (cmp_func(base + r, base + c) >= 0)
break;
swap_func(base + r, base + c, size);
}
}
}
EXPORT_SYMBOL(sort);
#if 0
/* a simple boot-time regression test */
int cmpint(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
static int sort_test(void)
{
int *a, i, r = 1;
a = kmalloc(1000 * sizeof(int), GFP_KERNEL);
BUG_ON(!a);
printk("testing sort()\n");
for (i = 0; i < 1000; i++) {
r = (r * 725861) % 6599;
a[i] = r;
}
sort(a, 1000, sizeof(int), cmpint, NULL);
for (i = 0; i < 999; i++)
if (a[i] > a[i+1]) {
printk("sort() failed!\n");
break;
}
kfree(a);
return 0;
}
module_init(sort_test);
#endif지금까지의 과정을 이해했다면, 쉽게 읽힐 코드이다.
내부적 정렬 알고리듬은 힙 정렬을 구현한 코드이다.
테스트를 해보자. 약간의 수정(static 제거, 주석 제거, 필요한 함수만 복사)을 한 코드는 아래와 같다.
sort6.c
#include <stdio.h>
#include <stdlib.h>
typedef unsigned int u32;
void u32_swap(void* a, void* b, int size)
{
u32 t = *(u32*)a;
*(u32*)a = *(u32*)b;
*(u32*)b = t;
}
void generic_swap(void* a, void* b, int size)
{
char t;
do {
t = *(char*)a;
*(char*)a++ = *(char*)b;
*(char*)b++ = t;
} while (--size > 0);
}
void sort(void* base, size_t num, size_t size,
int (* cmp_func)(const void*, const void*),
void (* swap_func)(void*, void*, int size))
{
/* pre-scale counters for performance */
int i = (num / 2 - 1) * size, n = num * size, c, r;
if (!swap_func)
swap_func = (size == 4 ? u32_swap : generic_swap);
/* heapify */
for (; i >= 0; i -= size) {
for (r = i; r * 2 + size < n; r = c) {
c = r * 2 + size;
if (c < n - size &&
cmp_func(base + c, base + c + size) < 0)
c += size;
if (cmp_func(base + r, base + c) >= 0)
break;
swap_func(base + r, base + c, size);
}
}
/* sort */
for (i = n - size; i > 0; i -= size) {
swap_func(base, base + i, size);
for (r = 0; r * 2 + size < i; r = c) {
c = r * 2 + size;
if (c < i - size &&
cmp_func(base + c, base + c + size) < 0)
c += size;
if (cmp_func(base + r, base + c) >= 0)
break;
swap_func(base + r, base + c, size);
}
}
}
//----------------------------------------------------------------------------
int int_cmp(const void* a, const void* b)
{
return (*(int*)a - *(int*)b); // 커널 코드에서는 음수를 허용하고있다. 단순히 빼는 비교 정책을 구현하면 된다. (sort5.c 를 보면 > 0 이 붙어있었다)
}
int main()
{
int a[] = { 400, 300, 500, 200, 600, 100, 700 };
int i;
sort(a, 7, sizeof(a[0]), int_cmp, 0);
for (i = 0; i < 7; i++) {
printf("%4d", a[i]);
}
printf("\n");
return 0;
} 100 200 300 400 500 600 700잘 작동하는 모습이다.
sort 함수를 분석해 보자
void sort(void* base, size_t num, size_t size,
int (* cmp_func)(const void*, const void*),
void (* swap_func)(void*, void*, int size))swap 함수 포인터를 추가로 받고 있다.
generic_swap 함수가 있는데 왜 추가로 받을까?
if (!swap_func)
swap_func = (size == 4 ? u32_swap : generic_swap);generic_swap을 언제나 쓰는 것이 아니라, 사용자가 null이라 주면 크기 비교를 통해 적용할 swap 함수를 다르게 택한다.
word 크기의 경우 추가적 연산이 필요 없는 integer 단위의 연산이 가장 빠르기에 택한 최적화이다.
'알고리듬 & 자료구조' 카테고리의 다른 글
| 알고리듬 성능 요인 - cache (0) | 2024.09.25 |
|---|
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- tomcat11
- 연관관계 편의 메서드
- generic swap
- reader-writer lock
- tree
- generic sort
- OOP
- servlet
- 엔티티 설계 주의점
- S1
- JPA
- 톰캣11
- PS
- 객체 변조 방어
- thread
- CPU
- Memory
- Dispatcher Servlet
- C
- 이진탐색
- S4
- core c++
- pocu
- 논문추천
- 개발 공부 자료
- Spring MVC
- condition variable
- 백준
- sleep lock
- Java
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 |
글 보관함