collections.rbtree

2004년 여름쯤에 파이썬 2.4가 릴리스되기 전에 collections 모듈에
타입이 1개 밖에 없는데 이름이 복수로 붙어서, 피보나치 힙을
넣자는 얘기가 있을 때 한 3주일 고민을 해서 피보나치 힙을 구현
했었습니다. 그런데, 피보나치 힙이 워낙 괴짜스러운 자료구조라서 복잡하고
편리한 것들을 추가하기에는 영 불편해서 결국은 그냥 중단했었습니다.

올해 초에는, 피보나치힙과 비슷한 용도에 사용할 수 있지만,
바이너리 트리의 특징을 유지하고 있기 때문에, 구현이 훨씬 쉬운
레드블랙 트리를 한번 구현을 해 볼까 생각을 했었습니다. 그런데~ 훈련소
다녀오고 나니까 머리가 안 돌아가서.. 이히히 ^_^;;
결국은 한참을 벼르던 레드블랙 트리 구현을 마침 숙제하기가
너무 귀찮기도 하고 파이썬 2.5도 곧 피쳐프리즈가 되지 않을까 해서 밀어넣어보려고 한번 집중해서 구현해 봤습니다. 기본적으로
제공되는 메쏘드는

  • T.insert(v): 값을 트리에 넣음
  • T.remove(v): 값을 트리에서 뺌
  • T.clear(): 트리를 비움
  • T.has_key(k): 키가 있는지 검사
  • T.values(): 값의 리스트를 리턴
  • T.keys(): 키의 리스트를 리턴
  • T.items(): (키, 값) 페어의 리스트를 리턴
  • T.nfirst(n): 작은 값부터 순서대로 n개를 리턴
  • T.nfirstitems(n): 작은 값부터 순서대로 n개를 (키, 값) 페어의 리스트로 리턴
  • T.nlast(n): 큰 값부터 순서대로 n개를 리턴
  • T.nlastitems(n): 큰 값부터 순서대로 n개를 (키, 값) 페어의 리스트로 리턴
  • T.popleft(v): v보다 작은 값을 모두 빼내고 리스트로 리턴
  • T.popleftitems(n): v보다 작은 값을 모두 빼내서 (키, 값) 페어의 리스트로 리턴
  • T.popright(v): v보다 큰 값을 모두 빼내고 리스트로 리턴
  • T.poprightitems(n): v보다 큰 값을 모두 빼내서 (키, 값) 페어의 리스트로 리턴
  • 그 외에 __setitem__, __getitem__, __len__, __contains__ 이 지원됩니다.

아무래도 레드블랙트리나 피보나치힙류는 세션 테이블같이 정렬 순서에 따라서 빠르게 작업을 해야 하는 경우에 프리어러티 큐로 활용하는 것이 가장 대표적인 용례인데, 피보나치힙으로 구현을 한다면 순위를 뽑으려고 할 때 매번 extractmin을 해야하는 반면에, 레드블랙트리는 그냥 트리에서 돌아다니는 것으로 구할 수 있다는 것이 장점이라고 할 수 있겠습니다. (속도는 완전한 C 타입으로 구현하면 피보나치힙이 훨씬 빠르지만, 파이썬의 비교연산 특성상 파이썬 확장 모듈이 되면 별 차이가 안 납니다.)

소스는 오픈룩 trac 작업실안에도 있고, 소스포지 패치 리뷰 트래커에 Patch #1324770으로 올렸습니다. 이히히. 잘 돼서 파이썬 2.5에 들어가면 좋겠군요.

오픈소스 최고의 최적화 옵션은 -Ofun

일반적인 오픈소스 프로젝트는 아무래도 여가시간에 자발적으로 참가하는만큼 프로젝트 진행 방향에 있어서 기업 프로젝트에서와 같이 “데드라인 엄수”, “최저 생산가”, “최고의 속도”, “가장 완벽한 인터페이스”가 아니라, 그저 “개발자의 재미”가 최고의 가치로 작용합니다. 완벽한 UI를 만들면 재미있는 개발자들은 완벽한 UI를 만들고, 표준을 완벽하게 엄수하는 것으로 재미를 느끼는 개발자들은 표준을 어기는 코드가 있으면 길이길이 날뛰면서 표준에 맞게 고쳐서 패치를 내겠지요. (토끼군처럼 남이 못 알아보도록 짜는 것에 재미를 느낄 수도 있고.. =3=3) 재미가 오픈소스 프로젝트의 가장 큰 요소인 것은 너무나 당연함에도 불구하고, 그동안 정부의 오픈소스 정책이나, 오픈소스를 추종하는 사용자들, 체계적인 체제를 갖추지 않은 오픈소스 프로젝트 들에서는 많이 간과되어 왔습니다.

최근 《재미와 소프트웨어 개발》이라는 논문이 나왔습니다. 이 논문에서는 주로 오픈소스 프로젝트들을 예를 들어서, 개발자들에게 개발의 재미를 주는 요소들과, 프로젝트 생산성, 창의성의 관계에 대해서 살펴보고 있습니다. 작업의 명료성, 재미, 충동, 주의, 집중 등이 프로젝트 결과에 영향을 주는 요소로 재미있게 분석되어 있습니다. 🙂

Haskell로 구현된 Perl6 프로젝트인 pugs 개발자가 쓴 O’Reilly 기사에서 얘기하고 있는 pugs의 -Ofun 성공 비결은 이렇게 요약하고 있습니다. (각 조건의 설명은 원문을 참조하세요.)

  • -Ofun을 프로젝트 최우선 최적화 조건으로 삼아라.
  • 현대적인 분산형 버전 컨트롤 시스템을 사용하라.
  • 커밋이 허용되는 개발자들을 최대한 늘리고 커밋을 쉽게 하는 무정부주의를 지향하라.
  • 빌드가 깨지거나 개발을 방해하는 데드락을 피하라.
  • 커미터 권한을 많은 다양한 사람들에게 주어라.
  • 돌아가는 코드가 아이디어보다 낫다.
  • 끈끈하고 도움을 주는 개발자 커뮤니티를 만들자. (예: 신규 개발자들에게 멘터링을 해주는 방식)
  • 흥미와 배움은 전염된다.

기업이 투자하는 것이 아니라면, 오픈소스 프로젝트가 성공하기 위해서는 리더들은 무엇이 개발자들에게 개발 동기를 유발하는가를 고려하여 그 점들을 자극할 수 있는 무언가를 충분히 재공해 줘야할 듯 합니다. 주변의 예만 보더라도, FreeBSD의 버그 트래킹 시스템인 GNATS는 웹에서 접근할 수 있는 개발자 리소스가 제한되어 있기에, 버그 트래킹 시스템에 접근하려면 ssh로 중앙 서버에 접속해야하고, 그 과정이 미미하지만 동기 요소를 떨어뜨리는 요소로 작용하게 마련입니다. 그래서 FreeBSD 버그 트래킹 시스템에서는 유난히 오래된 버그들이 많고 개발자들이 할당만 해놓고 거들떠보지도 않는 경우가 많습니다. 또한, 코드를 직접 커밋해서 다른 사람들이 리뷰할 수 있는 경우와, 최근 CVS로 업데이트한 다음에, diff를 떠서, 복잡하게 버그 트래킹 시스템에 올린 다음에, 커미터에게 리뷰를 받아서 다시 또 설명을 한 다음에 결국 한참 있다가 커밋되는 것과는 피드백의 시간에 있어서 동기 유발에 큰 차이를 보이겠지요.

그나저나, 저 오라일리 글의 “bus error” 표현은 아주 재미있군요. 이히히히~

Worse yet, a “bus error” (a key person being hit by a bus) may stall the project for good.

FreeBSD시 세미나 자료

10월 29일에 개최될 예정인 Hello FreeBSD 세미나에서 발표할 자료를 만들었습니다.
웹에 떠돌아다니는 여러 프리젠테이션들과 머리 속에 흩어져 있는
정보를 참고로 하여 극히 일부만~ 으흐흐



발표 자료 다운로드 (pdf 포맷)

제가 주최하는 행사가 아니라, 구체적으로 어떤 형식으로 진행될 지는 잘 모르겠지만, FreeBSD관련 행사가 정말 오랜만에 있는 것이니만큼 FreeBSD에 관심 있는 분들이 많이 오셨으면 좋겠습니다.
그동안 많은 행사가 개발자 중심의 세미나였던 반면에 이 세미나는 내용을 봐서는 SE들을 위한 행사인 것 같네요~

학생으로 변신하기 위한 물품들

학생이 되니까 들고다녀야하는 장비의 종류가 꽤 다르군요. 흐흐. 이제 슬슬 중도에 하루 종일 있어도 그다지 불편하지 않은 단계가 되었습니다. 아하하;;

계산기
예전에 EL-5120을 썼었는데, 물리랑 화학 외에는 앞으로 쓸 일없겠지 하고 누구 빌려준 다음에 누구한테 빌려줬는지 까먹어서 결국은 새로 샀습니다. -.-; 옛날보다 가격이 많이 내렸군요.. 한동안 계산기가 없어서 전화기로 rath님의 hanirc 프로그램을 띄워가지고 IRC에 들어가서 IRC봇한테 파이썬 명령을 내려서 계산했었는데, 하나 계산하려면 2~3분씩 타이핑하느라 고생;; 그래서 결국은 큰맘먹고 새로 계산기를.. 흑흑. log랑 실수 제곱만 제공되면 전자사전에 들어있는 계산기 써도 되는데 아쉽네용.

타이머
저는 시간을 무척 비효율적으로 쓰는데, 막 뭔가 하나 잡으면 딴짓하느라 시간가는지도 모르고 2~3시간이 훌쩍 흘러버립니다. 으흐흐.. 그래서, 이번 학기는 꼭 멋지게 시간을 보내 보고자 승범이가 쓰던 타이머와 같은 모델을 사서, 뭘 해도 시간을 정해놓고 하고 있습니다. 아하하. 특히 제일 좋을 때는 10분만 자야지 하고 타이머를 쥐고 자고 있으면 아주 -.-b _-_ 그리고 공부에 너무 빠져 들어서 밥먹는 것 잊어버리는 상황을 피할 때도 좋습니다. (괜히 걱정해 본다;;;;)

전자사전
흐흐 모르는 단어가 왜 이리 많은지.. 벌써 단어장에 단어가 100개를 넘었습니다. 흑. 단어장 기능 정말 좋군요. 🙂 전자사전에 공학용계산기 기능이 없다는게 가장 아쉽군요. 넣을 만도 한데 계산기 팔려고 안 넣었나…

FreeBSD 홈페이지가 바뀌었어요

Google Summer of Code 프로젝트 중의 하나였던 FreeBSD 웹 사이트 프로젝트가 거의 완료되어서, 실제 사이트로 올라왔군요.

뭔가 개발자들만 바글바글한 해키시하던 이미지에서 회사같은 이미지로 바뀌게 되어서 나름대로 경영진들한테는 신뢰감을 줄 것 같기도 하네요. 으흐흐~ 초기화면에서 두번 클릭만에 ISO 파일을 다운로드 받을 수 있다는 점도 실행차를 줄였다는 점에서 매우 큰 발전이라고 생각됩니다. -O- (수업시간에 배운 말을 써먹어 본다 =3=3)

FreeBSD 로고는 거의 막바지에 다다랐는데, 로고 후보로 나온게 “”모두 다 맘에 안 든다 원래대로 가자!”라고 주장하는 사람들이 대거 등장해서 과연 어떻게 될 지 모르겠군요.. 으흐;;

포트 메인테이너의 게으름은 끝이 없다

다른 OS들은 대체로 “게으른 사람들을 위한 OS”라고 표명하면서
그냥 놔두고 가끔 엔터만 쳐주면 된다는 것을 자랑으로 합니다.
그런데, FreeBSD는 아무래도 “게으른 사람들에 의한 OS”라서,
FreeBSD 개발자들의 편의를 위한 것이 대체로 사용자 편의성보다
우선하는 분위기 입니다. 므흐흐. 🙂 흔하지 않은 특징이라는
것이 아주 맘에 듭니다. =3=3

그러다가 이제는 포트 메인테이너들이 새 버전 나왔는지
가끔 홈페이지 들어가 보는 것조차 귀찮아져서, 직접 안 가고도
새 버전이 나오면 포트 메인테이너에게 알려주는 서비스가
시작되었습니다. edwin@이 만든 이 스크립트는, 기록된
웹 사이트와 배포 ftp 목록, http URL 추측 등의 온갖
주먹구구식 방법을 동원해서 새로운 버전이 나왔는지 체크를
합니다. 결과는 메일로 통보되지만, 웹으로도 확인할 수 있습니다.

예를 들면, 제 포트 중에 새 버전이 나온 것은 여기를 보면 확인할 수 있는데, 지금 23개가 아웃데이트돼서
아웃데이트 순위로 5위를 먹었습니다. –; 그런데, 파이썬 포트들 중에 슬레이브 포트로 돼서 버전이 안 올라간 것들이 있어서 상당히 억울합니다. 우워우워!

다른 패키지 시스템 개발자들도 이것 응용해서 도입하면 유용하겠군요..

거울 속으로 들어가면 더 이상 우유를 마시지 못할지도 몰라

“How would you like to live in Looking-glass House, Kitty? I
wonder if they’d give you milk in there? Perhaps Looking-glass milk
isn’t good to drink..”
“야옹아, 거울 집 안에 사는 건 어때? 거기서도 우유를 주니? 거울 속에서는 우유는 마실 수 없는 것일지도 몰라..”

거울 나라의 앨리스 Through the Looking Glass – Lewis Carol

연휴 내내 숙제만 하다가, 막판에 하고 있는 생화학 숙제.. 가르쳐주지도 않은 lactic acid(젖산)의 optical activity에 대한 문제가 나왔는데, 아무리 봐도 무슨 얘긴지 몰라서 웹을 찾다보니 젖산의 optical activity에 대해서 저런 얘기가 있군요;; 젖산이 chiral molecule이라서 거울에 뒤집으면 lactase가 소화를 못하기 때문에 우유를 못 마신다는.. -O-

아흑흑. 생화학 챕터 1은 가르쳐 주지도 않은 내용만 잔뜩 나와서 한 문제 푸는데 구글을 30분씩 찾아봐야 하는 것일까.. ㅠ.ㅠ 역시 구글의 도움을 받아서 숙제하기에는 그래도 컴퓨터과학 과목들이 훨씬 낫군요…