'전체 글'에 해당되는 글 215건

  1. 2011.03.25 Compiling openmotiff 2.3.3 on OSX
  2. 2011.03.25 memo: gcc option - stop right after preprocessing stage
  3. 2011.03.14 linux 에서 apple aluminum keyboard 의 F13-F19 인식시키기
  4. 2011.03.09 축소 지향의 일본인 / 이어령
  5. 2010.11.27 애니메이션 비망록 (+추천) - 3
  6. 2010.11.03 카메라 용어 정리 - f 값 (f-number), f-stop 5
  7. 2010.10.07 timsort
  8. 2010.09.11 google instant search 끄기 2

Compiling openmotiff 2.3.3 on OSX

Computing 2011. 3. 25. 01:26

My environment:

orchistro.deltabellun:~$ uname -a
Darwin deltabellun.local 10.6.0 Darwin Kernel Version 10.6.0: Wed Nov 10 18:13:17 PST 2010; root:xnu-1504.9.26~3/RELEASE_I386 i386

Configuring:

./configure --prefix=/usr/X11 --with-x-includes=/usr/X11/include --with-x-libraries=/usr/X11/lib --with-freetype-config=/usr/X11/bin/freetype-config CC='gcc -I/usr/X11/include -I/usr/X11/include/freetype2' LDFLAGS=-L/usr/X11/lib

After it gives out this error message when compiling:

UilLexAna.c:1488: error: request for member 'value' in something not a structure or union

You need to make a little bit of modification in clients/uil/uilDefI.h:286:

#if defined(linux)
--->
#if defined(linux) || defined(__APPLE__)

A.....n........d you're OK to continue building openmotiff. Enjoy it.

:

memo: gcc option - stop right after preprocessing stage

Computing 2011. 3. 25. 01:04

If gcc is given "-E" option, it stops after preprocessing stage. Its output will be like following:

orchistro.deltabellun:~/work/iso-2022-jp$ cat a.c
#include <stdio.h>

int main(void)
{
    printf("%c%c%c%c%c", 0x1b, 0x24, 0x42, 0x30, 0x21); /* nihongo kanji */
    printf("%c%c%c%c%c", 0x1b, 0x24, 0x42, 0x2d, 0x21); /* circled 1 */
    printf("%c%c%c\n", 0x1b, 0x28, 0x42); /* ascii */

    return 0;
}
orchistro.deltabellun:~/work/iso-2022-jp$ gcc -E a.c | head -30
# 1 "a.c"
# 1 "<built-in>"
# 1 "<command-line>"
# 1 "a.c"
# 1 "/usr/include/stdio.h" 1 3 4
# 64 "/usr/include/stdio.h" 3 4
# 1 "/usr/include/_types.h" 1 3 4
# 27 "/usr/include/_types.h" 3 4
# 1 "/usr/include/sys/_types.h" 1 3 4
# 32 "/usr/include/sys/_types.h" 3 4
# 1 "/usr/include/sys/cdefs.h" 1 3 4
# 33 "/usr/include/sys/_types.h" 2 3 4
# 1 "/usr/include/machine/_types.h" 1 3 4
# 34 "/usr/include/machine/_types.h" 3 4
# 1 "/usr/include/i386/_types.h" 1 3 4
# 37 "/usr/include/i386/_types.h" 3 4
typedef signed char __int8_t;



typedef unsigned char __uint8_t;
typedef short __int16_t;
typedef unsigned short __uint16_t;
typedef int __int32_t;
typedef unsigned int __uint32_t;
typedef long long __int64_t;
typedef unsigned long long __uint64_t;

typedef long __darwin_intptr_t;
typedef unsigned int __darwin_natural_t;
orchistro.deltabellun:~/work/iso-2022-jp$ gcc -E a.c | tail -30


extern int __snprintf_chk (char * , size_t, int, size_t,
      const char * , ...)
  ;




extern int __vsprintf_chk (char * , int, size_t,
      const char * , va_list)
  ;




extern int __vsnprintf_chk (char * , size_t, int, size_t,
       const char * , va_list)
  ;
# 444 "/usr/include/stdio.h" 2 3 4
# 2 "a.c" 2

int main(void)
{
    printf("%c%c%c%c%c", 0x1b, 0x24, 0x42, 0x30, 0x21);
    printf("%c%c%c%c%c", 0x1b, 0x24, 0x42, 0x2d, 0x21);
    printf("%c%c%c\n", 0x1b, 0x28, 0x42);

    return 0;
}
orchistro.deltabellun:~/work/iso-2022-jp$

:

linux 에서 apple aluminum keyboard 의 F13-F19 인식시키기

Computing 2011. 3. 14. 23:57
Linux's compiz is a quite good program. It provides linux desktop users with various fancy effects that will mesmerize your eyes and make you feel great. However, if you have Apple's aluminum keyboard with numpad version, you might have found that your compiz configuration program does not recognize your function keys F13 through F19. It's because xorg of ubuntu desktop does not map those keys to meaningful symbols. It just maps them as XF86blablabla, and it does not work for your compiz cofiguration program.

Here, I am going to show you how to make your ubuntu machine to recognize F13 through F19 of Apple's aluminnm keyboard.

First of all, you need to find out key codes of F13 to F19 using 'xev'.

Secondly, you'll need 'xmodmap' to map each of function keys to an appropriate symbol.

For example, the keycode of F15 key is 193. It is not assigned to a meaningful symbol. So you are going to map it by typing in following command in your terminal:

xmodmap -e 'keycode 193 = F15'

You'll need to do the same thing for F13, F14, F16, ... , F19.

It would be great inconvenience if you had to do this every time you log on to your ubuntu machine.

Fortunately, you can save your xmodmap configuration in .Xmodmap file in your home directory and your ubuntu machine will load the file when you log on to your computer.

For folks who are not willing to bother finding out key codes of all function keys, here goes my .Xmodmap file:

keycode 191 = F13
keycode 192 = F14
keycode 193 = F15
keycode 194 = F16
keycode 195 = F17
keycode 196 = F18
keycode 197 = F19

Have fun with your apple aluminum keyboard!

----

xev 를 이용해서 F13-F19 의 키코드를 알아낸다.

man xmodmap 을 해서 xmodmap 의 사용법을 알아낸다.

적절한 symbol 로 매핑시켜 준다.

예제) xmodmap -e 'keycode 193 = F15'

매번 설정하기 귀찮으면 ${HOME}/.Xmodmap 에 적어 둔다.

내 .Xmodmap 파일:

keycode 191 = F13
keycode 192 = F14
keycode 193 = F15
keycode 194 = F16
keycode 195 = F17
keycode 196 = F18
keycode 197 = F19

관련 포스팅 : http://orchistro.tistory.com/72


:

축소 지향의 일본인 / 이어령

Books 2011. 3. 9. 00:22

내가 처음으로 세간에서 이야기하는 '일본론' 이라는 류의 서적을 읽은 것은 군대에서 읽었던 '나는 일본 문화가 좋다' 이다. 당시 갓 인터넷이 널리 퍼지고 있었으며, 암암리에 어둠의 경로로 어렵게 구한 일본 애니메이션의 동영상을 보고서 한참 일본 문화에 대한 관심이 새록새록 피어나던 시기였던지라 그럭저럭 재미있게 읽어 내려갔던 기억은 있지만, 정작 지금은 그 내용이 기억나지 않는다. 지금도 내 책장 한구석에 있을 터이지만, 다시 빼 내어 읽을 생각은 없다.

그 다음 읽었던 일본 관련 서적은 전여옥이 쓴 '일본은 없다' 이다. 이 역시 지금은 그 내용이 거의 기억나지 않지만, 일본을 폄하하는 내용이 주를 이루었던 것 같다. 읽으면서도, '이 사람, 무슨 일본에 열등의식 같은 게 있나' 하는 생각이 들 정도였는데, 거기 더해서 그 당시에도 그랬지만 지금도 여전히 싫어하고 있는 '애국'과 '국수주의', '민족주의'에 호소하는 근거 빈약한 주장까지 더해져 상당히 좋지 않은 인상을 받았었다.

'일본은 없다'를 읽고서 느낀 실망 때문에, 그 이후로 줄줄이 쏟아져 나온 '일본은 있다', '일본은 있다 없다를 넘어서' 와 같이 무슨 어린아이들 말장난 하듯 이어지는 시리즈의 책들을 한권도 읽지 않았다. 그 책들도 모두 초라한 민족주의와 피해의식에 호소하는 영양가 없는 내용에 불과하리라 섣불리 짐작해 버렸기 때문이다. 일본 관련 서적에 편견이 생겨버린 것이다.

그리고 거의 10년이 지난 2010년, 읽을 거리를 찾아서 이리저리 둘러보던 나는 의외로 이어령 교수의 1982년의 저작물에 눈이 가게 된다.


'축소 지향의 일본인' ---> 네24 링크


원제 「縮み」志向の日本人 ---> 일본 아마존 링크
참조 : 이어령 교수에 대한 일본어 위키피디아 : http://ja.wikipedia.org/wiki/%E6%9D%8E%E5%BE%A1%E5%AF%A7
책의 표지 사진은 각각 yes24, amazon 에서 가져온 것임.


우선, 저자가 전여옥씨는 감히 명함도 들이밀지 못할 이어령교수라는 점, 일본에서 먼저 출판되고, 영역, 불역이 되었다는 점, 그리고 최근 일본어를 좀 배워서 일본에 대한 흥미가 많이 부풀어 올라 있었다는 점에서 책을 주문하였다.


대학시절에야 책을 한권 잡으면 다 읽을 때 까지 손에서 놓지 않았었는데, 먹고 사는 일에 바쁜 요즘은 한권을 잡고 한달이고 두달이고 띄엄띄엄 보는 경우가 대부분이다.

그러나 이 책은 달랐다. 저녁 먹을 무렵에 책을 읽기 시작해서, 다 읽고 보니 동틀녘이었다.


우선, 저자의 시각이 무엇보다도 마음에 들었다. 감정에 치우치지 않고 객관적인 입장에서 글을 써 내려가고 있다.

또한, 일본 사회의 집단 무의식이라고나 할까, 일본인의 대개의 경향이라고나 할까, 아무튼 그러한 특징들을 '일본어'에서 찾았다는 점이 또한 마음에 들었다. 언어와 생활은 뗄래야 뗄 수 없는 관계이다. 언어가 사고를 지배하고, 사고는 또 언어를 지배하고, 언어에 지배당하는 사고는 개개인의 행동방식, 대인관계, 집단생활 등, 사람들의 삶에 영향을 미친다. '언어'라는 것이 얼마나 사람의 생활에 큰 영향을 미치는가 하면, .... 내 능력으로는 도저히 설명을 하지 못하겠다. 19세기에서 20세기 초엽의 구조주의 철학(언어학)에서부터 비트겐슈타인까지의 철학사의 개요만 읽어 보아도 언어와 인간 삶의 관계에 대해 내가 어떤 생각을 가지고 있는지 어느정도 이해할 수 있을 터이니 '말'과 '인간사'의 관계는 그에 관련된 책을 읽어 보라는 말로 대충 얼버무리겠다.

아무튼, 이어령 교수는 '일본어' 에서 일본인의 대개의 사고 방식과, 일본 사회의 모습, 일본 경제의 흥과 망(?), 일본 문화의 전반에 걸쳐 나타나는 공통점 (위대한 지성들은 어디서든 공통점, 유사점을 찾으려고 한다는 말을 어디선가 읽거나 들었다) 에 대해 하나씩 이야기를 풀어 나간다.

이 책을 21세기 초에 전여옥이 쓴 '일본은 업ㅂ다'와 비슷한 시기에 읽었다면, 지금처럼 재미있게 느끼진 못하였을 것이다. 하지만 공교롭게도 나는 지금 일본어를 어느 정도는 할 줄 알며 (JLPT N1 정도는 될 터), 수많은 일본 드라마, 애니메, TV 방송 및 직접 상당한 시간동안 대면하고 지냈던 일본인을 통해 일본에 대한 나름의 기초 지식을 가지고 있는 상황이다. 이러한 상황에서 이 책을 읽으니 '아하, 그러고 보니 정말 그렇구나!' 라며 무릎을 치며 책을 읽어 내려갈 수 밖에 없다.


물론, 이어령 교수가 자신의 주장을 뒷받침하기 위해 예시한 모든 것들에 동의하는 것은 아니다. 때로는 언어의 단면만 보고서 섣불리 판단했다는 생각이 드는 부분도 보이고, 근거로 제시한 자료 또한 조사가 불충분한 부분이 눈에 띄기도 했다.

그럼에도 불구하고, 어떤 집단의 사람들에 대한 일반론을 펼치기 위해 잡은 출발점이 바로, 그 집단이 사용하는 '말'이라는 점. '말'에서 출발하여 '말'에만 한정되어 끝나는 것이 아니라 사회의 여러 부분에까지 논리를 펼쳐 나갔다는 점에서 나는 이 책이 아주 좋다. 즐겁게 읽었다는 말이다.


다음에 읽을 책도 이어령 교수의 책으로 해야 겠다. 벼르고 벼르다 아직도 구입하지 않았던 '한국인의 신화' 로 해 볼까.


----

아 참, 졸렬한 내 짤막한 이 글을 보고서 이 책을 읽어 보려는 생각이 든 분들은 주의하시기 바란다. 일본어에 대한 지식이 있고 없고에 따라 이 책의 재미는 두 배 이상으로 차이가 난다. 내가 일본어를 잘한다고 젠체하는 것이 아니다. 물론 한국어판으로 2002년에 옮겨 적으면서 일본어를 모르는 사람이 읽어도 좋게끔 신경을 많이 쓴 것이 보이지만, 그래도 어쩔 수 없는 부분이 많이 보였다. 일단, 이 사실을 염두에 두고서 독서를 시작할 것을 일러두겠다.


:

애니메이션 비망록 (+추천) - 3

아니메, 드라마 2010. 11. 27. 00:22

애니메이션 비망록 - 1

애니메이션 비망록 - 2


추천할 만한 애니메

  1. 이브의 시간 (イブの時間)


    로봇이 나오는 미래의 이야기이다. 진부한 소재이다. 그렇지만 역으로 생각해 보면, 재미있기 때문에 많이 사용된 소재이고, 그렇기 때문에 진부하게 느껴지는 것이 아닌가 한다.
    흔한 소재이지만, 이야기의 전개가 재미있는 편이다.

  2. RD 잠뇌 조사실 (RD潜脳調査室)
    나노 로봇이 일반화 된 근미래 (과연 근미래일까? 초등학교때 공상과학 만화 등을 보면 2020년에는 자동차가 날아다니고 있었는데...) 의 이야기이다.
    초반에 이야기가 진행되는 세계에 대한 설명에 너무 많은 시간을 들여서 지루한 면이 있다.
    후반부의 극의 긴장감과 재미는 꽤 좋은 편이다.

  3. 키노의 여행 (キノの旅)
    우화집같은 내용이다.
    사람에 따라 좋아하는 내용일 수도 있으나, 너무 뻔해서 좋아하지 않는 내용일 수도 있다.
    이같은 옴니버스식 만화는 몰아서 보는 게 아니라 방영할 때 한편씩 봐야 한다.

  4. 냥코이 (にゃんこい!)


    이 애니메는 할렘물이다. 즉, 남자 주인공과 그 남자 주인공을 좋아하는 다수의 여성 조연들이 출연하는 애니메이다.
    일반적으로 할렘물 애니메는 그다지 재미있지 않다. 스토리 라인이 설득력이 없다. 주인공의 인물상이 답답하다.
    그렇지만, 냥코이는 할렘물 애니메의 일반적인 마이너스 요인을 가지고 있지 않다.
    아주 잘 만들어진 스토리라인으로 인해 재미있게 시청하였다.
    아쉬운 점은, 마지막에 결론이 나지 않는다는... 헉, 스포일러인데...

  5. 톱을 노려라2! (トップをねらえ2!)
    앞편 시리즈인 톱을 노려라 1! 을 보지 않았더라도, 충분히 즐길 수 있다. 아니, 전편과는 전혀 관계 없는 애니메이다.
    일단, 그렌라칸같은 열혈물인데, 알고 봤더니 이것도 가이낙스 제작이었다. 가이낙스의 '열혈물' 스타일이 어느정도 짐작이 되긴 하는데, 그다지 마음에 들지 않는 스타일이다.
    그럼에도 불구하고, 그리 길지 않은 시리즈이기 때문에 가볍게 잠시동안 즐길 수 있는 애니메.

  6. 방랑소년
  7. 마법소녀 마도카 마기카
  8. 그날 본 꽃의 이름을 우리는 아직 모른다.
  9. 바쿠만 - 2기 기대중.
  10. 유루유리 - 2011-08월, 6화부터 본격적으로 재미있어지기 시작했다.
  11. 토끼 드롭스
  12. 모리타씨는 과묵




그다지 추천하고 싶지 않은 애니메

  1. 레이디 X 버틀러 (れでぃXばと)
    이녀석도 할렘물인데, 성인용 등급이다.
    등급과는 별개로, 등장 인물들이 아무 이유도 없이 주인공 남자에게 연모의 정을 느끼게 된다.
    감정이입이 매우 어려우며, 이야기에 원인과 결과가 나타나지 않는다.
    노출이 보고 싶은 사람이라면 한번쯤 볼 만 하다.


:

카메라 용어 정리 - f 값 (f-number), f-stop

사진기 2010. 11. 3. 01:28

최초 작성 : 2010. 06. 01
오류 정정 및 내용 업데이트 : 2010. 11. 3


흔히들 카메라의 렌즈에 대해 이야기할 때 무심코 'f 값이 작아서 밝은 렌즈라' 어쩌고 저쩌고 이렇게 이야기하는 모습을 볼 수 있다. 이러저러한 사진 블로그 등을 뒤져 보면 f 값이 작을 수록 조리개가 많이 개방된다는 것, 초보들이 "동경"하는 사진인 아웃포커스된 사진을 찍기 용이해진다는 것 등을 알 수 있다. 그런데, 정작 왜 f 값과 조리개의 개방 정도는 반비례하는 것인지를 물어보면, 주변의 지인들도 그렇고, 누구 하나 정확하게 대답해 주는 사람이 없다. 도대체 f 값이 무엇이길래?


f number ?

요즘은 세상의 웬만한 지식은 전부 위키피디아에 있는 것 같다. 물론, 한국어 위키피디아의 이야기가 아니라 영어 위키피디아이다. 위키피디아를 뒤져 보도록 하자.

http://en.wikipedia.org/wiki/F_number

영어를 읽는 데에 부담이 없는 분들은 그냥 위의 위키피디아 페이지를 읽으시는 편이 내가 어설프게 정리한 이 포스팅을 읽는 것 보다 훨씬 나으니, 위의 링크를 이용하도록 하시라.

우선, f 값 N 의 정의는 아래와 같다 :

N = f / D

여기서, f 는 렌즈의 focal length, 즉, 초점 거리이며, D 는 조리개가 개방되었을 때의 개방부의 지름, 즉, Aperture 의 지름이다. (이하 Aperture 의 직경으로 통일)

이해를 쉽게 하기 위해서, 상황을 단렌즈의 경우로 단순화시켜 보자. 단렌즈 (초점 거리가 고정되어 있는 렌즈) 의 초점 거리는 고정되어 있다. 변하지 않는 값이다. 따라서 위의 식에서 f 를 그냥 20 으로 대체시켜 버리자. (내 카메라에 장착된 렌즈가 20mm 단렌즈이기 때문에 정한 상수) 그러면, 위의 식은 아래와 같이 된다 :

N = 20 / D

이렇게 써 놓고 보니, 중학교 때 배운 함수의 그래프가 생각난다. 심심한데 그래프나 한번 그려 보자.

gnuplot> plot [x=0:46] [0:20] 20/x


위에서 눈으로 쉽게 확인할 수 있듯이 Aperture 의 직경이 증가함에 따라 f 값이 작아진다. 바꾸어 말하면, f 값이 작아짐에 따라 조리개가 많이 개방된다고도 이야기할 수 있다.

그렇다. f 값 자체가 저렇게 생겨 먹은 것이니, 조리개의 개방 정도와 반비례하는 것이 당연하다.


그러면, f 값이 가지는 의미는 무엇인지 슬슬 궁금해지기 시작한다. 도대체 이 f 값을 어떻게 해석해야 할 것인가? 이 값의 의미는 쉽게 생각해서, 렌즈에 입사되어서 촬상 소자에 도달하는 광자의 갯수의 역수라고 생각하면 된다. 역수가 나오니 갑자기 어려워지는데, 좀 더 쉬운 예를 들어 보자.

f 값이 같은 두 개의 렌즈는 렌즈의 초점 거리와 Aperture 직경이 다르더라도 동일한 양의 빛이 광자가 촬상 소자에 도달한다는 뜻이다. 즉, 동일한 "밝기" 로 상이 맺힌다.

예를 들어서, 초점 거리 100mm 인 렌즈와 135mm 인 렌즈가 있다고 가정하자.
그런데, 이 두 렌즈 모두 f 값이 4 가 되도록 조정해 두었다.
즉, 100mm 렌즈는 Aperture Diameter 가 25mm (4 = 100 / 25),
135mm 렌즈는 Aperture Diameter 가 33.8mm (4 = 135 / 33.8) 에서 4 의 f 값을 가진다.

그리기 힘드니 위키피디아의 그림을 인용하도록 하겠다 :


위 그림은, 동일한 f 값으로 세팅한 두 개의 렌즈가 상이 맺히는 부분에 동일한 광량을 입사시키는 모습을 표현했다.

33.8mm 만큼 조리개가 열려 있으면 25mm 에 비해서 더 많은 광자가 입사되겠지만, 그만큼 초점 거리가 길기 때문에 촬상 소자까지 도달하는 광자는 적어진다라고 이해하면 되겠다.

즉, f 값은 촬상소자에 도달하는 광자의 양을 나타내는 값 혹은, 촬영되는 상의 "밝기" 라고 그냥 생각해도 무방하다.


일반적으로 f 값을 조리개 개방시 개방된 부분의 크기를 나타내는 값이라고 근사화시켜서들 이야기하곤 한다. 100% 틀린 말이라고는 할 수 없지만, 100% 맞는 말이라고도 할 수 없다. 왜냐하면 위의 그림에서 보듯이 렌즈의 초점 거리가 다르면 같은 f 값을 세팅한다 해도 조리개 개방시의 직경이 다르기 때문이다.


그렇다면, 실제 사진을 찍을 때 f 값을 조정하는 것에는 어떤 의미가 있는지 생각해 보자.

f 값을 변경시키면 (모든 설명은 단렌즈 기준으로 한다, 즉, 초점 거리는 상수임) 조리개가 열리는 정도가 달라지므로 촬상 소자에 도달하는 광자의 갯수가 (반비례로) 변화한다.

예를 들어 보자. 아주 어두운 공간에서 잔상이 남지 않도록 사진을 찍고싶다고 가정해 보자. 잔상이 남지 않으려면 셔터 스피드를 짧게 해 주어야 한다는 것 쯤은 다들 알고 있으리라 생각한다. 그런데, 셔터 개방 시간을 짧게 하면 렌즈에 들어오는 빛의 양이 적어져서 아주 어둡게 사진이 찍힐 것이다. 뭘 찍었는지 알아보기 힘들수도 있다. 피사체를 알아볼 수 있는 정도의 밝기로, 잔상이 남지 않게끔 짧은 셔터 스피드로 사진을 찍기 위해서는 어떻게 하면 될까, 플래시를 터뜨리지 않는다면, 렌즈에 들어오는 빛의 양을 많게끔 하려면, 조리개를 많이 열 수 밖에 없다. 따라서, f 값을 낮추어서, 즉, 조리개를 많이 개방해서 짧은 조리개 개방 시간에도 최대한 많은 양의 빛을 받아 들여서 "밝게" 나오게끔 하면 된다.


f-stop ?

렌즈의 조리개는 여러장의 날개로 이루어져 있다. 이 날개들이 열리는 정도는 미리 계산되어서 조정되어 있다. 또한 이 개방 정도는 연속적인 값이 아니라 불연속적인 값이다. 이 불연속적인 값들의 하나 하나를 stop 이라고 일반적으로 부른다. 조리개의 stop 들은 각각 다음 stop 이 현재 stop 보다 정확하게 조리개의 면적이 두 배가 되도록 조절되어 있다.

국민학교 산수 시간에 배웠던 원의 넓이를 구하는 공식을 상기해 보도록 하자.

S = π r 2

위 식을 이용해서 면적이 두 배가 되는 원의 반지름 r' 을 구하면,


그런데, S 는 π r 2 이므로,


면적이 두 배가 되면, 단위 시간당 통과하는 빛의 양 (광자의 갯수) 도 두 배가 된다.

즉, 직경이 √2 배 만큼 커지면, 빛의 양은 두 배가 되고, 직경이 √2 배 만큼 줄어들면 빛의 양은 절반이 된다.

렌즈의 조리개는 처음에 이야기했듯이, 각 stop 들이 인접한 바로 앞의 stop 에 비해 빛의 양이 두 배가 되도록 미리 조절되어 있다. 단렌즈의 경우, 초점 거리가 고정되어 있으므로, 위 결과를 f 값의 계산에 대입해 보자.

N = f / D, f 는 focal length, 단렌즈의 경우, 상수임.
만약 D = f 이면, f 값은 1 이 된다.
그 다음 값으로, 단위 시간에 조리개를 통과하는 빛의 양이 절반이 되는 직경은 f / √2 가 되며,
이 때, f 값 N = f / D = f / (f / √2) = √2 ~= 1.414
그 다음 값으로, 단위 시간에 조리개를 통과하는 빛의 양이 1/4가 되는 직경은 f / (√2)2 가 되며,
이 때, f 값 N = f / D = f / (f / (√2)2) = (√2)2 = 2
그 다음 값으로, 단위 시간에 조리개를 통과하는 빛의 양이 1/8가 되는 직경은 f / (√2)3 가 되며,
이 때, f 값 N = f / D = f / (f / (√2)3) = (√2)3 ~= 2 * 1.414 = 2.828
.
.
.

빛의 양이 절반씩 감소해 가는 직경들을 나열하면 아래와 같다 :



위 직경들을 f 값의 정의인 N = f / D 에 대입해서 얻어진 f 값들을 빛의 양이 많은 쪽부터 적은 쪽으로 순서대로 나열하면 다음과 같다 :

1.0
1.4
2.0
2.8
4.0
5.6
8.0
11.3
16.0
22.6
...

어디서 많이 본 숫자들이다.
지금, 자신이 가진 카메라를 들고, 다이얼을 돌려서 f 값을 조절해 보자.
기종에 따라 차이가 있겠지만, 내 카메라인 gf1 의 예를 들어 보겠다 :




위 표에 있는 숫자들이 보인다.
다이얼을 돌려서 f 값을 조절하면, 저 눈금 사이를 1/3 씩 움직여 가는 것을 확인할 수 있다.
현대의 카메라들은 사용자가 빛의 양을 딱 두 배, 절반씩 조절하는 것 보다 좀 더 세밀하게 조절할 수 있게끔 위에서 보는 바와 같이 f 값을 좀 더 세분화 해 두었다. 내 gf1 은 세 단계로 세분화 시켰지만, 카메라에 따라서, 네 단계로 한 기종도 있으며, 두 단계로 한 기종도 있다.

기억해야 할 것은 저처럼 숫자가 적혀 있는, 굵은 눈금으로 표시된 f stop 들 간에는 밝기가 정확히 두 배 씩 차이가 난다는 것이다.


밝기 조절 - f 값과 셔터 속도와의 상관 관계

여태까지 약간 복잡(?)한 수식을 써 가면서 f stop 에 대해서, 그 값이 무엇을 뜻하는지를 알아 보았는데, 이 지식을 사진 촬영할 때 어떻게 활용하면 좋을까?

위키피디아에 따르면, f 값을 정하는 표준이 확립되면서, 셔터 속도도 그에 맞추어서 표준화가 이루어졌다고 한다. (http://en.wikipedia.org/wiki/Shutter_speed)
그래서, 셔터 스피드를 1 step 줄이고, f 값을 1 stop 줄이면 (조리개 직경을 1 stop 크게 함) 동일한 밝기의 결과물을 얻을 수 있게끔 표준화가 되었다고 한다. 실제로, 내 gf1 을 S 모드에 두고 다이얼을 돌리면, 그대로 셔터 스피드와 f 값이 변화하는 것을 볼 수 있다 :


표준화된 셔터 스피드 값들은 위키피디아를 참조하자 : http://en.wikipedia.org/wiki/Shutter_speed


이 지식을 활용할 수 있는 상황은 여러 가지가 있겠으나, 지금 머릿속에 떠 오르는 상황은 다음과 같은 상황이다 :

형광등 불빛 아래에서 움직이는 물체를 찍는 상황이다. 카메라의 모드를 자동으로 두고 노출 측정을 하니 f4, SS 1/25 가 나왔다. 그런데, 1/25 초면, 100%, 손떨림 때문에, 흔들린 이미지 밖에 찍지 못할 것이다.

이 때, 동일한 밝기를 유지하면서, 손떨림에 의한 효과도 최소화 하려면, 셔터 스피드를 더 줄여야 할 것이다. 그래서 셔터 스피드를 광량이 절반으로 줄게끔 1/50 초로 1 step 줄이면 (위키피디아의 셔터 스피드 표 참조), f 를 1 stop 줄여야 (조리개를 1 stop 열어야) 한다. 따라서, 같은 밝기를 유지하면서 1/50 초의 셔터 스피드로 촬영하려면, f 는 2.8 이 되어야 한다.

1/50 초는 상당히 느린 셔터 스피드이다. 그래도 불안해서 한단계 더 셔터 스피드를 낮춘다. 1/100 초로 하게 되면, f 값은 2.0 이 되어야 한다.

사진이 어려운 (그러면서도 재미있는) 이유는 여기에 있다. f 가 2.0 이 되면, 피사체가 근접해 있을 경우, 심도가 매우 낮아진다. 그런데, 내가 심도가 깊은 사진을 찍기를 원한다면.... 야간 실내 촬영의 경우, 방법이 없다. 삼각대를 사용하고, 셔터 스피드를 높이면서, f 값을 크게 하는 수 밖에 없다. 혹은 flash 를 사용하는 수 밖에 없다.


일반적으로 사용되는 용어 - 밝은 렌즈, 빠른 렌즈

여러가지 어려운 이야기들을 두서없이 더 어렵게 ㅠㅠ 이야기했는데, 이제, 일반적인 카메라 동호회 등에서 이야기하는 f 값에 관련된 용어들을 다시 한번 생각해 보자.

먼저, f 값이 작은 렌즈를 "빠른 렌즈 (fast lens)" 라고 이야기한다. 왜인지는 생각해 보면 쉽게 알 수 있다. f 값이 작은 렌즈는 셔터를 그만큼 크게 개방하므로 빛의 양이 많이 들어오게 할 수 있다. 그래서 셔터 스피드를 빠르게 하더라도 적절한 노출의 사진을 얻을 수 있기 때문에 "빠른 렌즈 (fast lens)" 라고 부르는 것이다.

같은 맥락에서 f 값이 작은 렌즈를 "밝은 렌즈" 라고 부르기도 한다.


그럼, 이게 f 값의 전부인가?

아니다. f 값은 나같은 초심자들의 동경의 대상인 소위 "아웃 포커싱" 된 사진을 찍는 데에도 큰 영향을 미친다.

아웃 포커스 (shallow focus) 는 다음 기회에 자세히 다루도록 하고, 여기서는 조리개를 많이 열면 아웃 포커스 효과가 두드러지게 나타나고, 조리개를 조으면 아웃 포커스 효과가 잘 안나타난다는 것만 이야기하도록 하겠다.

다시 말하면, f 값을 작게 하면 아웃 포커싱이 되고, 크게 하면 안되거나, 되어도 그 정도가 약하다는 것만 언급하고, f 값과 심도와의 관계 함수와 같은 자세한 내용은 다음 기회에 다루도록 하겠다.


:

timsort

Computing 2010. 10. 7. 16:27

timsort ?

timsort 는 merge sort 를 아주 많이 최적화 한 소팅 알고리즘이다. 고안자의 이름인 Tim Peter 를 따서 timsort 라고 부른다.

소팅 알고리즘 종류의 분류상 timsort 는 stable sort, in-place sort 로 분류된다.

timsort 는 naive 한 (실험실에서나 볼 수 있는) pseudo random data 뿐만 아니라 quick sort 등이 좋은 성능을 보이지 못하는 real world data 에서도 상당히 좋은 성능을 보여 준다. 그런 연유로 사이, java.util 의 array sort 가 timsort 를 사용하고 있으며, python 의 list sort 가 timsort 알고리즘을 사용하고 있다. 좀 더 자세한 소개는 wikipedia 에 잘 나온다: http://en.wikipedia.org/wiki/Timsort

timsort 는 merge sort 에 아주 많은 최적화를 해 두어서 완벽하게 이해하는 데에는 꽤나 시간이 걸린다. 그러나 일단의 기본 원리만 알면 복잡하긴 해도 그다지 어렵지는 않다. 영문으로 된 자세한 설명은 timsort 의 고안자인 Tim Peter 가 다음의 페이지에 잘 적어 두었다: http://svn.python.org/projects/python/trunk/Objects/listsort.txt

본 article 에서는 위 문서의 내용 중 timsort 의 핵심이라고 할 수 있는 몇가지를 알기 쉽게 (우리말로) 다시 설명해 보도록 하겠다.


Runs

일단, 위에서도 언급하였듯이, timsort 의 기본 알고리즘은 변형된 merge sort 이다. 다만, naive 한 merge sort 와 크게 다른 점은 run 생성시 run 의 size 를 adaptive 하게 동적으로 구한다는 점이다. timsort 는 run 을 만들 때, 이미 정렬되어 있는 sequence 를 기본 단위로 해서 생성한다. 만약 정렬되어 있는 기본 단위가 특정 상수 (minrun) 보다 작다면, 그 특정 상수만큼의 길이를 binary insertion sort 를 한 후 인위적으로 정렬시킨 후 이를 run 으로 사용한다.

timsort 가 호출되면 제일 처음 하는 일은 minrun 값을 구하는 것이다. minrun 은 임의의 run 이 구성될 수 있는 최소 길이이다. minrun 을 구할 때, 만약 입력된 sequence 의 element 갯수 N 이 64 보다 작으면 minrun 은 N 이 된다. 이처럼 작은 단위에서는 웬만해서는 binary insertion sort 보다 빠른 소팅방법은 없으며, 그냥 binary insertion sort 를 sequence 에 대해 수행해 버린다.

minrun 을 계산할때의 목표는 merge 과정에서 merge 대상이 되는 각각의 run 이 가능한한 perfectly balanced 상태를 유지하도록 하는 것이다. 왜냐하면 그렇게 했을 때 merging 이 가장 빠르기 때문이다. 이 조건을 만족하는 minrun 값을 구하는 법에 대한 자세한 내용은 http://svn.python.org/projects/python/trunk/Objects/listsort.txt 의 Computing minrun 부분을 참조하도록 한다.

run 을 구하는 데 있어서, 만약 구해진 run 의 길이가 minrun 값보다 작다면, 앞에서도 계속 언급했듯이, minrun 길이의 구간을 binary insertion sort 를 이용해서 sort 해 버린 후 이를 run 으로 잡는다. binary insertion sort 는 작은 길이의 sequence 에서는 매우 빠른 성능을 보이는 sorting algorithm 으로써, gnu libc 의 quick sort 나 bsd libc 의 quick sort 또한 partition 을 해 나가다가 partition 의 길이가 일정 사이즈 이하가 되면 quick sort 를 포기하고 binary insertion sort 를 수행하는 최적화를 하고 있다.


Stablity and definition of descending and ascending

한가지 염두에 두어야 할 것은 timsort 는 stable sort 라는 것이다. 이로 인해 descending 과 ascending 의 정의는 아래와 같이 strict 하게 정의되어 있다:

a run with n elements is ascending iff a1 <= a2 <= a3 ... an-1 <= an
a run with n elements is descending iff a1 > a2 > a3 ... an-1 > an

위와 같은 strict 한 descending 의 정의로 인해서 sorting 시 descending 으로 정렬되어 있는 run 을 만날 경우, 양 끝의 element 를 서로 swap 해서 해당 run 을 ascending 으로 교환하더라도 stability 가 보장된다.


Merge Stack

timsort 는 run 을 구하고, 구해진 run 을 계속 merge 해 나가는 과정의 반복이다.

이에 있어서, 앞서도 언급했지만, merge 가 가능한한 balanced 상태로 이루어 지는 것이 알고리즘의 효율이 훨씬 좋아지기 때문에, 가능한한 비슷한 길이의 run 끼리 merge 하기 위해 merge stack 이라는 구조체를 사용하고 있다.

일단 하나의 run 이 만들어지거나 판별 되면, timsort 는 그 run 의 시작 위치와 길이를 merge stack 이라는 구조체에 push 해 넣는다. merge stack 은 소스코드를 살펴 보면, 그냥 시작 위치와 길이를 가지고 만들어진 구조체의 배열이다.

이렇게 하나의 run 을 push 한 후에는 merge_collapse() 함수를 호출하여서 앞서 push 되어 있던 run 과 merge 를 할 것인가를 판단하여 merge 를 하거나 혹은 merge 하는 것은 약간 뒤로 미룬 후 그 다음 run 을 찾는 루틴으로 돌아가거나 한다.

메모리 사용이나 캐쉬 히트율등을 고려할 때 merge 를 최대한 미루는 것과 최대한 빨리 그때그때 하는 것 사이에서 적절한 타협을 해야 하는데, timsort 에서 취하고 있는 방법은 아래의 두 가지 조건을 만족하도록 merge stack 을 유지하는 방법을 취하고 있다:

run 이 입력 sequence 상에서 왼쪽에서 오른쪽으로 A, B, C 의 순서로 배치되어 있을 경우,
invariant #1 : A > B + C
invariant #2 : B > C

그러나 만약 merge stack 의 각 run 의 길이가 A <= B + C 일 경우에는 A 와 B 둘 중 작은 쪽을 B 와 merge 하는 정책을 취한다. 예를 들면 아래와 같다: (뒤의 숫자는 run 의 길이이다)

A:30 B:20 C:10 ----> A:30 BC:30   (A > C 임. 따라서 C 를 B 와 merge)

만약 다음과 같다면:

A:500 B:400 C:1000 ----> AB:900 C:1000    (A < C 임. 따라서 A 를 B 와 merge)

그러나, 위 두가지 경우 모두 이처럼 merge 를 수행한 이후에도 위의 조건 2 번을 여전히 만족시키지 못한다. 그럴 경우 위의 조건들을 만족시킬 때 까지 merge_collapse() 함수를 계속 수행하도록 한다.

참고로, 서로 인접해 있는 run 끼리만 merge 를 하는 이유는 stability 를 만족시키기 위해서이다. 왜 그렇게 해야만 stability 가 만족되는지는 http://svn.python.org/projects/python/trunk/Objects/listsort.txt 문서를 참조할 것.


Right before actual merging

윗 절에서 merge 할 run 을 선택하는 방법을 설명했으니 이제는 merge_collapse() 함수에서 실제 merge 가 어떻게 수행되는지를 살펴 보도록 하겠다.

merge_collapse() 함수는 merge stack 에 남아있는 run 이 없어질 때까지 merge stack 의 run 들을 merge 하는 함수인데, 실제 merge 는 merge_collapse() 함수에서 호출되는 merge_at() 함수에서 수행되므로 merge_at() 함수를 개략적으로 살펴 보도록 하겠다.

merge_at() 함수에서 본격적인 merge 에 들어가기 전에 하는 일은 merge 를 수행할 필요가 없는 구간을 구해내는 것이다. 다시 말하면, 각각의 run 은 모두 이미 그 안에서 정렬되어 있는 상태이므로 아래의 조건을 만족하는 구간을 주어진 두 개의 run 에서 구해낸다. 아래의 그림과 같다:


merge_at() 함수에서는 위 그림의 RUN ARUN B 를 merge 하게 된다. 이 때, gallop_right() 함수를 수행하여 RUN B 의 첫번째 원소보다 큰 원소들이 첫번째 출현하는 위치를 RUN A 에서 찾는다. 그리고, gallop_left() 함수로 RUN A 의 마지막 원소보다 작은 원소가 첫번째 출현하는 위치를 RUN B 에서 역순으로 찾는다.

사실상, AB 를 전부 merge 할 필요는 없다. 위의 조건을 만족하는 A'B' 만 merge 하면 되는 것이다.

gallop_left(), gallop_right() 함수에 대해서는 다음 절에서 설명하도록 하고, 본격적인 merge 함수의 개략적 흐름에 관해서 이야기해 보도록 하자.


Merge Memory

메모리에 대해 다루기 전에 우선 알아 두어야 할 사항을 짚어 두고서 넘어가도록 하자.

우선 바로 앞 절에서 다루었듯이, merge 를 수행할 필요가 없는 부분은 이미 잘려지고, 위 그림의 A' 과 B' 으로만 merge 를 수행하게 된다. 앞으로는 A' 과 B' 에서  ' 기호를 떼고 그냥 A, B 라고 부르겠다. 이처럼 merge 를 수행할 필요가 없는 부분을 잘라 냄으로써, memory 할당량을 줄일 수 있다. 뿐만 아니라 성능면에서도 이득을 기대할 수 있다. 그러나, 만약 data sequence 가 random 일 경우에는 이같은 노력이 오버헤드로 작용한다. 그럼에도 불구하고, timsort 는 "real world data" 에 완전한 random data 는 아주 드물다는 rationale 하에 작성되었기 때문에, 더 큰 성능 이득을 얻기 위한 작은 도박을 하고 있는 것이다.

어찌 되었던, timsort 의 merge algorithm 은 성능과 메모리 효율을 높이기 위한 목적으로 크게 두 가지 루틴으로 나뉜다: merge_lo()merge_hi() 가 그것인데, 두 루틴의 기본 로직은 동일하다. 다만 각각의 루틴이 사용되는 경우 및 merge 의 진행 방향이 다를 뿐인데, run 의 길이에 따라서 어떤 루틴이 사용될지가 결정된다:

if A <= B, merge_at() calls merge_lo()
if A > B, merge_at() calls  merge_hi()


이제, 메모리에 대해 이야기할 준비가 되었다.

merge algorithm 이 원래 그렇듯이, timsort 역시 merge 를 수행하기 위한 부가적인 memory 를 필요로 한다. 이 메모리를 merging area 라고 부르자. timsort 는 입력 sequence 에서 이미 정렬된 구간을 run 으로 선택하기 때문에 run 의 길이가 교과서의 merge sort 와는 달리 가변적이다. 따라서 merging area 를 할당하는 데에도 약간의 트릭을 사용하였다.

트릭은 간단하다. merging area 를 할당할 때 두 개의 run 중 더 작은 run 의 사이즈만큼만 할당하는 것이다.

우선 merge_lo() 의 경우를 살펴 보자. merge_lo() 는 merge 대상이 되는 run 의 길이가 A <= B 일 때 호출된다. 따라서, merging area 의 구성 및 merge 방향은 아래의 그림과 같이 구성된다:


위 그림에서 볼 수 있듯이, run A 의 길이가 더 짧기 때문에, run A 의 사이즈만큼 메모리를 할당한다. 그리고 나서 할당한 메모리로 원래 run A 의 내용을 복사해 준다. merge 는 복사된 run A 와 run B 사이에서 일어나며, merge 의 결과는 원래 run A 였던 메모리의 시작부분부터 하나씩 저장되게 된다.

약간 주의깊이 생각해야 할 것은, 이처럼 merge 를 하는 와중에 exception 이 발생하거나 sort 가 중단될 경우, 나머지 남은 부분을 원래 있던 부분에 복사해 주어야 한다는 것이다. in-place sort 의 조건을 만족시켜야 하기 때문이다.

merge_hi() 의 경우는 merge 대상이 되는 run 의 길이가 A > B 일 때 호출된다. 따라서 merging area 의 구성 및 merge 방향은 아래의 그림과 같이 구성된다:


마찬가지로, 더 짧은 길이의 run 인 run B 만큼의 메모리를 할당하고, 그곳에 원래의 run B 를 복사해 넣는다. 그리고, merge_lo() 와는 반대로 오른쪽에서 왼쪽으로 각 run 의 element 를 비교해 가면서 merging area 에 merge 결과를 채워 넣는다.

merge_hi()merge_lo() 와는 달리, 각 run 의 element 를 비교해서 merging area 에 채워넣는 결과는 두 element 중 보다 큰 element 를 채워 넣는다는 것에 주의하도록 한다.


Merge Algorithms

앞 절에서 merge_hi()merge_lo() 에 대해 소개했기 때문에, 두 루틴의 공통적인 부분만 설명하겠다.

merge 루틴은 크게 두 개의 mode 로 나누어진다. 첫번째는 일반적인 merge 와 동일한 mode 이다. "one pair at a time mode" 라고 부르도록 하겠다. 두번째는 "galloping mode" 라는 특수한 mode 이다.

설명은 merge_lo() 를 기준으로 진행하겠다. merge_hi() 의 경우는 괄호 안의 단에 기입했다.

merge 의 시작은 교과서의 알고리즘대로 run A 와 B 의 첫번째 (merge_hi() 에서는 마지막) element 를 서로 비교해서 더 작은 (merge_hi() 에서는 더 큰) 값을 merging area 에 복사해 넣는 것으로 시작한다. 설명의 편의를 위해서 run B 의 첫번째 (마지막) element 가 더 작은 값 (큰 값) 을 가지고 있다고 가정하자. 그러면, run B 의 첫번째 (마지막) element 가 merging area 에 복사된다.

여기서, 교과서의 merge 와 다른 점은 각각의 run 이 연속해서 선택된 횟수를 유지한다는 점이다.

만약 어느 한쪽의 run 이 연속해서 MIN_GALLOP 만큼 선택되었을 경우에는 "galopping mode" 로 전환된다. 설명의 편의상 run A 가 연속해서 선택된 run 이고, run B 는 연속해서 선택되지 않은 run 이라고 가정하도록 하자.

galopping mode 는 연속해서 MIN_GALLOP 이상 선택된 run A 에서 연속해서 선택되지 않은 run B 의 현재 위치의 값 (편의상 B[0] 라고 두겠다) 보다 큰 값이 언제 출현하는가를 검색한다. galopping mode 라는 이름이 시사해 주듯이, A 에서 B[0] 를 검색해 갈 때, A 의 인덱스를 1 씩 증가시켜서 검색하는 것이 아니라 2n 씩 검색주기를 늘려서 검색해 간다. 그리고, B[0] 보다 큰 값이 발견되면 바로 앞의 인덱스와 발견된 인덱스 사이에서 binary search 를 해서 B[0] 가 어느 위치에 들어가야 할지를 결정한다. 그리고 그 위치보다 앞에 존재하는 모든 A 의 값을 merging area 에 복사해 넣는다.

그리고 나면, 다시 A[0] 의 값을 가지고 run B 를 동일한 방식으로 검색한다. 이 때, 방향은 오른쪽에서 왼쪽방향이다. 그렇게 해서 결정된 run B 의 일정 구간을 다시 merging area 에 복사해 넣는다.

위의 두 과정을 복사해 넣어진 구간의 길이가 MIN_GALLOP 보다 길 동안 계속한다. 만약 복사해 넣은 구간의 길이가 MIN_GALLOP 보다 작을 경우 다시 "one pair at a time mode" 로 돌아간다.


Galloping 에 대한 자세한 설명은 그다지 필요 없을 듯 하다.
소스를 받아서 한번 살펴보는 것과, 방금 위에서 설명한 것으로 충분할 것 같다.


Performance

그러면, 가장 중요한 소팅 알고리즘의 성능을 실제로 테스트해 볼 시점이다.

naive 한 성능 측정은 random 데이터를 생성해서 그것을 소팅하는 데에 걸리는 시간을 가지고 알고리즘의 성능을 판단한다. 그렇지만, 그것만으로는 불충분하다. 왜냐하면 실 세계에서 발생하는 데이터는 random 한 경우보다 일정한 패턴을 가지고 있기 때문이다. 이 때문에 timsort 가 고안되었다고도 할 수 있다.

성능 측정에 사용할 입력 sequence 는 대략 아래와 같은 유형이다 : (출처 : http://www.softpanorama.org/Algorithms/sorting.shtml)

  1. Completely randomly reshuffled array (this is the only test that naive people use in evaluating sorting algorithms) .
    완전히 random 하게 뒤섞인 수열.

  2. Already sorted array (you need to see how horrible quicksort is on this case and how good shellsort is ;-). This is actually a pretty important case as often sorting is actually resorting of previously sorted data done after minimal modifications of the data set.
    이미 정렬되어 있는 수열 (이 경우 퀵 소트가 얼마나 형편 없는 성능을 내며, 쉘소트가 얼마나 빠른지 봐야 한다. 이 케이스는 사실상 매우 중요한 케이스라고 할 수 있는데, 왜냐하면 대부분의 경우 소팅은 이전에 정렬되어 있던 데이터에 아주 작은 데이터를 수정한 후 그 세트를 다시 소팅하는 경우가 많기 때문이다)

  3. Already sorted in reverse order array (many algorithms work slow on such an array)
    역순으로 이미 정렬되어 있는 수열 (상당수의 알고리즘이 느린 성능을 보인다)

  4. Chainsaw array
    톱날처럼 분포되어 있는 수열

  5. Array consisting of identical elements (many algorithms work slow on such an array)
    같은 값으로 구성된 수열 (상당수의 알고리즘이 느리게 동작한다)

  6. Already sorted array with N permutations (with N from 0.1 to 10% of the size)

  7. Already sorted array in reverse order array with N permutations

  8. Data that have normal distribution with duplicate (or close) keys (for stable sorting only)
    중복되거나 아주 근사한 값이 여러개 분산되어 존재하는 수열 (stable sorting 에만 적용)

  9. Pseudorandom data (daily values of S&P500 or other index for a decade might be a good test set here; they are available from Yahoo.com)
    의사난수(?) 로 이루어진 수열 (주식시세 변동 등)



실제 테스트한 데이터는 http://orchistro.tistory.com/205 를 참조한다.


----

timsort source code download : http://timsort.googlecode.com/
python 소스트리에서 timsort 루틴만 추출해 낸 것. 포인터를 직접 증/감 시키는 것이 아니라 java 의 구현처럼 index variable 을 사용함. 포인터를 직접 증감하는 방식과의 성능 차이는? 테스트 해 보지 않음.
python 소스보다 조금 더 많은 주석.

----

참고 웹 페이지들 :

wikipedia : http://en.wikipedia.org/wiki/Timsort

python mailing list : http://mail.python.org/pipermail/python-dev/2002-July/026837.html

android java.util : http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/TimSort.java?view=co

python svn repository :
http://svn.python.org/projects/python/trunk/Objects/listsort.txt
http://svn.python.org/projects/python/trunk/Objects/listobject.c

그 외 참고 문헌 (timsort 저자의) :
"Optimistic Sorting and Information Theoretic Complexity" / Peter McIlroy / SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp 467-474, Austin, Texas, 25-27 January 1993


:

google instant search 끄기

Computing 2010. 9. 11. 13:35

며칠전 구글이 검색 페이지에 이상한 짓을 했다.

검색 키워드를 입력하면 입력하는 즉시즉시 결과 페이지가 화면 아래에 뜨는 기능인데,

나는 정신이 산만해져서 이 기능이 매우 마음에 들지 않았다.

자, 어떻게 이 기능을 끌까...


1. 우선, http://www.google.com/instant 에 들어가서 Try it now 버튼을 누른다 :




2. 그러면 instant search 페이지로 이동을 한다.

3. 아무 단어나 검색을 하자 :



4. 검색 결과가 나오면 instant search 를 조정할 수 있는 화면이 나온다. 거기서 instant search off 를 해 주면 된다.




참고 페이지 : http://www.pcworld.in/news/how-disable-google-instant-search-34972010

: