[백준] 10825번: 국영수
이 문제를 최적화하면서 공부해 볼 것이다. 간단한 문제이지만 최적화에 따라 메모리 사용량과 실행 시간 등이 크게 달라진다.
진행할 최적화 유형은 아래와 같다.
- mmap을 통한 커널 직접 호출
- 기수정렬 구현을 통한 정렬 성능 최적화
- 정렬할 요소 크기에 따른 정렬 알고리즘 변경
- AMD64에서 진행하는 SIMD 최적화
SIMD 부분은 ARM64 SIMD 관련 문서를 참고하면 같은 맥락이다. mmap을 통한 호출은 아직 다룬 적이 없었는데, BMP 관련 공부를 할 때 해 보면 좋을 것이다.
문제
도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.
- 국어 점수가 감소하는 순서로
- 국어 점수가 같으면 영어 점수가 증가하는 순서로
- 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
- 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)
입력
첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.
출력
문제에 나와있는 정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력한다.
예제 입력 1
12
Junkyu 50 60 100
Sangkeun 80 60 50
Sunyoung 80 70 100
Soong 50 60 90
Haebin 50 60 100
Kangsoo 60 80 100
Donghyuk 80 60 100
Sei 70 70 70
Wonseob 70 70 90
Sanghyun 70 70 80
nsj 80 80 80
Taewhan 50 60 90
예제 출력 1
Donghyuk
Sangkeun
Sunyoung
nsj
Wonseob
Sanghyun
Sei
Kangsoo
Haebin
Junkyu
Soong
Taewhan
출처
- 문제를 만든 사람: baekjoon
- 데이터를 추가한 사람: alssel2525
- 빠진 조건을 찾은 사람: djm03178
알고리즘 분류
- 정렬
정렬 알고리즘의 한계를 넘어서: 52ms에서 8ms까지
동일한 정렬 문제에서 라이브러리 수준의 최적화를 넘어 시스템 아키텍처와 알고리즘의 특성을 극한으로 활용했을 때 발생하는 성능 차이를 분석한다.
1. 기존 구현 (Baseline: 52ms)
초기 구현은 표준 라이브러리(scanf, qsort, printf)에 의존한다.
- I/O 병목:
scanf와printf는 가변 인자 파싱과 버퍼링 오버헤드로 인해 대량의 데이터 처리 시 심각한 지연을 발생시킨다. - 비교 기반 정렬:
qsort는 $O(N \log N)$의 시간 복잡도를 가지며, 매 비교마다 함수 포인터를 통한 오버헤드가 발생한다. - 데이터 구조: 16바이트 정렬은 되어 있으나, 데이터 접근 패턴이 캐시 효율을 극대화하지 못한다.
2. 최적화 구현 (Advanced: 8ms)
성능을 결정짓는 세 가지 핵심 요소(I/O, 메모리 아키텍처, 알고리즘)를 전면 개편하였다.
A. Zero-copy I/O 및 고속 파싱
표준 입출력 스트림 대신 리눅스 커널의 mmap 시스템 콜을 사용한다. 파일 캐시를 유저 공간에 직접 매핑하여 메모리 복사 횟수를 제로(Zero-copy)에 수렴하게 한다. 또한, NEXT_INT 매크로를 통해 정수 파싱 과정에서 발생하는 상태 머신 오버헤드를 제거하였다.
B. 데이터 레이아웃 최적화 (Key Packing)
국어(내림), 영어(오름), 수학(내림) 점수를 하나의 24비트 정수 key로 압축하였다.
- 내림차순 정렬이 필요한 과목은
255 - 점수를 적용하여 모든 조건이 정수 오름차순 정렬로 귀결되도록 설계하였다. - 이를 통해 복잡한 분기 조건문 없이 단순 산술 비교만으로 정렬 우선순위를 판단할 수 있다.
C. Radix Sort의 도입
비교 기반 정렬의 하한선인 $O(N \log N)$을 탈피하기 위해 LSD(Least Significant Digit) Radix Sort를 구현하였다.
- 24비트 키를 8비트씩 3번의 패스(Pass)로 처리하여 $O(N)$의 시간 복잡도를 달성한다.
- Radix Sort는 안정 정렬(Stable Sort)이므로, 과목 점수가 동일한 경우 발생하는 타이 브레이크(Tie-break) 처리에 유리하다.
D. 하이브리드 타이 브레이킹 (Tie-breaking)
점수 키가 완전히 일치하는 그룹에 대해서만 이름순 정렬을 수행한다.
- 그룹의 크기가 작은 경우(32 이하)는 데이터 이동이 적은 Insertion Sort를 사용한다.
- 그룹의 크기가 큰 경우에만
qsort를 호출하여 불필요한 함수 호출 비용을 최소화한다.
3. 실습 코드
표준적 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#define STUDENT_MAX_NAME_LEN 11
// Declare a student type
typedef struct student {
char name[STUDENT_MAX_NAME_LEN];
// uint8_t to save memory space
uint8_t korean ;
uint8_t english;
uint8_t math ;
} student_t;
int compare(const void *a, const void *b) {
const student_t *student_a = (const student_t *)a;
const student_t *student_b = (const student_t *)b;
// if Korean Score is Not Same
if(student_a->korean != student_b->korean) {
return student_b->korean - student_a->korean;
}
// if English Score is Not Same
if(student_a->english != student_b->english) {
return student_a->english - student_b->english;
}
// if Math Score is Not Same
if(student_a->math != student_b->math) {
return student_b->math - student_a->math;
}
// else Sort by Name
return strncmp(student_a->name, student_b->name, STUDENT_MAX_NAME_LEN);
};
int main(void) {
int students_len;
int student_t_len = sizeof(student_t);
// Scan how Many Students are in a class
scanf("%d", &students_len);
// Declare students as an Array
// calloc(nr, size) to ensure \0 escape
student_t *students = calloc(students_len, student_t_len);
for(int i = 0; i < students_len; i++) {
// Name, Korean, English, Math order
// uint8_t is okay, 0 <= score <= 100
scanf("%s %hhu %hhu %hhu", students[i].name, &students[i].korean, &students[i].english, &students[i].math);
}
// Sort by declared compare function
qsort(students, students_len, student_t_len, compare);
// Print(Name Only)
for(int i = 0; i < students_len; i++) {
printf("%s\n", students[i].name);
}
free(students);
return 0;
}
튜닝한 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#define STUDENT_MAX_NAME_LEN 16
typedef struct student {
char name[STUDENT_MAX_NAME_LEN]; // zero-padded
uint32_t key; // packed sort key (24-bit used)
} __attribute__((aligned(16))) student_t;
static inline uint32_t make_key(uint8_t kor, uint8_t eng, uint8_t math) {
// Desired order:
// korean desc, english asc, math desc
// Encode to ascending integer key:
// (255-kor) asc, eng asc, (255-math) asc
return ((uint32_t)(uint8_t)(255u - kor) << 16) |
((uint32_t)eng << 8) |
(uint32_t)(uint8_t)(255u - math);
}
static int compare_name_only(const void *a, const void *b) __attribute__((hot));
static int compare_name_only(const void *a, const void *b) {
const student_t *sa = (const student_t *)a;
const student_t *sb = (const student_t *)b;
return memcmp(sa->name, sb->name, STUDENT_MAX_NAME_LEN);
}
static inline void insertion_sort_name(student_t *a, int n) {
for (int i = 1; i < n; i++) {
student_t x = a[i];
int j = i - 1;
while (j >= 0 && memcmp(a[j].name, x.name, STUDENT_MAX_NAME_LEN) > 0) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
}
/*
24-bit LSD radix sort, stable, 3 passes of 8 bits.
pass0 (shift 0): arr -> tmp
pass1 (shift 8): tmp -> arr
pass2 (shift 16): arr -> tmp
final: tmp holds sorted result, copy back to arr
*/
static inline void radix_sort_by_key_24(student_t *arr, student_t *tmp, int n) {
size_t count[256];
// pass 0 (shift 0): arr -> tmp
memset(count, 0, sizeof(count));
for (int i = 0; i < n; i++) count[arr[i].key & 0xFFu]++;
size_t sum = 0;
for (int i = 0; i < 256; i++) { size_t c = count[i]; count[i] = sum; sum += c; }
for (int i = 0; i < n; i++) {
unsigned b = arr[i].key & 0xFFu;
tmp[count[b]++] = arr[i];
}
// pass 1 (shift 8): tmp -> arr
memset(count, 0, sizeof(count));
for (int i = 0; i < n; i++) count[(tmp[i].key >> 8) & 0xFFu]++;
sum = 0;
for (int i = 0; i < 256; i++) { size_t c = count[i]; count[i] = sum; sum += c; }
for (int i = 0; i < n; i++) {
unsigned b = (tmp[i].key >> 8) & 0xFFu;
arr[count[b]++] = tmp[i];
}
// pass 2 (shift 16): arr -> tmp
memset(count, 0, sizeof(count));
for (int i = 0; i < n; i++) count[(arr[i].key >> 16) & 0xFFu]++;
sum = 0;
for (int i = 0; i < 256; i++) { size_t c = count[i]; count[i] = sum; sum += c; }
for (int i = 0; i < n; i++) {
unsigned b = (arr[i].key >> 16) & 0xFFu;
tmp[count[b]++] = arr[i];
}
memcpy(arr, tmp, (size_t)n * sizeof(student_t));
}
int main(void) {
// mmap for zero-copy input
struct stat st;
fstat(0, &st);
char *p = (char *)mmap(NULL, (size_t)st.st_size, PROT_READ, MAP_PRIVATE, 0, 0);
char *end = p + st.st_size;
// Fast parsing integer from mmap pointer
#define NEXT_INT(n) do { \
unsigned _x = 0; \
while (p < end && ((unsigned char)*p < '0' || (unsigned char)*p > '9')) p++; \
while (p < end && ((unsigned char)*p >= '0' && (unsigned char)*p <= '9')) _x = _x * 10u + (unsigned)(*p++ - '0'); \
(n) = _x; \
} while (0)
unsigned students_len_u;
NEXT_INT(students_len_u);
int students_len = (int)students_len_u;
student_t *students = (student_t *)aligned_alloc(16, (size_t)students_len * sizeof(student_t));
if (!students) students = (student_t *)malloc((size_t)students_len * sizeof(student_t));
student_t *tmp = (student_t *)aligned_alloc(16, (size_t)students_len * sizeof(student_t));
if (!tmp) tmp = (student_t *)malloc((size_t)students_len * sizeof(student_t));
if (!students || !tmp) return 0;
for (int i = 0; i < students_len; i++) {
// parse name, zero-pad to 16
while (p < end && (unsigned char)*p <= ' ') p++;
char *dst = students[i].name;
char *dst_end = dst + STUDENT_MAX_NAME_LEN;
while (p < end && (unsigned char)*p > ' ' && dst < dst_end) *dst++ = *p++;
// consume rest of token if longer than buffer (shouldn't happen in this problem)
while (p < end && (unsigned char)*p > ' ') p++;
// zero pad remaining
while (dst < dst_end) *dst++ = 0;
unsigned kor_u, eng_u, math_u;
NEXT_INT(kor_u);
NEXT_INT(eng_u);
NEXT_INT(math_u);
students[i].key = make_key((uint8_t)kor_u, (uint8_t)eng_u, (uint8_t)math_u);
}
// radix sort by key (24-bit)
radix_sort_by_key_24(students, tmp, students_len);
// tie-break: same key => name asc (switch insertion/qsort by run length)
enum { INSERTION_THRESHOLD = 32 };
for (int i = 0; i < students_len; ) {
int j = i + 1;
uint32_t k = students[i].key;
while (j < students_len && students[j].key == k) j++;
int run_len = j - i;
if (run_len > 1) {
if (run_len <= INSERTION_THRESHOLD) {
insertion_sort_name(students + i, run_len);
} else {
qsort(students + i, (size_t)run_len, sizeof(student_t), compare_name_only);
}
}
i = j;
}
// output buffer
char *out_buf = (char *)malloc((size_t)students_len * 12);
char *q = out_buf;
for (int i = 0; i < students_len; i++) {
const char *s = students[i].name;
while (*s) *q++ = *s++;
*q++ = '\n';
}
write(1, out_buf, (size_t)(q - out_buf));
free(tmp);
free(students);
free(out_buf);
return 0;
}
4. 성능 비교 및 결론
| 지표 | 기존 구현 | 최적화 구현 | 개선율 |
|---|---|---|---|
| 시간 복잡도 | - | ||
| I/O 방식 | scanf / printf |
mmap / write |
- |
| 실행 시간 | 52ms | 8ms | 약 85% 단축 |
| 메모리 점유 | 3852KB | 10476KB | 약 172% 악화 |
이러한 방식은 메모리 정렬이 엄격하게 필요하기 때문에 커널 호출로 일부 성능 이점을 가지고 오더라도 메모리를 너무 낭비하게 된다. 특수한 상황에서는 확실히 적용해 볼 만한 최적화이다.
비유를 해 보자면, 색종이를 더럽게 잘라도 적게 쓰는 것과, 색종이를 깔끔하게 잘라서 빨리 자르지만 종이를 낭비하는 것이다. 대부분의 경우 C언어를 사용하는 환경은 메모리가 제한되어 있기 때문에 깔끔하게 짜고 컴파일러를 믿는 것이 좋다. 하지만 고도의 성능을 요구하는 일부 엔터프라이즈 환경에서는 상사가 쓰라고 하면 쓰는 정도는 될 수 있다. 그러나 나의 판단으로 SIMD는 이미 널리 쓰이니 그렇다 치더라도 커널 호출을 굳이 하는 것은 권장할 바가 아니라고 생각한다.
맺으며
당연한 소리지만, 실제 코딩 테스트에서 이런 짓을 하지는 말자. 시간이 모자란다.