<aside>
⛔ 42 과제 get_next_line
에 대한 스포일러를 포함하고 있습니다.
아직 get_next_line
과제를 완료하지 않으셨다면, 살포시 뒤로가기 눌러주세요!
</aside>
<aside>
⚠️ get_next_line
프로젝트를 위한 가이드가 아닙니다. 아마도 도움이 안 될 거에요...
</aside>
get_next_line
돌아보기get_next_line
과제는 파일 2개, 함수 10개가 최대입니다.
이 10개의 함수만으로 모든 것을 해결하는 것은... 상당히 골치 아픈 일입니다.
다른 프로젝트에서 get_next_line
을 사용할 수 있습니다. 물론 전 절대로 안 쓸 거지만,
다른 프로젝트에서도 쓸 것이라면 아무래도 어느 정도는 효율적으로 만드는 게 좋겠죠?
일단 get_next_line
에서 시간복잡도를 말아먹기 좋은 부분을 알아보겠습니다.
fd
에서 한 줄씩 읽어서 리턴하는 get_next_line(fd)
함수를 만들면 됩니다.
단, 전역변수를 사용할 수 없고 static 변수를 딱 한 개 사용할 수 있으며
read(fd, buffer, size)
호출에 사용할 size
로 정해진 매크로 상수를 사용해야 합니다.
파일이 끝나거나 오류가 발생하면 NULL
을 리턴합니다.
자잘한 예외 처리, 모든 기능을 10개의 함수에 욱여넣기가 사실 제일 어려운 부분이겠지만
내부에서 사용하기 위해 구현해야 할 것이 크게 두 가지가 있습니다.
fd
에서 읽은 (추후 문자열로 바꿀) 데이터를 임시로 저장해야 합니다.fd
를 키로 해서 삽입/삭제, 검색)우선 만만한 2번부터 보겠습니다.
일단 맵을 OPEN_MAX
길이의 고정 길이 배열로 만드는 건 반칙입니다.
OPEN_MAX
는 고정되어 있고, 실제로 OPEN_MAX
보다 큰 fd
가 있을 수 있습니다.
결국 가변 길이 자료구조를 사용한 맵을 만들어야 하는데, 상당히... 쉽지 않습니다.
가장 만만한 방법이 링크드리스트를 사용한 맵인데, 삽입/삭제/검색이 모두 $O(n)$입니다.
사실 맵은 그다지 고민하지 않아도 됩니다. 사실 진짜 문제가 되는 부분은 이 부분입니다.
문자열을 합치는 것은 $O(n)$입니다.
여러 번에 나눠서 read
를 호출하기 때문에 문자열을 $O(n)$번 합치게 되는데,
그러면 문자열을 합치는 부분이 총 $O(n^2)$이 됩니다.
작은 문자열을 여러 번 합치는 것처럼, 긴 문자열을 여러 번 나누는 것도 마찬가지입니다.
이 둘만 해결해도 (예외 처리를 제외하면) 꽤 쓸 만한 효율을 되찾을 수 있습니다.
문자열을 바로 합칠 필요가 없습니다.
나중에 문자열로 만들 수 있는 무언가가 필요한 것입니다.
문자열을 연결한 링크드리스트로 만들면 $O(n)$으로 해결할 수 있는 문제입니다.
typedef struct s_get_next_line_stringbuilder_node
{
struct s_get_next_line_stringbuilder_node *next;
size_t length;
char buffer[];
} t_get_next_line_stringbuilder_node;
typedef struct s_get_next_line_stringbuilder
{
t_get_next_line_stringbuilder_node *head;
t_get_next_line_stringbuilder_node *tail;
size_t total_length;
} t_get_next_line_stringbuilder;
만들어야 할 함수가 늘었네요!
stringbuilder
에 문자열을 추가하는 함수 read
까지 여기서 처리해야 할지도?)stringbuilder
의 내용대로 문자열을 만들고, 다시 비우는 함수레드블랙트리는 효율적이라서 정말 널리, 많이 쓰입니다.
…하지만 함수 10개로 모든 것을 해결해야 하는 이 프로젝트에는, 적절하지 않은 듯합니다.
Trie 기반의, 높이가 4(=sizeof(int)
)인 256(=1 << CHAR_BIT
)진 트리로도 충분합니다.
typedef union u_get_next_line_session_map
{
struct s_get_next_line_session_map **child;
t_get_next_line_session *value;
} u_get_next_line_session_map;
// key = (unsigned char *)(&fd);
// value = map[key[0]]->child[key[1]]->child[key[2]]->child[key[3]]->value;
코드를 첨부하지는 않지만, 함수 두 개로 맵에 삽입/삭제가 모두 해결됩니다.
$O(log n)$처럼 보일 수 있지만 높이와 차수가 모두 상수라 $O(1)$이고, 충분히 빠릅니다.
함수 10개로 이 기능을 효율적으로 구현하는 건 쉽지 않은 일입니다.
함수 10개에 모든 기능을 넣으면서 가독성까지 고려하는 것은 정말 어렵습니다.
심지어 함수 프로토타입 자체가, 제대로 된 예외 처리는 아예 불가능하게 생겼습니다.
다른 곳에 쓰려면 get_next_line
을 열심히 만들기보다는 그냥 따로 만드는 것을 권장합니다.
… 그래도! 효율에 대한 고민은 반드시 한 번쯤은 해 보셨으면 좋겠습니다.