고요한 하늘

32비트 머신에서는 warning 없이 잘 컴파일 되던 것이 64비트 머신으로 갔더니
cast from pointer to integer of different size
이런 메세지가 뜬다..

unsigned short int* 형을 unsigned int형으로 바꾸는 부분에서 발생한 warning인데
sizeof로 확인해보니
unsigned short int*가 64비트에서는 8byte 자료형이고, unsigned int는 4byte 자료형이라서 발생하는 문제였다.
그래서 unsigned int를 unsigned long int로 수정했더니 warning이 사라졌다.

보통의 경우 파일을 처리할때

open보다는 fopen을 사용한다.

O_CREAT니 O_RDWR과 같은 옵션을 외우느니 그런 옵션이 내장되어 있어서

사용하기 편한 fopen을 사용한다.

습관의 차이일수도 있다.(보통은 open보다는 fopen을 먼저 접한다 )

그런데 가끔은 open을 사용해야하는 경우도 있다.

파일을 빈번히 열고 닫을 경우 fopen보다는 open이 속도가 빠르기 때문이다.

정말로 그런지 테스트를 한번 해보았다.

첫번째 파일은 test_open.c로

open, close만 10,000,000번 한다.

두번째 파일은 test_fopen.c는

fopen, fclose만 10,000,000번 한다.

테스트는 test_open한번 실행하고 test_fopen실행하는 식으로 총 5번 시간을 측정했다.

test_open  : avg 24.6/sec

test_fopen : avg 37.6/sec

open, close 함수가 fopen(fclose)함수에 비해 1.5배 정도 빠른것으로 보인다.

물론 open을 파일을 열었을 경우에는 read,write함수를 사용해야 하고 read, write함수를 효율적으로 사용하기 위해서는 한번에 읽어오는  page size를 알아야 하는 번거로움이 있다.

이 테스트에서는 이런 것들을 모두 배제하고 파일을 열고 닫는데 어느 정도 속도차이가 있는지에만 초점을 맞추어 테스트를 진행했다.

보너스 : open, close를 1억번 해도 결과는 같을까?

test_open : 3m54.256s

test_fopen :  5m35.421s

프로그램을 자주 고치다 보면 이전에는 사용했지만 현재에는 사용하지 않는 함수들이 많이 생긴다.

그런 함수들이 한두개에 지나지 않고, 자신이 모든 함수들을 제어할수 있다면 상관없겠지만.
자신이 만든 코드를 다른 사람에게 인수 인계 하거나 문서화를 할때 사용하지 않는 함수는 시선을 혼란시키기 코드 집중도를 떨어뜨리기 때문에 가급적 지우는것이 바람직하다.

그런데 잘 사용하는지 사용하지 않는지 확인 하기 위해서 grep로 찾아도 보고 했지만 정착 최상위 함수가 if 조건으로 복잡하게 되어 있다면 이것을 판단하기는 여간 어려운 것이 아니다.

만에 하나....만번중에 한번정도 실행되는 코드일 가능성 때문에 지울수가 없다.
이런 경우를 사용하지 않는 코드를 찾아볼수 있는 툴이 있는데 이 툴이 바로 gcov 이다.

gcov를 설명하려고 한게 아닌데 이야기가 길어졌다.

본론으로 들어가면
tistory에 포스팅한후에 혹시나 해서 구글에 가서 검색을 했다.(포스팅후 1,2시간 정도 지난것 같다 )

그런데 검색이 된다.


지금 티스트리에는 글을 한달에 한두개 정도 밖에 올리지 않아서 클롤러의 방문횟수가 많지 않을텐데
그럼에도 불구하고, 글을 게시한지 1시간도 되지 않아서 글이 검색에 노출이 된다.

이것은 두가지 의미를 내포한다.
1. 크클롤러가 열라 바쁘게 돌아다닌다. 내 블로그같이 글을 자주 포스팅 하지 않는 곳에도
2. 동적 색인을 한다.  영어권 웹페이지에 대한것과 한국어 웹페이지에 대한것을 별도의 색인 서버에서 색인할텐데 한국어 웹페이지에 대한것은 적어도 1시간 이내에 동적색인을 하는것 같다.

아직 네이버나 다음에서는 검색되지 않는다.
요약하면  TISTORY에 글을 쓰면 구글이 국내 검색엔진 가운데 가장 먼저 검색에 노출시킨다.(성급한 일반화 일수 있음)



언제 시간이 나면 동적 색인이 어느 정도의 interval을 두고 실행되는지 확인해 봐야 겠다.

만들어 놓고 쓰지 않는 함수가 if 분기로 인해 실행이 되지 않는 코드를 찾기 위한 방법으로

아래와 같이 컴파일 하면

gcc -fprofile-arcs -ftest-coverage -g test.c -o test

  test.gcda , test.gcno 와 같은 두개의 파일이 생긴다.

execution>> ./test 1000

execution>> gcov test.c

test.c.gcov 이 생성된다.

vim으로 test.c.gcov를 열어보면

        1:   10:    if(argc != 2)
        -:   11:    {
    #####:   12:        printf("Usage "%s count\n",argv[0]);
    #####:   13:        exit(1);
        -:   14:    }
        -:   15:
        -:   16:
        -:   17:    else

     1001:   38:    for(i = 0; i < count; i++)
        -:   39:    {

실행되지 않는 코드가 표시된다.
참고 : http://korea.gnu.org/manual/release/gcov/

일반적으로 리눅스에서 작업중 튜닝이 필요할때 프로파일링 작업을 한다.

가장 일반적인 방법이 컴파일 옵션에 -pg를 주고 pgrof로 프로파일링된 내용을 보는것인데

이것과는 조금 다른 프로파일링 기법이 있어서 소개한다.

이미 많은 개발자들이 사용하고 있는 valgrind의 서브 모듈인 callgrind가 바로 그것인데

아래에 간단한 사용법을 정리하였다

 실행 방법

> valgrind --tool=callgrind ./test < input.txt > /dev/null

실행된 내용은 가지고 출력 파일을 생성한다

>callgrind_annotate callgrind.out.7838 > callgrind.out.7838.txt

사용법 보기

> callgrind_annotate --help

함수별 결과보기

> callgrind_annotate --inclusive=yes callgrind.out.7842 > callgrind.out.7842.txt

호출한 함수 목록 보기

>callgrind_annotate --inclusive=yes --tree=caller callgrind.out.7842 > callgrind.out.7842.txt

>많은 정보 보기

>callgrind_annotate --inclusive=yes --tree=both --context=100 --auto=yes --threshold=10 callgrind.out.11328 > callgrind.out.11328.txt

I   <- instruction

D  <- data

r   <- read

w  <- write

l    <- level n cache
m  <- memory

공정한 시간 측정을 위해서

우리는 문자열 비교를 위한 strcmp 함수를 해쉬와 트리 검색시 동일한 코딩 스타일을 사용한  inline code로 교체하였다.

우리는 ternary tree와 hashing의  성능 평가를 하기 위해 동일한 사전을 사용한다.

우선 각 단어를 트리에 입력한다.

아래 그림은 3개의 서로 다른 머시에 데이터를 빌드하고 검색시의 시간 측정 결과이다.

 

 

 

ternary search trees는 검색에 실패할때에 항상 눈에 띌만큼   해싱 보다 빠르다.

 Ternary tree 에서 일부의 캐릭터로 검색결과가 없음을 알수 있는데 반해 해싱은 모든 키를 검사한후에야 알수 있다.

길이가 긴 키 데이터군과 앞부분 몇글자가 미스매치된 군에서 ternary tree는 해싱의 1/5정도의 시간이 소요된다.

 

함수 insert3과 search의 결합은  symbol table의 시간 효율을 가져온다

내 웹사이트에 기술된 일반적인 사전에서 ternary search trees는 해싱의 약 1/3정도의 공간만을 사용한다.

ternary search trees의 선택적인 표기는 좀더 공간효율이 좋다.

서브 트리가 싱글 스트링을 포함할때, 문자열 자체의 포인터를 저장한다(그리고 각 노드는 그 노드가 노드 또는 스트링을 가르키고 있는지를 표시하기 위해 3비트를 저장한다

이것은 코드가 덜 효율적임을 의미한다.그러나 해싱에서 사용한 공간에 가깝게 트리의 노드를 줄인다.

 우리는 여러면에서 Ternary Search Tree의 안좋은 성능에 대해서 The Analysis of Hybrid Trie Structures 논문에 분석해 놓았다.

 

 binary search tree의 대부분의 표준기술은 즉시 ternary cousins에 즉시 적용할수 있다.

예를 들면 우리는 재귀적 순회로 소팅된 순서로 트리에 있는 문자열을 보여줄수 있다.

void traverse(Tptr p)

{

if(!p) return;

traverse(p->lokid);

if( p->splitchar)

traverse(p->eqkid);

else

printf("%s\n",(char*)p->eqkid);

traverse(p->hikid);

}

단순한 재귀 검색은  모든 아이템의 주어진 범위내의 주어진 성분 또는 리스트의 전임자 또는 후임자를  발견할수 있다.

만약 모든 노드에 count 필드를 추가한다면 우리는 빠르게 주어진 범위의 선택한 mth번째 가장 긴 요소 또는  주어진 서브트링으로 시작하는 많은 문자열의 수를 알 수 있을 것이다.

ternary tree 에서 이런 대부분의 연산에는 로그 시간이 요구된다.그러나 hash table에서는 linear time이 요구된다.

 

 

 

 

 

 

이 글은 스프링노트에서 작성되었습니다.

htttp://www.ddj.com/windows/184410528

당신이 문자열을 저장 할려고 할때 당신은 어떤 data structure를 사용하는가

존과 로버트는 binary search trees의 공간 효율과 digital tries의 시간 효율을 결합한 ternary search trees로 시작할  것을 제안했다.

--

당신이 문자열을 저장 할려고 할때 당신은 어떤 data structure를 사용하는가

당신은 문자열을 array에 뿌리는 해쉬테이블을 사용할수도 있다.

이방법은 접근이 빠르다. 하지만 상대적인 순서에 대한 정보를 잃어버린다.

다른 방법은 문자열을 순서대로 저장하고 비교적 빠른 binary search trees를 사용하는것이다.

아니면 당신은 가볍고 빠르지만 공간을 많이 소비하는 digital search tries를 사용하는 것이다.

이 기사에서 우리는 binary search trees의 공간 효율과 digital tries의 시간 효율을 결합한ternary(3-wary) search trees를 실험한다.

일반적인 검색 문제에서 이방법은 해슁을 하는 방법보다 빠르다. 그리고 다양한 기능들을 제공한다.

Ternary searches은 해슁보다 빠르고 powerful하다.

우리는 1997년 심포지엄에서 ternary search trees에 대해서 설명하였다.

아래 그림은 binary search tree로 2개의 알파벳을 갖는 12개의 노드들을 표현한다.

모든 노드에 좌측에는 자신보다 작은 값을 우측에는 큰값을 갖는다.

검색은 root에서 시작한다.

"ON"이라는 단어를 찾기 위해서 우리는 먼저 "IN"과 비교하고 오른쪽 노드로 이동한다.

그리고 다시 "OF"와 비교하여 우측 노드로 이동하고  다시 "OR"과 비교하여 좌측의 "ON" 을 검색한다.

모든 비교과정에서 두단어의 모든 캐릭터에 접근해야 한다.

Digital search tries는 문자열의 캐릭터를(1byte)를 저장한다.

아래 그림은 12개 단어셋에 대해서 Digital search tries로 표현되었다.

 각 입력 문자열은  각 노드를 표현하는 노드 바래 아래에 보여진다.

트리의 각 노드는 26개의 서브 노드를 가지고 있다.

검색은 매우 빠르다. 만약 "is"를 검색한다면 root에서 시작하여 'i'노드로 이동하고 다시 's'로 이동한다. 이것으로 검색이 끝난다.

모든 노드에서 우리는 array에 직접 접근한다.

불행히도 search tries는 엄청난 공간을 요구한다.

노드마다 26개의 branch,를 가지기 때문에 104byte의 공간을 요구하고 256개의 노드는 kilobyte를 소비한다.

8개의 노드 34000개의 캐릭터를 표현하기 위해서는 megabyte이상의 메모리를 필요로 한다.

binary search trees의 공간 효율과 digital tries의 시간 효율을 결합한ternary(3-wary) search trees는 캐릭터 단위로 진행하는점에 있어서 tries와 비슷한다.

각노드는 3개의 children을 가짐으로써 공간적인 효율을 기함으로써 binary search trie와 비슷하다.

검색시 비교는 노드에서 문자열의 한 캐릭터와 현재 키릭터를 비교한다.

만약 검색할 캐릭터가 작으면 좌측으로 분기하고 검색할 캐릭터가 크다면 우측으로 분기한다.

만약 같다면 middle child로 이동하여 검색하는 문자의 다음 글자로 다시 위의 작업을 진행한다.

아래그림은 12개의 단어셋을 가지는 balanced ternary search tree이다.

좌우 child는 실선으로 equal pointer는 점선으로 펴현했다.

입력 문자열의 터미널 노드에 표시했다.

'is' 검색시 루트에서 시작하여 'i' 노드에서 's'로 equal child로 이동한다.그리고 's'를 비교함으로써 검색이 종료된다.

--- continued ---

참고 : http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html

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

     

대학원때 POS 태거를 구현할때 처음 접했던 알고리즘인데 태거이외에도 많은 곳에서 사용되는듯하다.

HMM이 등장하는 곳에서는 처리 속도때문에 어김없이 따라 나오는 알고리즘으로 dynamic programming과도 밀접한 관련이 있다..

음성 처리와 언어처리에서 많이 사용되지만 HMM이 앞에 두분야 이외에도 확률이 수반되는 분야에는 빠지지 않고 등장하는것 같다.

c로 프로그램 하기에는 코딩시간도 오래걸리고 나중에 봐도 기억이 안나는 관계로 open office 스프레트 쉬트로 간단히 만들어 봤다.

open office로 아래 파일을 열면 데이터들이 보이는데 데이터들에 마우스 포인터를 찍으면 안에 수식이 나타난다. 수식은 곱셈이 전부이고 함수는 max()함수가 전부이다.

max()함수는 안에 인자들중 최대값을 선택하는 함수이다. 예를 들면(ex = max(1,2,3)) 이면 max의 리턴값은 3이 된다.

각 값들이 어떤 값을 참조했고 어떤 값에 종속적인지 보기 위해서

도구(alt+t->추적(alt+d)을 클릭하면 선례추적과 종속 추적이 있는데 항목별로 선택해보면 값들의 의존관계를 볼수 있다.

단축키 : shift + f7(선례), shift +f5(종속)


이미지 출처 :    http://www.telecom.tuc.gr/~ntsourak/demo_viterbi.htm