[IT/리뷰] 생각하는 프로그래밍

생각하는 프로그래밍 : 네이버 도서 (naver.com)

생각하는 프로그래밍 : 네이버 도서

'프로그래밍 본질에 관한 15가지 에세이'라는 부제를 갖고 있다. 프로그래밍 기초와 관련된 다양한 관점을 다룬 여러 에세이들을 볼 수 있지 않을까 기대하고 읽기 시작했다.

 

내용은 생각 외로 우리가 평소 알고리즘 공부한다고 할 때 다루는 알고리즘, 시간/공간 복잡도, 데이터 구조 등과 관련된 내용들을 다뤘다. 그게 기초라고 할 수는 있겠지만 간단한 에세이라기보다는 깊게 다루고 있는 듯했다.

 

읽다 보니 책 자체적으로나 외부적인 환경 때문에 중간에 재미가 많이 떨어졌었는데.. 참고 꾸역꾸역 읽었다. 다시금 알고리즘적인 공부들을 해야겠다는 생각을 하는 정도로 만족했고, 그 외에 크게 도움 되는 건 없었다. 물론 에세이를 읽으면서 알고리즘을 해결하는 놀랍고 신기한 코드들은 있었다.

 

점차 흥미가 떨어진 것도 있겠지만, 서문 부분이 가장 매력이 있었다.

프로그래머로서 개발 업무를 하며 직접 정렬이나 탐색 프로그램을 개발해야 하는 경우가 얼마나 있을까? 이미 라이브러리에서 기본으로 제공하고 데이터 양이 많은 경우 데이터베이스를 사용하므로 데이터베이스의 기능을 활용하면 된다. 그러다 보니 일반 프로그래머가 정렬이나 탐색 프로그램을 직접 작성해야 하는 경우는 거의 없고 그보다 비즈니스 로직과 관련된 문제로 고민하는 경우가 더 많을 것이다. 그렇다면 알고리즘과 데이터 구조에 대한 공부는 무의미한 것일까?

---

알고리즘과 데이터 구조는 그 자체로도 중요하겠지만 더욱 중요한 것은 프로그래머로 하여금 문제에 접근하는 방법과 어떻게 해결할지에 대한 방향을 제시하는 데 있다. 이미 알고 있는 알고리즘을 적용해 쉽게 문제를 해결할 수도 있겠지만 그렇지 않은 경우도 많다. 이 책에서는 문제를 해결하는 단순한 방법의 접근부터 다른 문제를 제시한 뒤 효율적인 방법을 제시할 것이다. 경우에 따라 복잡해지기도 하지만 발상의 전환으로 더 간단한 방법을 제시하는 경우가 많다. 즉, 단순하게 알고리즘과 데이터 구조를 나열하는 것이 아니라, 문제를 분석하고 더 좋은, 더 간단한, 더 효율적인 방법을 찾는 사고 과정을 설명할 것이다.

---

"디스크 파일을 어떻게 정렬하지?"

 

이 문제를 해결하기 위한 나의 실수는 그의 질문에 그냥 답하려고 했던 것이다. merge sort에 대해 간단한 설명과 더불어 알고리즘 책을 찾아보라는 나의 충고에 그의 반응은 냉담했다. 그는 공부를 원한 것이 아니라 문제 해결을 원했다.

다시 대화를 통해 문제를 파악했을 때 정확한 문제를 기술할 수 있게 됐다.

입력 : 최대 n개의 양의 정수를 포함하는 파일로, 각 숫자는 n보다 작고, n=10^7이다. 어떤 숫자가 두 번 이상 나오는 것은 치명적 에러이다. 정수 이외에 관련된 데이터는 없다.

출력 : 입력된 정수를 오름차순으로 정렬한 리스트

제약조건 : 메모리를 많아야 대략 1MB 정도를 사용할 수 있고, 디스크 공간은 충분하다. 실행시간은 최대 몇 분 정도가 될 수 있고, 10초 정도 안에 작업을 끝낼 수 있으면 충분하다.

 

이에 대한 대응 방안은 다양할 수 있다. 첫 번째로는 간단한 머지 정렬이 생각날 수 있다. 하지만 그럼에도 여전히 실행이 느릴 수 있다.

두 번째로는 문제의 특별한 성질을 이용하는 것이다. 각 숫자를 7바이트에 저장한다면 사용 가능한 메모리(1MB)에 약 143,000개의 숫자를 저장할 수 있다. 그러나 각 숫자를 32비트 정수로 표현하면 1MB에 250,000개의 숫자를 저장할 수 있다. 따라서 우리는 입력 파일을 40번 읽는 프로그램을 이용해, 파일을 읽을 때마다 250,000개의 정수를 정렬하는 식(퀵 정렬과 유사)으로 구현할 수도 있다. 물론 입력 파일 전체를 40번이나 읽어야 한다.

위 두 가지 방안을 조합한다면 더 좋은 해결책이 나올 수 있다. 머지 정렬과 같이 입력 파일을 한 번만 읽어 들이고 작업 파일에 한 번만 쓰면서, 40 패스 알고리즘처럼 중간 파일을 사용하지 않는 방법이 있을 것이다. 

 

문제를 다시 정의하면 다음과 같을 것이다.

입력 파일 안에 있는 모든 숫자를 사용 가능한 메모리 내에 나타낼 수 있어야 한다.
따라서, 최대 1천만 개의 서로 다른 정수를 약 8백만 비트에 표현할 수 있어야 한다.

 

해결 방법은 비트맵(bitmap) 또는 비트 벡터(bit vector) 표현법을 사용하는 것이다. 이 해결책은 메모리 범위 내에서 일반적인 정렬 문제에서 사용하지 않는 세 가지 특성을 이용한 것이다.

1. 상대적으로 적은 범위의 입력
2. 중복 숫자 없음
3. 레코드에 정수 이외에 다른 연관 데이터 없음

 

제시한 비트맵 해결방안은 머지 정렬을 이용한 것보다 효율적이었다. 머지 정렬은 몇 분의 시간이 걸릴 때 이 해결방안은 약 10초의 시간 밖에 걸리지 않았다.

작은 문제에 대한 주의 깊은 분석은 때로 엄청난 실질적 이익을 얻을 수 있다. 몇 분 동안의 주의 깊은 연구로 코드 길이, 프로그래머의 작업 시간, 실행 시간을 10배 이상 줄인 케이스다.

 

시간-공간 트레이드오프인 것과 아닌 것

프로그래밍 분야에서는 시간-공간 트레이드오프가 많다. 그러나 경험 상 프로그램이 사용하는 공간을 줄이면 그 실행시간 역시 줄어드는 경우가 자주 있었다. 공간을 효율적으로 사용하는 비트맵 구조는 정렬 시간을 크게 단축시켰다. 삭용 공간을 줄이는 것이 실행시간까지 단축시키는 데는 두 가지 이유가 있다.

1. 데이터가 적다는 것은 그것을 처리하는 데 걸리는 시간도 적다.
2. 데이터를 디스크보다는 메모리에 두면 디스크에 접근하는 오버헤드를 피할 수 있다.

단순한 디자인

프랑스 항공기 디자이너 Antoine de Saint-Exupery는 "추가할 것이 더 이상 없을 때가 아니라 제거할 것이 없을 때, 완벽함에 도달했다는 것을 알게 된다."라고 말했다. 더 많은 프로그래머가 자신의 작업을 평가함에 있어 이 말을 기준으로 삼아야 한다. 간단한 프로그램이 복잡한 프로그램보다 더 신뢰할 수 있고, 안전하고, 견고하고, 효율적일 뿐 아니라 빌드와 유지보수를 하기 쉽다.

---

프로그래밍을 배우는 사람은 알고리즘 코스에서 많은 것을 얻을 수 있다. 새로운 문제를 푸는 데 필요한 중요한 작업과 기술을 익힐 수 있다. 나중에 나올 칼럼에서 고급 알고리즘이 개발 기간을 단축하고 실행 속도를 빠르게 하는 두 가지 모두에 있어 어떻게 소프트웨어 시스템에 영향을 미치는지 살펴볼 것이다.

이에 못지않게 중요한 것은 아로리즘은 프로그래밍의 좀 더 일반적인 수준에서 훨씬 더 중요한 영향을 끼친다는 것이다. Martin Gardner는 <Aha! Insight>에서 알고리즘의 공헌을 다음과 같이 묘사했다. "어려워 보이는 문제이지만 간단하면서도 기대하지 않았던 솔루션이 있는 경우가 있다." 알고리즘에 대해 생기는 "아하!"라는 영감은 깊은 연구를 통해서만 얻어지는 것이 아니다.

 

여기저기에서 쓰이는 이진 탐색

프로그래밍에서 이진 탐색이 가장 일반적으로 사용되는 예는, 정렬된 배열 내의 한 요소를 찾아내는 것이다. 이진 탐색 프로그램은 제대로 구현하기 어려운 것으로 유명하다. 유명하고 쉽다고 생각하지만 오류 없이 바로 구현하는 사람은 드물다.

---

짧게 해도 충분한 프로그램을 길게 작성하지 마라! 대부분의 구조가 Polya의 <How to Solve It>에 나오는 "발명가의 패러독스"의 예가 된다. "더 일반적인 문제가 풀기에도 더 쉬울 것이다." n가지 경우를 처리할 수 있는 일반적인 프로그램을 작성한 다음 n=23인 경우에 적용하는 것보다, n-23인 경우에 대해 직접 문제를 푸는 것이 더 어렵다는 뜻이다.

데이터 구조를 잘 설계하면 큰 프로그램을 작게 만들 수 있다. 잘 설계된 데이터 구조는 실행시간과 메모리 사용량을 감소시키고, 포팅과 유지보수를 쉽게 하는 등 여러 가지 긍정적인 효과를 가진다. Fred Brooks는 <Mythical Man Month>의 9장에서 메모리 사용량 절감에 대해 언급했지만, 다른 특성을 바라는 프로그래머에게도 좋은 충고가 된다.

작업을 하다 메모리가 부족해 어떻게 해야 할지 모를 때에는 코드에서 한 걸음 룰러나 불만을 가지면서 데이터를 주의 기게 살펴보는 것이 최선이다. 데이터의 표현(representation)이 프로그래밍의 본질이다.

불만을 가질 때 생각해 볼 반한 몇 가지 원리가 있다.

1. 반복되는 코드는 배열을 사용해 다시 작업해보라
2. 복잡한 구조는 캡슐화하라
3. 가능하면 최신 도구를 사용하라
4. 데이터 구조가 프로그램이 되게 하라

---

프로그래밍이라는 것에 대해 정확히 파악해 볼 필요가 있다. 코딩 기술은 정확한 프로그램을 작성하는 데 있어 작은 한 부분에 지나지 않는다. 작업의 대부분은 앞의 세 칼럼에서 다루었던 문제 정의, 알고리즘 디자인, 데이터 구조의 선택이다. 이 작업들을 잘 해낼 수 있다면, 정확한 코드의 구현은 쉬운 것이 보통이다.

 

생각보다 어려운 이진 탐색

대부분의 프로그래머는 이진 탐색의 설명만 있으면 코드를 쉽게 작성할 수 있다고 생각하지만, 실제로는 그렇지 않다. 믿게 되는 유일한 방법은 지금 바로 코드를 직접 작성해 보는 것이다.

이 문제를 직업 프로그래머 대상의 어떤 강좌에서 과제로 내보았다. 수강생들은 한두 시간을 들여 위의 설명을 각자가 선택한 언어로 표현했다. 고수준의 가상코드는 훌륭했다. 정해진 시간이 지나고 거의 모든 프로그래머들이 정확한 코드를 작성했다고 보고했다. 프로그래머들은 테스트 케이스를 가지고 30분 동안 그들의 코드를 시험했다. 여러 반에서 백 명이 넘는 프로그래머들의 코드가 조금씩 다른 결과를 보였다. 90%에 프로그래머들은 버그를 발견할 수 있었다. (나머지 10%도 버그가 없다고 단정할 수는 없다.)

그럴만한게 Knuth의 <Sorting and Searching>에서는, 이진 탐색이 처음 발표된 것은 1946년이라고 했다. 그러나 버그가 없는 최초의 이진 탐색 코드는 1962년이 되어서야 나타났다.

 

프로그램 검증의 역할

프로그래머는 코드의 정확성을 확인하기 위해 주로 테스트 케이스를 사용한다. 어떤 입력에 대해 수동으로 프로그램을 실행시켜주는 것이다. 이는 강력한 도구이지만 프로그래머가 프로그램에 대해 깊게 이해하고 있어야 한다. 그렇지 않다면 처음부터 테스트 케이스를 작성할 수도 없었을 것이다. 프로그램 검증의 주된 이점 중 하나는 이것이 프로그래머로 하여금 자신의 이해를 표현할 수 있는 언어가 된다는 것이다.

이 책의 뒷부분에서는 미묘한 프로그램을 개발하면서 검증 기법을 사용할 것이다. 코드를 작성하면서 설명을 나타내기 위해 검증 언어를 사용할텐데 특히 각 루프에 대한 불변식을 스케치하는 데 도움이 된다. 중요한 설명은 프로그램에서 단정문으로 나타난다. 어떤 단정문을 실제 소프트웨어에 포함시킬지를 결정하는 것은 오랜 경험으로만 익힐 수 있다.

검증 언어는 보통 코드가 처음 작성된 후에 코드를 살펴보면서 시작한다. 테스트하는 동안 단정문에 위배되는 일이 발생하면 버그의 위치를 알게 되며 위반의 형태를 보고 또 다른 버그를 만들지 않으면서 버그를 제거하는 방법을 알 수 있다. 디버깅은 잘못된 코드뿐만 아니라 잘못된 단정문도 고쳐야 한다. 단정문은 프로그램 유지보수에 중요하다.

---

지금까지 문제를 정확히 정의하기 위해 깊게 생각했다. 요구사항을 분명히 파악하고 알고리즘과 데이터 구조를 주의 깊게 선택했다. 프로그램 검증 기법을 통해 확신을 가질 수 있는 가상 코드를 작성했다. 이것들을 큰 시스템에 적용할 수 있을까?

스캐폴딩(scaffolding)을 만들면 기능에 쉽게 접근할 수 있다. 코드를 작성하고 스캐폴딩으로 증명한 뒤 철저한 테스트를 할 수 있다. 그다음에 실행시간에 대한 검사를 수행한다. 이런 검사 결과로 우리는 프로그램을 신뢰할 수 있게 된다.

 

테스트 장치(harness)

함수를 시험한 첫 번째 단계는 손으로 간단한 몇 가지 테스트를 해보는 것이다. 아주 작은 테스트 케이스로도 버그를 잡기에 충분한 경우가 있다. 크기가 큰 배열에 대해서는 이런 작업이 지루해지기 때문에 테스트 드라이버(driver)를 작성한다. 그런 다음에 다른 스캐폴딩을 추가해가며 프로그램을 키워나가는 것이다.

비슷한 테스트를 계속한다면 정확성에 점점 더 큰 확신을 가질 수 있겠지만 계속된 수작업 테스트에 점점 더 지겨워질 것이다. 다음 단계는 이런 작업을 자동화할 스캐폴딩을 작성하는 것이다.

작가는 큰 프로그램 깊숙이 들어있는 알고리즘을 디버그 할 때는 프로그램을 한 줄씩 실행시키면서 따라갈 수 있는 디버깅 도구를 사용한다. 그러나 스캐폴딩을 사용해 알고리즘에 대해 작업해야 하는 경우에는 print 문을 사용하는 것이 복잡한 디버거를 사용하는 것보다 더 빠르고 더 효율적이다.

 

단정문 사용 요령

함수를 스캐폴딩에서 테스트할 때나 컴포넌트 테스트를 통해 시스템 테스트로 넘어갈 때 단정문은 많은 도움이 된다. 어떤 프로젝트에서는 전처리기와 함께 assert를 정의하여 컴파일할 때 제거하여 런 타임 오버헤드를 초래하지 않기도 한다.

 

시간 측정

정확성에 확신을 가질 수 있게 되었으니 실행 시간을 확인해야 한다. 테스트 자동화한 스캐폴딩의 각 케이스의 평균 실행시간을 계산한다.

 

가장 좋은 스캐폴딩은 보통 제일 만들기 쉬운 것이다. 어떤 작업에 대해 가장 쉬운 스캐폴딩은 GUI를 포함한다. 그러나 알고리즘과 관련된 여러 작업에서는 단순한 명령행 기법이 더 쉽다.

---

어떤 프로그래머는 효율성에 너무 많은 신경을 쓴다. 사소한 최적화(optimization)에 대해 너무 일찍 걱정을 하기 때문에 지나치게 교묘해서 유지보수하기 어려운 프로그램을 만들어낸다. 반면 어떤 프로그래머는 효율성에 거의 신경 쓰지 않아 구조적으로는 멋지더라도 완전히 비효율적이라서 쓸 수가 없는 프로그램을 만드는 것으로 끝나기도 한다. 좋은 프로그래머는 컨텍스트에 적합한 효율성을 유지한다.

코드 튜닝은 기존 프로그램의 비효율적인 부분을 찾아내서 약간의 변경을 가해 속도를 개선하는 작업이다. 항상 따라야 할 올바른 접근 방법도 아니고 별로 매력적이지도 않지만 때로는 퍼포먼스에 있어 큰 차이를 만들기도 한다.

 

코드 튜닝에 대한 가장 중요한 원리는 웬만하면 하지 말아야 된다는 것이다. 다음 사항들은 코드 튜닝을 해야 할지, 말아야 할지를 결정하는 데 도움을 준다.

• 효율성의 역할
  • 미숙한 최적화는 프로그래밍에서 악의 근원이다. 효율성으로 인해 정확성, 기능성, 유지보수성 등이 희생될 수도 있다.
• 측정 도구
  • 프로파일을 통해 프로그램이 어디서 시간을 소모하고 있는지 찾아내야 한다. 대부분의 시간이 몇몇 핫 스팟(hot spot)에서 소모되고 나머지 부분의 코드는 드물게 실행된다.
• 디자인 수준
• 속도 개선이 둔화될 때
  • 개선 작업을 한 후에는 대표적인 입력값에 대해 효과를 측정해보는 것이 중요하다.

---

메모리 절약을 얘기하면 "너무 옛날 얘기잖아!"라 생각할 수 있다. 컴퓨팅 환경이 열악했던 과거에는 용량이 작은 머신에 얽매였지만 요즘은 그런 일이 사라진지 오래다. "GB대의 메모리가 흔한데, 메모리 걱정을 하는가?"가 새로운 철학이 되었다.

하지만 예나 지금이나 프로그램을 간결하게 만들기 위해 열심히 생각하는 것은 득이 될 수 있다. 어떤 경우에는 이런 생각을 하다가 프로그램을 더 단순하게 만들 수 있는 새로운 통찰을 얻기도 한다. 메모리 사용량을 줄이면 실행 시에 바람직한 부수적 효과를 얻게 되는 경우도 종종 있다. 프로그램이 작을수록 빨리 로드할 수 있고 캐시에도 더 적합하다. 다루는 데이터가 적다는 것은 데이터를 처리하는 데 필요한 시간이 적다는 의미이다. 네트워크를 통해 데이터를 전송하는 데 필요한 시간은 데이터의 크기와 직접적으로 비례한다. 메모리 칩의 가격이 저렴할지라도 메모리는 매우 중요한 것이다. 초소형 머신은 여전히 매우 적은 메모리를 갖고 있다. 대형 머신이라 할지라도 거대한 문제를 풀려면 역시 메모리에 주의해야 한다.

핵심 - 단순함

단순함은 기능성, 견고성, 속도 향상, 메모리 절약 등의 결과를 가져올 수 있다.

데이터 공간을 위한 기법

단순화가 문제를 해결하는 가장 쉬운 방법이지만, 몇몇 어려운 문제는 이것만으로는 해결되지 않는다.

1. 저장하지 말고, 다시 계산하라.
2. 희박 데이터 구조
3. 데이터 압축
4. 할당 정책

코드 공간을 위한 기법

때로는 메모리 병목이 되는 것이 데이터가 아니라 프로그램 자체의 크기일 수도 있다. 코드의 크기를 줄이는 몇 가지 일반적 방법이 있다.

1. 함수 정의
   • 흔히 나타나는 패턴을 함수로 치환하는 방법으로 단순화시키는 것을 말한다. 코드 크기도 줄고 의미도 더 명확해진다. (상향 방식 디자인의 예)
2. 인터프리터
3. 기계어로 변환

---

프로그래밍 프로세스에 있어 중요한 몇몇 단계가 있다.

발견된 문제를 이해하라

문제가 발생한 컨텍스트에 대해 사용자와 대화를 나눠라. 문제의 설명에는 종종 솔루션을 찾는 데 도움이 되는 아이디어가 있다. 다른 아이디어를 배제하면 안 된다.

추상적인 문제를 구체화하라

문제에 대한 간결하고 구체적인 설명은 처음에 문제를 푸는 데 도움이 되고, 이 솔루션이 다른 문제에 어떻게 응용될 수 있는지를 볼 때에도 보탬이 된다.

디자인 공간을 탐구하라

너무도 많은 프로그래머들은 솔루션에 너무 빠르게 도달하려 한다. 한 시간 동안 생각한 후 한 시간 동안 코드를 작성하는 것이 아니라, 일 분 동안 생각하고 하루 동안 구현한다. 비정형 고수준 언어를 사용하면 디자인 묘사에 도움이 된다. 가사아 코드는 제어의 흐름을 나타내고, 추상 데이터 구조는 중요한 데이터 구조를 표현한다.

한 솔루션을 구현하라

운이 좋은 날에는 디자인 공간을 탐색하여 어떤 프로그램이 다른 프로그램보다 훨씬 우월하다는 것을 발견하게 된다. 대부분의 경우에는 최상의 솔루션을 선택하기 위해 상위의 몇 가지를 빠르게 구현해보아야 한다. 가능한 가장 강력한 오퍼레이션을 사용해 선택한 디자인을 직관적인 코드로 구현할 수 있도록 많은 노력이 필요하다.

되돌아보라

Polya의 <How to Solve It>에서는 "항상 뭔가 할 일이 남아있다. 충분히 연구하고 깊게 파고 들면 어떤 솔루션이라도 더 향상시킬 수 있다. 그리고 어떤 경우에라도 그 솔루션을 더 잘 이해할 수 있다."고 말한다.

---

디자인 프로세스를 강조한다. 여기 프로그램를 위하나 10가지 제안이 있다.

1. 정확한 문제에 대해 작업하라
2. 솔루션의 디자인 공간을 연구하라
3. 데이터를 살펴보라
4. 봉투의 뒷면을 이용하라
5. 대칭(symmetry)을 이용하라
6. 컴포넌트를 이용하여 디자인하라
7. 프로토타입을 작성하라
8. 어쩔 수 없을 때는 트레이드오프를 해라
9. 단순함을 유지하라
10. 우아함을 추구하라