Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
본 글은 복잡한 수식 파싱 경험과 해시 테이블 구현 과정을 회고하며, 자료구조와 알고리즘의 근본 원리를 강조합니다. 특히 C나 Python 같은 저수준 언어에서도 핵심 개념을 직접 구현할 수 있음을 보여주며, 개발 과정에서 '불가능하다'는 선입견에 대한 경각심을 일깨웁니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 RSS: GeekNews (한국어)의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기Greenspun의 프로그래밍 제10법칙이 떠오름. 충분히 복잡한 C나 Fortran 프로그램에는 Common Lisp의 절반을 임시방편으로, 비공식 명세에 따라, 버그투성이에 느리게 구현한 무언가가 들어 있음.
대학 조별 과제에서 Excel 수식 파서를 맡았는데, 엿새쯤 고민하다가 문자열을 찾아 바꾸는 작업을 숫자 하나가 남을 때까지 반복하면 된다는 걸 깨달았음.
괄호와 쉼표를 추적해 함수 형태의 수식을 파싱하는 부분은 이미 만들었고, 산술 연산자는 우선순위에 따라 3+6*2 → 3+MUL(6,2) → ADD(3,MUL(6,2))처럼 바꾸면 됐음. 이후 안쪽부터 ADD(3,MUL(6,2)) → ADD(3,12) → 15로 평가하는 방식임.
어쩌다 보니 코드가 1,000줄에 달했는데, 같은 과제를 한 다른 학생은 정규식으로 50줄에 끝냈다고 함. 돌이켜 보면 드라이버로 못을 박은 셈임. 나중에 ADD() 구문 없이 산술 파서만 다시 만들어 보니, 정규식도 쓰지 않고 JavaScript 약 30줄로 훨씬 깔끔하게 구현할 수 있었음. 물론 eval이면 한 줄도 가능함.
왜 불가능하다고 생각했는지 궁금함. 필요한 건 자료구조와 알고리즘 기초뿐임. 내가 학위를 딸 때는 실습 과제를 전부 C로 제출해야 했음.
참고할 만한 책으로는 『Data Structures, Algorithms, and Software Principles in C』 1994년판이 있음. https://www.amazon.com/dp/0201591189
CPython의 해시 테이블 구현도 살펴볼 만함. 실제로 쓰이는 구현치고는 놀랄 만큼 이해하기 쉬운 편임.
대학에서 해시 테이블을 배우고 C로 직접 구현해야 했으며, 아마 1학년 때였을 것임. 위키백과에 따르면 개념과 어셈블리 구현은 1953년까지 거슬러 올라감. C가 등장한 뒤에는 당연히 C로도 구현했을 것임.
C로 해시 테이블을 만들 수 없다면 C보다 고수준인 Python에서도 만들 수 없을 것임. 고수준 언어로 할 수 있는 일은 거의 정의상 저수준 언어로도 가능하지만, 그 역까지 반드시 성립하는 건 아님. Python처럼 고수준 언어 자체가 저수준 언어로 구현되기도 함.
Python에 내장된 dict도 해시 테이블이며, 거의 확실히 C로 작성됐을 것임. Raymond Hettinger의 Python 딕셔너리 강연 영상을 찾아보거나 인터프리터 소스 코드를 살펴보면 됨.
기억이 맞는다면 Kernighan과 Ritchie의 『The C Programming Language』 초판에도 충돌 처리용 버킷을 갖춘 간단한 C 해시 테이블 예제가 있었음. 키에 들어 있는 모든 문자의 ASCII 값을 더한 뒤 특정 수로 나눈 나머지를 쓰는 단순한 알고리즘임.
realloc으로 메모리 블록이 이동해 내부 포인터가 깨진다면, 아레나 배열의 인덱스를 저장하면 되지 않을까? 4바이트 인덱스를 쓰면 메모리도 줄일 수 있을 것임. 다만 Fib(40)이 노드 약 13억 개를 만들고 12GB 넘게 쓰다가 메모리 부족으로 죽었다니, 8바이트 인덱스를 유지해도 되겠음.
실행을 모두 멈추는 표시 후 쓸기 방식 대신 복사형 가비지 컬렉터는 어떨까? 재귀 피보나치는 쓰레기를 많이 만들지만, 기억하기로 어느 한 시점에 살아 있는 객체 집합은 꽤 작음. 실제 생존 객체가 매우 많은 GC 벤치마크가 필요하다면, n == 0에서 None을 반환하고 그 외에는 (garbage(n-1), garbage(n-1))을 반환하는 함수를 쓰면 됨. 적절한 자료구조가 없어도 클로저로 쉽게 흉내 낼 수 있음.
피보나치 평가 방식을 바꾼다는 건 AST를 재귀 순회하는 방식을 바꾸겠다는 뜻인가, 아니면 지수 시간이 걸리지 않는 피보나치 알고리즘을 쓰겠다는 뜻인가?
새 기능을 화이트보드에 그릴 때 “방금 ‘그냥’이라고 했어?”라는 말을 자주 썼음. 대개 누군가 너무 야심 차게 생각할 때 제동을 거는 용도였음. 이 글에서는 “just”가 23번 등장함. 때로는 정말 그냥 밀어붙여야 할 때도 있음.
글쓴이처럼 메모리 관리를 직접 설계하는 데 빠져드는 건 유혹적이고 학습용으로도 가치가 있겠지만, 실제로 눈에 띄는 성능 향상을 얻은 사람이 있을까? mimalloc과 tcmalloc 같은 라이브러리는 전문가들이 공들여 최적화하므로, 모든 할당과 해제에 지원되는 malloc과 free를 쓰는 것보다 가볍게 덧붙인 자체 기법이 더 나을 가능성은 낮아 보임. 여기서는 어떤 접근을 추천하는지 궁금함.
내 경험상 99%는 malloc/free가 최선임. 충분히 빠르고 검증됐으며, 이미 모든 곳에서 쓰고 있음.
나머지 1%에서는 맞지 않는 요구가 생김. 복잡한 객체 그래프에는 소유 지점이 하나로 정해지지 않거나, 해제 가능 지점마다 직접 해제하도록 관리하기가 너무 어려울 수 있음. 이때는 참조 계수를 포함한 가비지 컬렉션을 고려할 수 있음. 네트워크 서버의 요청 처리처럼 짧은 시간에 많이 할당하고 요청이 끝나면 한꺼번에 버리면서 지연 시간을 최소화해야 하는 경우도 있음.
다만 모두 절충이 필요함. GC를 쓰면 예측 가능성이 떨어지고 성능은 좋아질 수도 나빠질 수도 있음. 방식에 따라 포인터 주소를 안정적으로 유지하거나 객체 종료 처리를 수행하지 못할 수 있음. 아레나는 개별 해제나 재할당이 불가능하므로 적용 범위를 좁은 실행 구간으로 제한해야 함. 글쓴이도 이 부분에서 잘못 접근했음.
어떤 방식을 택하든 애플리케이션 곳곳으로 할당자를 전달하고, 자료구조도 직접 구현해야 할 가능성이 큼. 영속 데이터에는 GC, 연결별·요청별 데이터에는 아레나를 쓰는 식으로 여러 할당자가 동시에 필요할 수도 있음. 자체 할당자에는 버그가 생기기 쉬우며, 이런 버그는 찾기도 고치기도 무척 까다로움. 피할 수 있다면 피하길 권하지만, 제약이 많아 직접 뛰어들어야 할 때도 있음.
재미와 배움을 기준으로 추천함. 배우는 것도 재미있는 일이기 때문임.
“이거 하나 해보자 → 아, 망했네 → 반복”하는 전개 방식이 마음에 듦. 항 재작성, 즉 글에서 말한 그래프 축약이 곧 평가임.
예전에 모든 것이 객체인 프로그래밍 언어를 만든 적이 있음. 메시지 키워드도 없고, 1도 +도 객체임. 객체에 다른 객체를 보내면 객체를 돌려받음. 1+는 1에 +를 보낸 결과 객체이며, 여기에 1을 보내면 2가 나오고 +를 보내면 실행 중 타입 오류가 발생함. 반대 방향도 가능해서 +1 역시 객체이고, 이를 2에 보내면 3이 됨.
목록 객체를 더하면 흥미로워짐. (1,2,3,4,5)+1 → (1+,2+,3+,4+,5+) 1 → (2,3,4,5,6)처럼 동작함.