rein’s world

취미 생활로^[1] 하는 일 중에 하나가 프로젝트 오일러 라고 부르는 프로그래밍/수학 문제 웹사이트의 문제들을 푸는 것인데.

프로젝트 오일러에선,

• 2의 1000 제곱의 각 자리수 합을 구하라
• 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열 (lexicographic permutation) 중 백만번째로 나오는 것은 무엇인가
• 오일러 파이 함수 (euler phi-function)의 값이 n의 permutation인 것을 조사하라
• 다음과 같은 상황의 최단경로를 구하라

라는 식의 약간의 수학 + 알고리즘 문제들을 잔뜩 가지고 있다. 작년 초에 python에 좀 더 익숙해질 겸, 머리도 식힐 겸 — 프로그래머 스럽지아니한가 :$ – 시작했는데, 작년 말부터 좀 뜸하다가 요즘 다시 손을 대기 시작했다. Python을 사용해서 이런 문제를 풀면 얻게 되는 이익은,

• 큰 수를 쉽게 다룰 수 있다 — 기본적으로 자릿수 제한이 없는 정수를 쓸 수 있다
• list를 다루는게 매우 자연스럽다 — 기본적인 자료구조형인 list, map(dictionary)이 언어의 기본 자료형임
• OOP를 쓸 수 있다 — 유리수나 continued - fraction 같은 자주 쓰이는(…) 부분을 분리할 수 있다
• 언어 자체가 가벼운 코드로 많은 일을 할 수 있다 — 현존하는 스크립트 언어들의 특징이기도한…

인데, 사실 문제도 꽤 있다. 작년에 풀었던 문제 중에 python으로 2시간 10분 가량 돌려서 결과가 나왔던 문제가 있는데, 나중에 GMP^[2] 를 써서 해보니 1분 안쪽으로 줄어들더라고(…). 백배도 넘는 실행 시간 차이를 본 순간 -_-

이런 문제를 극복할 수 있는 — 적어도 일부 영역에서는 – 수단이 python에는 있다. 프로젝트 오일러를 주로 할 때에는 생각 못하고 있었는데, 최근 저걸 다시 생각해내고 넣어가면서 몇 개 테스트 해봤는데, 보통 4배에서 10배정도 가속되더라. 즉 전에 수 분 정도 걸린던게 수 초 ~ 수십 초 수준으로 실행속도가 빨라진 것.

바로 pysco 라는 x86 용의 파이썬 라이브러리덕분인데, 아주 간단한 코드만으로도 상당한 효율을 볼 수 있다. 예를 들어, 원래 코드의 앞 부분에 다음과 같은 부분만 들어가면된다.

import psyco
psyco.full()

…대략 이것만으로 프로젝트 오일러를 풀면서 작성했던 코드들이 수 배 향상된 속도로 동작하는 걸 확인할 수 있었다. 입사시험 문제의 일부로 사용한 문제들을 python으로 풀어보는데, 같은 코드를 C++로 작성해서 비교해봐도 8~20배 안쪽의 차이로 동작하는걸 확인할 수 있었다.^[3]

물론 psyco의 동작자체가 완전히 JIT는 아니고, 타입에 따라 별도의 특수화 코드를 생성해내는 방식이라 상당히 많은 메모리 (10~100배 정도? 내가 경험해본건 대략 10~30배) 를 사용해서 속도를 올리는 방식이라 매우 큰 코드 블럭에서는 약간 부적당할지도 모른다. 그 경우엔 위 처럼 psyco.full() 로 최적화 하는게 아니라 프로파일링 + 부분최적화^[4] 할 수 있는 수단을 제공해준다. 이건 프로젝트 오일러 문제 풀 수준의 코드에선 별로 볼 일이 없어서 잘 모르겠지만[...]

완전히 새로운 VM 구현도 아니고, 인터프리터 구현도 아닌, 그렇지만 간단히(?) 라이브러리 임포트 + 몇 줄 추가로 상당한 효율을 얻을 수 있다는 점에서 python의 매력이 점점 강해진달까 :$

간단한 프로그램을 만들 때 뭔가 어정쩡한 편리함/속도인 C#/Java를 쓸 일이 점점 더 줄어드는 기분…

1. 원래 프로그래머란건 … + 여담이지만 길드 워를 만든 아레나 넷은 취미가 프로그래밍인 사람을 채용한다더라… [↩]
2. GNU Multi-Precision Library. http://gmplib.org/ GNU LGPL로 제공되는 수학 라이브러리. 무한자리 정수 같은 것을 CPU 친화적인 명령 (SIMD같은 것들) 을 써서 고속으로 계산하게 도와준다 [↩]
3. 이건 문제 자체가 computation이 많은 알고리즘 코드라는데 기인하겠지만 [↩]
4. 어차피 코드의 20% 미만의 영역이 80%의 시간동안에 돌고, 암달의 법칙에 따라 저 부분을 우선 최적화하면… [↩]