'Programming' 카테고리의 글 목록 (7 Page)

Programming

strncpy vs memcpy 2010.12.02
코드 최적화 2010.11.08
N-Gram 소스 2010.11.08
strtok_r() 함수를 이용한 문자열 파싱 2010.11.06
strtok and strtok_r 2010.11.06
strtok, strsep와 같은 토큰 추출 프로그램 2010.11.06
python bigram 2010.11.05
[pyton] python으로 중간 수행시간 구하기...? 2010.10.27

strncpy vs memcpy

nlogn 2010. 12. 2. 14:17

2010. 12. 2. 14:17

[출처 : http://blog.daum.net/jchern/13756798]

블로그에서 strncpy와 memcpy 중 memcpy가 더 빠르다고 본 기억이 있어서 확인차원에서 구글 codesearch를 빌려 확인

-------------------------------------------------------------------

STRNCPY

-------------------------------------------------------------------

char *
strncpy(char *dst, const char *src, size_t n)
{
        if (n != 0) {
                char *d = dst;
                const char *s = src;

                do {
                        if ((*d++ = *s++) == 0) {
                                /* NUL pad the remaining n-1 bytes */
                                while (--n != 0)
                                        *d++ = 0;
                                break;
                        }
                } while (--n != 0);
        }
        return (dst);
}
-------------------------------------------------------------------

strcpy는 assign 연산후에 널인지를 체크하는 비교 연산이 한번더 수행되고

널체크이후 타켓에 남은 size n만큼 0으로 패딩한다.

-------------------------------------------------------------------

MEMCPY

-------------------------------------------------------------------

void *memcpy(void *_dst, const void *_src, unsigned len)
{
        unsigned char *dst = _dst;
        const unsigned char *src = _src;
        while(len-- > 0) {
                *dst++ = *src++;
        }
        return _dst;
}
-------------------------------------------------------------------

memcpy는 심플하게 len만큼 복사하고 끝...

정확히 size를 알고 있다면 strncpy보다는 memcpy가 속도상 약간의 이득이 있는것으로 보임..

저작자표시

코드 최적화

nlogn 2010. 11. 8. 16:40

2010. 11. 8. 16:40

http://www.kucuny.com/tc/55

http://kldp.org/node/79109

http://www.joinc.co.kr/modules/moniwiki/wiki.php/Site/C/Documents/COptimization

저작자표시

N-Gram 소스

nlogn 2010. 11. 8. 16:36

2010. 11. 8. 16:36

[출처 : http://irgroup.org/zbxe/5022]

n-gram이란 입련된 문자열을 n개의 음절단위로 절단하는 방법입니다.

예를 들어 "정보검색" 이란 문자열을 절단할 때..

1-gram : 정, 보, 검, 색 으로 분리

2-gram : 정보, 보검, 검색 으로 분리

3-gram : 정보검, 보검색 으로 분리

...

^_^ 간단하죠?

이 방식은 초기 검색엔진들에서 키워드 추출하는 방식으로 많이 애용되었습니다.

단순한 방식과 빠른 키워드 추출로 인기가 좋았죠.

특히나 미국의 검색엔진들이 CJK(중국,일본,한국)의 언어들을 처리하기 위해 형태소분석기를 만들수 없는 상황에서 많이 애용되었습니다.

부산물로 "사오정검색"이란 단어가 생겨나기도 했구요.. "보검"을 검색하면 정보검색이 나타나니까요..

서론이 길어졌습니다.

다음은 소스코드입니다.

=============================================================================

/******************************************************************************
N-Gram module

화일명: ngram.h
작성자:
작성일: 2001.12.03
내 용:

******************************************************************************/

#ifndef __N_GRAM_H__
#define __N_GRAM_H__

#define MAX_N_GRAM_NUM 10
#define MAX_ONE_WORD_SIZE ((MAX_N_GRAM_NUM + 1) * 2)
#define MAX_N_GRAM_WORD 10000
#define MIN_N_GRAM_NUM 1

// n-gram을 사용하여 string을 분해한다.
int NGram(unsigned char *str, int min, int max, unsigned char value[][MAX_ONE_WORD_SIZE]);

// n-gram으로 분해된 term들에 대해 중복을 제거하고 중복 갯수를 저장한다.
// 중복갯수는 각 단어의 처음에 한바이트로 기입된다.
int AvoidDuplicationTerm4NGram(unsigned char value[][MAX_ONE_WORD_SIZE], int num);

#endif

/******************************************************************************
N-Gram module

화일명: ngram.c
작성자:
작성일: 2002.12.03
내 용:

******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "ngram.h"

/******************************************************************************
AvoidDuplicationTerm4NGram
N_Gram 함수로 stem된 term들의 중복 여부를 검사하여 중복된 term들을 배제시킨다.
이 때 value 변수의 각 단어들은 첫번째 바이트로 중복된 갯수를 가진다.

input : unsigned char value[][MAX_ONE_WORD_SIZE]
int num 현재 item의 갯수
output: unsigned char value[][MAX_ONE_WORD_SIZE]
return: 중복 배제시킨 term의 갯수
******************************************************************************/
int AvoidDuplicationTerm4NGram(unsigned char value[][MAX_ONE_WORD_SIZE], int num)
{
int cnt;
int i;
int j;
unsigned char tmp[MAX_ONE_WORD_SIZE];

strcpy(tmp, value[0]);
value[0][0] = 1;
strcpy(value[0] + 1, tmp);

for(i = 1, cnt = 1; i < num; i ++)
{
  for(j = 0; j < cnt; j ++)
  {
   if(strcmp(value[i], value[j] + 1) == 0)
   {
    if(value[j][0] < 255)
     value[j][0] ++;

    break;
   }
  }

  if(j == cnt)
  {
   strcpy(tmp, value[i]);
   value[cnt][0] = 1;
   strcpy(value[cnt] + 1, tmp);

cnt ++;
}
}

return cnt;
}

/******************************************************************************
NGram
입력된 문자열을 min~max 사이의 n-gram으로 절단한다.
ascii code 128글자와 한글(ksc5601)코드에 대한 지원만을 한다.
stem 된 각 term들의 최대 갯수는 10000개로 제한한다.
한글 stem시 2byte씩 한글자를 이루므로 한 단어에 대한 버퍼의 크기는 두배로
잡아야 한다.
한글 정보검색에서 사용할 때는 1-gram과 bi-gram을 사용하는 것이 효율상 바람직.
필요에 따라서는 3-gram도 적용해 볼만 함
대소문자 구별을 한다.

input : char *str
int min n-gram 시작값
int max n-gram 마지막값
output: char value[][MAX_ONE_WORD_SIZE]
return: value count
******************************************************************************/
int NGram(unsigned char *str, int min, int max, unsigned char value[][MAX_ONE_WORD_SIZE])
{
int cnt;
unsigned char *p;
unsigned char *src;
int i;
int j;
int start;
int end;
int nletter;

start = (min > 0) ? min : 1;
end = (max < MAX_N_GRAM_NUM) ? max : MAX_N_GRAM_NUM;

cnt = 0;
for(i = start; i <= end; i ++)
{
  src = str;
  while(*src)
  {
   p = src;
   nletter = 0;
   for(j = 0, nletter = 0; nletter < i && *p != 0; j ++)
   {
    // 한글인지 영문인지 검사
    if(*p < 0x80)
    {
     // 제어문자일 경우 중지
     if(*p <= 0x20)
      break;

     value[cnt][j] = *p;
     p ++;
     nletter ++;
    }
    else
    {
     value[cnt][j++] = *p++;
     value[cnt][j] = *p;
     p ++;
     nletter ++;
    }
/*
    else if(*p >= 0xa1 && *p <= 0xfe) // 한글코드 영역이면
    {
     value[cnt][j++] = *p++;
     value[cnt][j] = *p;
     p ++;
     nletter ++;
    }
*/
   }

   if(nletter == i) // 정상 추출
   {
    value[cnt][j] = 0;
    cnt ++;

    // stem한 term의 갯수가 MAX_N_GRAM_WORD보다 크거나 같으면 종료
    if(cnt >= MAX_N_GRAM_WORD)
     break;
   }

   if(*src >= 0xa1 && *src <= 0xfe)
    src += 2;
   else if(*src < 0x80)
    src ++;
   else
    src ++;
  }
}

return cnt;
}

==============================================================================

Copy&Paste했더니 엉망이네요.

리눅스에서 gnu c를 사용했던 소스입니다만 윈도에서도 잘 돌아가네요.

저작자표시

strtok_r() 함수를 이용한 문자열 파싱

nlogn 2010. 11. 6. 12:16

2010. 11. 6. 12:16

[출처 : http://sp0ngee.tistory.com/51]

어느날 strtok() 함수의 메뉴얼 페이지를 보게 되었는데 다음과 같은 내용이 있었습니다.

버그

이 함수를 사용해서는 안된다. 만일 사용해야 한다면, 다음을 주의하라:

이 함수는 처음 인자를 수정한다.

구분자의 원본은 잃게 된다.

이 함수는 상수 문자열에서는 사용해서는 안된다.

strtok() 함수는 파싱하는 동안 정적 버퍼를 사용한다. 그래서 thread safe가 아니다. 만일 이것이 문제라면 strtok_r() 를 사용해라.

여기서 말하는 thread safe란 것은 여러 thread가 동시에 사용되어도 안전하단 말입니다.
thread safe에 대해서 더 자세히 알고 싶으시면 출처의 링크를 참고하시거나, 구글에서 검색해 보세요.
[ 'thread safe' 출처: http://kldp.org/node/36904 ]

그래서 앞으로 문자열 파싱을 할 일이 생기거든 strtok_r() 함수를 사용해 보려고 합니다.
머리가 좋지 못한 저는 여기에 정리해 놓고, 필요할 때 가져다 쓸려구요...-_ㅜ
혹시 필요하신 분들도 가져다가 사용하시길 바랍니다.

또한, 코드 내용 중에 잘못된 부분이나, 수정하면 더~ 좋은 프로그램이 되겠다라는 곳이 있으면 주저하지 마시고 답변 달아주세요! 다른 분들이 잘못된 정보를 알아가면 안되니까요. ^^

사용 예제를 보기 전에 간단하게 메뉴얼 페이지 내용을 적어봤습니다.

이름

strtok, strtok_r - 문자열에서 토큰들을 뽑아낸다.

사용법

#include <string.h>

char *strtok(char *s, const char *delim);

char *strtok_r(char *s, const char *delim, char **ptrptr);

설명

`토큰`이란 문자열 delim에 속하지 않는 문자들로 이루어진 비어 있지 않은 문자열이며 \0 이나 delim에 있는 문자가 뒤따른다.

strtok() 함수는 문자열 s를 토큰으로 파싱하기 위해 사용된다. strtok()의 첫번째 인자로 s를 주면, 가장 앞에 있는 토큰을 구하고, 그 문자열안의 다음 토큰을 구하고자 할 때에는 첫번째 인자를 NULL로 설정하여야 한다. 각 호출은 다음 토큰에 대한 포인터를 반환하거나 더이상 토큰이 발견되지 않는다면 NULL을 반환한다. 토큰이 구분자로 끝난다면, 이 구분자는 \0 로 겹쳐 쓰여지며 다음 문자에 대한 포인터가 strtok()에 대한 다음 호출을 위해 저장된다. 구분 문자열 delim는 각 호출 시 다를 수 있다.

strtok_r() 함수는 strtok() 와 동일하게 작동한다. 그러나 정적 버퍼를 사용하는 대신에 이 함수는 char * 포인터로 할당된 유저에 대한 포인터를 사용한다. 이 포인터, ptrptr 파라미터는 같은 문자열을 파싱하는 동안 같아야만 한다.

다음은 예제 소스코드 입니다.

#include <stdio.h>
#include <string.h>
#define DELIM "_"
 
int main(void)
{
char buf[] = "My_name_is_ubuntu";
char tmp[4][10] = {};
char *token;
char *ptr[2];
int i = 0;
 
token = strtok_r(buf, DELIM, &ptr[0]);
while( token )
{
strcpy(tmp[i], token);
token = strtok_r(tmp[i], DELIM, &ptr[1]);
while( token )
{
strcpy(tmp[i], token);
token = strtok_r(NULL, DELIM, &ptr[1]);
}
token = strtok_r(NULL, DELIM, &ptr[0]);
i++;
}
 
for(i=0; i<4; i++)
printf("tmp[%d]: %s\n", i, tmp[i]);
 
return 0;
}

실행 결과 입니다.

*참고로 delim은 delimiter의 약자입니다. 단어의 뜻은 '구분 문자'입니다.
이 단어는 자기 테이프 등에서 데이터의 시작(끝)을 나타내는 문자나 기호를 말합니다.

저작자표시

strtok and strtok_r

nlogn 2010. 11. 6. 12:14

2010. 11. 6. 12:14

[출처 : http://www.jamsun2.com/zbxe/?mid=study&document_srl=94602&page=6&sort_index=readed_count&order_type=desc]

char* strtok(char* src, const char* delim)
{
// src, delim 이 NULL 인지, delim 이 "" 인지 체크하는 코드는 생략
char* tok;
static char* next; // 분석을 시작할 위치
if (src != NULL)
next = src;
tok = next;

// boundary condition check
if (*next == '\0')
return NULL;

// 분석 시작
for (; *next != '\0'; ++next)
{
if (*next in delim) // pseudo code
{
*next = '\0';
++next;
break;
}
}

return tok;
}

char* strtok(char* src, const char* delim, char** start)
{
// src, delim 이 NULL 인지, delim 이 "" 인지 체크하는 코드는 생략
char* tok;
  char* next; // 분석을 시작할 위치. static 을 없애고 start 라는 입력
  // 으로 초기화함
if (src != NULL)
next = src;
else
next = *start;

// boundary condition check
if (*next == '\0')
return NULL;

// 분석 시작
tok = next;
for (; *next != '\0'; ++next)
{
if (*next in delim) // pseudo code
{
*next = '\0';
++next;
break;
}
}

  *start = next;
return tok;
}

저작자표시

strtok, strsep와 같은 토큰 추출 프로그램

nlogn 2010. 11. 6. 12:10

2010. 11. 6. 12:10

[출처 : http://www.joinc.co.kr/modules/moniwiki/wiki.php/Code/C/token]

사용방법

char *token(char *str, char *src, const char* sep);

str : 토큰 분리를 위한 원본 문자열
src : 토큰 분리후 다음 문자열을 가르키는 포인터
sep : 토큰
return : 더이상 토큰이 없거나 '\0'을 만나면

#include "token.h" 
 
int main() { 
   char src[20]; 
   char str[20]; 
   char* next = &src[0]; 
   strcpy(src, "ab1de12eoqd12dq"); 
   while(next = token(str, next, "12")) { 
      printf("%s\n", str); 
   } 
   return(0); 
}

코드

#include <stdio.h> 
 
char* token(char* str, char* src, const char* sep) { 
   int i = 0; 
   if (*src == '\0') return(NULL); 
   while (1) { 
      if (sep[i] == '\0') { 
         str -= strlen(sep); 
         break; 
      } else if (*src == sep[i]) { 
         i++; 
      } else i = 0; 
      if (*src == '\0') break; 
      *str++ = *src++; 
   } 
   *str = '\0'; 
   return(src); 
}