[Data Structure] 스레드 이진 트리

 스레드 이진 트리라는 것은 무척이나 생소한 개념이다. 허나 이 개념이 등장한 이유는 아주 심플하다. 여태 우리가 배웠던 순회라는 것은 모두 Stack를 사용했기 때문에 효율적이지 않다. 그 노드 수가 많아질 수록 시간이 오래 걸리기 때문이다.
 이러한 점을 해결하고자 나온 개념이 바로 스레드(Thread), 실이다. 하나의 노드를 순회하고 나서 순회 타입에 맞는 다음 노드를 연결시켜놓은 것을 스레드라고 한다. 그래서 이러한 트리를 Thread Binary Tree라고도 부른다.
 여기서는 간단히 개념만을 살펴보기 위해서 중위 순회시 적용된 스레드의 코드만을 볼 것이다. 중위 순회에서는 왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리 순서로 순회를 하게 된다. 왼쪽 노드는 부모를 가리키면 되고 오른쪽 노드는 부모의 부모 노드를 가리키면 된다. 이 말이 어려울 수도 있는데 그냥 코드를 보면서 찬찬히 생각해보면 아주 쉽다.

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

#define FALSE 0
#define TRUE 1

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
    int is_thread;
} TreeNode;

// Node의 중위 후속자를 반환하는 함수이다. 이때
// 중위 후속자란 중위 순회를 할 때 해당 노드의 다음 노드(후속자)를 의미한다.
TreeNode* find_succesor(TreeNode *p){
    // q는 p의 오른쪽 포인터.
    TreeNode *q = (TreeNode*) p->right;
    // 만약 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 변환
    if (q == NULL || p->is_thread == TRUE) {
        // 오른쪽 포인터가 null일 경우는 완전히 모든 순회가 끝났을 때
        return q;
    }
    while (q->left != NULL) {
        q = (TreeNode*) q->left;
    }
    return q;
}

void thread_inorder(TreeNode *t){
    TreeNode *q;
    q=t;
    
    // 중위 순회이기 때문에 가장 먼저 맨 왼쪽 단말 노드로 향한다.
    while (q->left != NULL) q = (TreeNode*) q->left;
    
    do {
        printf("%c ",q->data);
        q = find_succesor(q); // 중위 순회시 다음 노드를 찾아 준다.
    } while (q);
}

int main(){
    TreeNode n1 = {'A',NULL,NULL,TRUE}; // threaded
    TreeNode n2 = {'B',NULL,NULL,TRUE}; // threaded
    TreeNode n3 = {'C',&n1,&n2,FALSE};
    TreeNode n4 = {'D',NULL,NULL,TRUE}; // threaded
    TreeNode n5 = {'E',NULL,NULL,FALSE};
    TreeNode n6 = {'F',&n4,&n5,FALSE};
    TreeNode n7 = {'G',&n3,&n6,FALSE};
    TreeNode *exp = &n7;
    
    n1.right = &n3; // A -> C
    n2.right = &n7; // B -> G
    n4.right = &n6; // D -> F
    
    thread_inorder(exp);
    printf("\n");
    return 0;
}

친절하게도 주석도 달아놨다 :D

[Java] 객체 비교

Java에서 객체를 비교할 때에는 ‘==‘ 연산자를 써야할까, ‘equals’ 메서드를 써야할까?

결론부터 말하자면 객체비교시 ‘==‘ 연산자는 각 객체의 주소 값을 비교한다. 반면 ‘equals’ 메서드는 객체 내부의 멤버들을 비교해서 같은지를 판단해준다. 

(커스텀 객체의 경우에는 equals 메서드를 오버라이딩 해야함)

다음의 코드를 보면서 곰곰히 살펴보자.

public static void main(String[] args) {

String s1 = "Hello";

String s2 = "Hello";

String s3 = new String("Hello");

String s4 = new String("Hello");

if(s1==s2) print("s1==s2");

if(s1.equals(s2)) print(“s1.equals(s2)”);

if(s3==s4) print("s3==s4");

if(s3.equals(s4)) print(“s3.equal(s4)");

if(s1==s3) print("s1==s3");

if(s1.equals(s3)) print("s1.equals(s3)");

}

public static void print(String what){

System.out.println(what);

}

 우선 s1과 s2를 비교해보자.

if(s1==s2) print("s1==s2");

if(s1.equals(s2)) print(“s1.equals(s2)");

이때 s1과 s2는 객체가 아니라 primitive 한 String이다. 즉 상수와 같다. 그러므로 이러한 String에 대해서는 ‘==‘으로 비교하더라도 내용을 비교하는데 아무 문제가 없다. 또한 ‘equals’ 메서드도 문제 없이 출력된다.  

이번엔 s3와 s4를 비교해보자.

if(s3==s4) print("s3==s4");

if(s3.equals(s4)) print(“s3.equal(s4)");

s3와 s4는 new String을 통해 객체화 시켰다. 아까 ‘==‘는 주소값을 비교한다고 했다. 그런데 new를 통해 생성된 객체들은 모두 다른 주소값을 가진다. 그러니 아무리 내용이 같더라도 ‘==‘비교로는 객체 내용이 같은지 판단할 수가 없다. 그래서 s3==s4에서 걸리지 않는것이다. 다만 equals 메서드는 객체 내부의 멤버를 비교하기 때문에 s3.equals(s4)가 true가 된다.

[Data Structure] 이진 트리 노드 개수 세기 (Counting TreeNode)

 요즘 들어서 하는 일이 많아져서 조금씩 밖에 못하고 있다. 이정도는 금방하고 넘어가야 하는데 조금 게을러졌다. 여튼 잡설은 여기까지 하고 ..

 이번에 볼 내용은 이진 트리에서 노드의 개수를 세는 방법이다. 어차피 현재 재귀 형식을 사용하기 때문에 직관적이고 쉽다. 또한 두번째로 단말 노드를 세는 메서드가 추가되어 있다. 단말 노드는 알다시피 자식 노드가 없는 마지막 노드를 의미한다.

 코드를 보자.

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

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 노드 개수 세는 메서드
int get_node_count(TreeNode *root){
    if (root == NULL) return 0;
    int result = 1;
    result += get_node_count((TreeNode*)root->left) + get_node_count((TreeNode*)root->right);
    return result;
} 

// 단말 노드 개수 세는 메서드
int get_leaf_count(TreeNode *root){
    int result = 0;
    if (root == NULL) {
        return 0;
    } else if (root->left == NULL && root->right == NULL){
        return 1;
    }
    result += get_leaf_count((TreeNode*)root->left) + get_leaf_count((TreeNode*)root->right);
    return result;
} 

int main(){
    TreeNode n6 = {300,NULL,NULL};
    TreeNode n5 = {500,NULL,NULL};
    TreeNode n4 = {200,&n6 ,NULL};
    TreeNode n3 = {100,&n4 ,&n5 };
    TreeNode n2 = {50 ,NULL,NULL};
    TreeNode n1 = {0  ,&n2 ,&n3 };
    printf("전체 노드의 수 : %d\n",get_node_count(&n1));
    printf("자식 노드가 없는 노드의 수 : %d\n",get_leaf_count(&n1));
    return 0;
}

[Data Structure] Binary Tree를 이용한 디렉토리 용량 계산

 이번에도 아주 단순한 코드를 소개한다. 이진트리를 활용해서 디렉토리의 용량을 계산해보자. 사실 말이 안되는게 하위폴더는 최대 2개다. 왜냐하면 우리는 이진트리를 공부해야 하니까.

 폴더의 용량을 계산하기 위해서는 하위 폴더의 모든 용량이 이미 계산되고 자신의 용량까지 더해줘야한다. 그래서 후위(post order) 순회를 사용한다. 후위 순회 코드랑 아주 유사하다. 다만 재귀적으로 폴더의 용량을 리턴한다는 점만 다르다. 원리는 똑같으니 더 이상의 설명은 생략한다.

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

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int calc_direc_size(TreeNode *root){
    if (root->left == NULL && root->right == NULL)
        return root->data;
    int left = calc_direc_size((TreeNode*)root->left);
    int right = calc_direc_size((TreeNode*)root->right);
    return root->data + left + right;
}

int main(){
    TreeNode n5 = {500,NULL,NULL};
    TreeNode n4 = {200,NULL,NULL};
    TreeNode n3 = {100,&n4 ,&n5 };
    TreeNode n2 = {50 ,NULL,NULL};
    TreeNode n1 = {0  ,&n2 ,&n3 };
    
    printf("디렉토리의 크기 : %d\n",calc_direc_size(&n1));
    return 0;
}

[Data Structure] Tree를 이용한 수식 계산

 우리는 예전에 스택을 이용해서 중위(infix), 후위(postfix) 방식의 수식 계산을 다뤘었다. 이것을 트리를 이용해서 할 수도 있다. 트리를 preorder, inorder, postorder 방식으로 traversal 하는 것과 같다.

 여기서는 트리를 이용해 후위 방식으로 수식을 처리해 볼 것이다. 여기서 트리는 피연산자는 항상 단말노드에 존재하며 연산자는 비단말노드로 구성된다.

 이러한 수식 계산을 위해 트리를 구성한 후에 재귀를 이용해 탐색을 한다. 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 탐색하고 그 값을 가지고 계산을 해주는 식이다. 여기서 리턴값들이 0 인 것은 수식이기 때문이다.

 코드를 보도록 하자. 금방 이해가 갈 것이다.

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

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int evaluate(TreeNode *root){
    // 재귀 호출 방식을 사용한다
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL)
        return root->data;
    int op1 = evaluate((TreeNode*)root->left);
    int op2 = evaluate((TreeNode*)root->right);
    switch (root->data) {
        case '+':
            return op1+op2;
        case '-':
            return op1-op2;
        case '*':
            return op1*op2;
        case '/':
            return op1/op2;
    }
    return 0;
}

int main(){
    TreeNode n1 = {1,NULL,NULL};
    TreeNode n2 = {4,NULL,NULL};
    TreeNode n3 = {'*',&n1,&n2};
    TreeNode n4 = {16,NULL,NULL};
    TreeNode n5 = {25,NULL,NULL};
    TreeNode n6 = {'+',&n4,&n5};
    TreeNode n7 = {'+',&n3,&n6};
    TreeNode *exp = &n7;
    
    printf("%d\n",evaluate(exp));
    return 0;
}

[Data Structure] Level Order

 저번 포스트에 이어 Binary Tree 순회에 대해 이어나가도록 하자. 이번에 다룰 순회방법은 Level Order이다. Level은 이미 이야기했다시피 이진 트리에서 계층을 나타내는 숫자다. 그렇다면 레벨 순회란 무엇일까.

 레벨 순회란 말그대로 레벨 별로 순회를 한다는 의미다. Level 1은 Root 노드를 의미하고 Level 2는 그 다음 계층의 노드들을 의미한다. 이렇게 레벨 별로 노드를 탐색하는데 여기서 제일 왼쪽편에 있는 노드부터 차례대로 탐색하게 된다.

 이 순회는 'Queue'가 사용된다. 노드를 참조할 때 자식 노드가 존재하게 되면 그 노드들을 Queue에 넣는다. 그리고 다시 큐에서 꺼내었을 때 그 노드값을 참조하고 다시 그 노드의 자식들을 큐에 집어넣는다. 이렇게 되면 레벨 Ordering이 된다.

 말보다 코드가 백번 낫다. 코드를 보자.

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

#define MAX_QUEUE_SIZE 100

typedef int element;
typedef struct {
    element data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

typedef struct {
    TreeNode queue[MAX_QUEUE_SIZE];
    int front;
    int rear;
} QueueType;

void init(QueueType *q){
    q->front = q->rear = 0;
}

void error(char *message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}

int is_empty(QueueType *q){
    return q->front == q->rear;
}

int is_full(QueueType *q){
    return (q->rear+1) % MAX_QUEUE_SIZE == q->front;
}

void enqueue(QueueType *q, TreeNode *item){
    if (is_full(q)) {
        error("q is full");
    }
    q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = *item;
}

TreeNode* dequeue(QueueType *q){
    if (is_empty(q)) {
        error("q is full");
    }
    q->front = (q->front+1) % MAX_QUEUE_SIZE;
    return &q->queue[q->front];
}

TreeNode* peek(QueueType *q){
    if (is_empty(q)) {
        error("q is empty");
    }
    return &q->queue[q->front];
}

void level_order(TreeNode *root){
    QueueType q;
    init(&q);
    TreeNode *tmp;
    enqueue(&q,root);
    while (tmp != NULL) {
        tmp = dequeue(&q);
        printf("%d ",tmp->data);
        
        if(tmp->left != NULL) enqueue(&q, (TreeNode*) tmp->left);
        if(tmp->right != NULL) enqueue(&q, (TreeNode*) tmp->right);
    }
}

int main(){
    TreeNode n1 = {1, NULL, NULL};
    TreeNode n2 = {4, (struct TreeNode*)&n1, NULL};
    TreeNode n3 = {16, NULL, NULL};
    TreeNode n4 = {25, NULL, NULL};
    TreeNode n5 = {20, (struct TreeNode*)&n3, (struct TreeNode*)&n4};
    TreeNode n6 = {15, (struct TreeNode*)&n2, (struct TreeNode*)&n5};
    TreeNode *root = &n6;
    level_order(root);
    
    return 0;
}

별로 어려운건 없다

[영화] 변호인 리뷰 (스포 없음)

 [스포없음 :D] 요즘 한창 영화 때문에 인터넷이 난리다. 그 영화가 바로 '변호인'이다. 왜 이렇게 영화 하나 때문에 난리일까. 바로 '변호인'이 대한민국 정치 이슈중 가장 뜨거운 감자인 '故노무현 전 대통령'의 이야기를 다뤘기 때문이다. 그렇다, 이 영화의 주인공은 바로 '故노무현 전 대통령'이다.

 사실 내가 TV를 좋아하지 않아서 그런지 변호인이라는 영화에 대해서 아무것도 모른 상태로 영화를 보게 되었다. 그러나 본 지 얼마 되지 않아 뭔가 느낌이 이상했다. 바로 주인공인 '송우석'이 고졸 변호사였기 때문이다. 어디선가 많이 들어본 것 같지 않은가? 고졸 변호사. 게다가 영화 시작시 넌지시 던졌던 '실화를 바탕으로 한 영화'... 

 다만, 묘했던 건 포스터나 광고에서는 특별히 '故노무현 전 대통령'의 냄새가 나지 않았다는 점이다. 아무래도 영화사 측은 최대한 정치적인 요소에 대해 언급하는 것을 피하는 모양새다. 아무래도 영화가 정치적인 이유로만 언급되는 것이 부담스러웠겠지. 

(1980년대 초 부산을 배경으로 세무 변호사 송우석의 인생을 송두리째 바꾼 다섯 번의 공판에 대한 이야기를 소재로 하고 있다. 고 노 전 대통령이 인권 변호사로 활동했을 당시를 영화화한 것이다.)

 하지만 아니나 다를까 이 영화는 '인간 노무현'을 이야기로 담음과 동시에 스스로 뜨거운 감자가 되었다. 그 동안 몇가지 일들이 있었다.

1. 일베의 '별점 테러' 공격

[참고 : 변호인, 개봉 전부터 공방 치열... '일베 회원 결집']

 아시다시피 일베는 한국 내 극우파계열의 사람들이 찾는 사이트로 알려져 있다.(사실 이 말이 맞는지 확신할 수 없다.. 근본은 극우이지만 하는 꼴을 보면 자극적인 기삿거리를 찾는 불나방 같다.) 이 사람들이 결집을 해서 '변호인'의 평점을 내려깎은 것이다. 

 이건 우파로서 해야하는 일이 아니라 그냥 유치한 짓이다. 영화는 영화관에서 사람들에 의해 평가 받아야 하는 것이지 자신과 이념 색깔이 다른 영화라고 의도적이고 집단적으로 이러한 결과를 만들어놓는 것은 정말 비겁한 짓이다. 이 녀석들은 입에 걸레를 물었는지 말 하나하나 더러운 냄새가 난다.

2. '송강호 죽이기' 검색어 

 갑자기 '송강호 죽이기'라는 검색어가 모 검색포털의 상위 검색어로 등극했다. 해당 키워드로 검색을 해보면 얼추 그 내용이 짐작이 간다. '故노무현 전 대통령'역을 맡은 송강호씨에게 정부가 압력을 가하고 있다는 것이다. 

[참고 : 송강호 죽이기 시작?.. "차기작 섭외 끊겼다" 발언]

 위의 사이트는 쿠키일보에서 올라왔던 기사를 캡쳐떠서 올려놓은 게시물이다. 원래 기사는 현재 삭제된 상태로 접속이 불가하다. 그런데 이 부분은 사실 그 진실성이 의심된다. 기사 자체가 엉터리였기 때문에 기사가 삭제된 것일 수도 있으며 사실 송강호가 저런 말을 했다는 것도 의심스럽다. 왜냐하면 그는 이번 해에 가장 큰 대박을 터뜨린 영화의 주인공이 아닌가? 그의 티켓파워는 이정도로 무너질 것으로 보이지는 않는다.  또한 정말로 저런 말을 했다면 왜 쿠키일보에서만 이런 기사를 찾을 수 있을까. 여튼 이 주제는 온통 추측 뿐이라 사실을 알 수가 없다. 

3. 영화 '변호인'의 흥행

[참고 : 노무현 효과? '변호인'의 흥행돌풍, 그 이유는?]

일베의 별점 테러에도 불구하고 영화 변호인은 그 기세가 만만치 않다. 현재 '변호인'의 별점은 8점대로 회복되었으며 빠른 속도로 별점이 상승하고 있다.

네이버 영화 '변호인' 평점 8.26. 현재 시각 2013년 12워 23일 새벽 2시 26분

 혹자는 현재 '변호인'의 흥행 이유를 '故노무현 효과'에서 찾을 수도 있겠다. 물론 이러한 면도 입소문을 타는데 주요했을 것이라 예상은 든다. 다만 직접 영화관에서 본 입장에서 말하자면 ..

 이 영화 생각보다 정말 재밌다 :D 송강호 특유의 그 찰진 연기와 영화 자체의 탄탄한 시나리오 구성 덕분에 보는 내내 몰입을 했다. 특히나 영화 속에서 최대 악역으로 등장하는 차동영 경감과의 한판 신은 긴장의 연속이었다. 그 팽팽한 긴장감 속에 송우석의 외침은 감동을 이끌어낸다.

 이 리뷰를 그 외침과 영화와 관련된 실제 '故노무현 전 대통령'의 사진으로 끝을 내겠다.  (감독이 이런 사진을 바탕으로 촬영을 했구나 하는 사실을 영화를 보신 분들은 느낄 것이다:D)

 

"대한민국 주권은 국민에게 있고

모든 권력은 국민으로부터 나온다.

국가란 국민이다"

[Data Structure] 이진 트리의 순회

 이진 트리의 순회(traversal)에는 전위(preorder), 중위(inorder), 후위(postorder) 세 가지 방법이 있다. 이 세가지 방법의 차이는 말 그대로 순서(order)의 차이다. 무슨 말을 하는 것인지 그림으로 보도록 하자.

 이진트리의 노드타입에는 위와 같이 부모, 왼쪽 자식, 오른쪽 자식 이렇게 셋으로 나눠진다. 여기서 순서라는 것은 어떤 노드를 먼저 참조할 것인가에 대한 문제다.

1. preorder (전위 순회)

 순서는 먼저 parent -> left -> right의 순으로 참조한다. pre- 라는 접두사는 먼저의 라는 의미를 가지는데 이러한 이름에 걸맞게 parent가 먼저 참조된다는 특징이 있다.

2. inorder (중위 순회)

 순서는 left -> parent -> right 로 이어진다. 마찬가지로 in-은 중간의 라는 의미이므로 parent 노드가 2번째로 참조된다.

3. postorder

 이쯤되면 감이 온다. left -> right -> parent 로 이어진다. post-는 나중의 라는 의미를 가지므로 parent 노드가 가장 나중에 참조된다.

 아래의 코드는 위의 트리를 표현하고 있다.

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

typedef int element;
typedef struct {
    element data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 전위 순회
void preorder(TreeNode *root){
    if (root == NULL)
        return;
    printf("%d ",root->data);
    preorder((TreeNode*)root->left);
    preorder((TreeNode*)root->right);
}

// 중위 순회
void inorder(TreeNode *root){
    if (root == NULL)
        return;
    inorder((TreeNode*)root->left);
    printf("%d ",root->data);
    inorder((TreeNode*)root->right);
}

// 후위 순회
void postorder(TreeNode *root){
    if (root == NULL)
        return;
    postorder((TreeNode*)root->left);
    postorder((TreeNode*)root->right);
    printf("%d ",root->data);
}

TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {4, (struct TreeNode*)&n1, NULL};
TreeNode n3 = {16, NULL, NULL};
TreeNode n4 = {25, NULL, NULL};
TreeNode n5 = {20, (struct TreeNode*)&n3, (struct TreeNode*)&n4};
TreeNode n6 = {15, (struct TreeNode*)&n2, (struct TreeNode*)&n5};
TreeNode *root = &n6;

int main(){
    printf("inorder : ");
    inorder(root);
    printf("\npreorder : ");
    preorder(root);
    printf("\npostorder : ");
    postorder(root);
    printf("\n");
    return 0;
}

 recursive 한 코드이므로 이해하기가 아주 쉽다. 더 이상의 설명은 생략한다 ㄱ-

[Data Structure] Binary Tree Using Linked List

 별 다르게 언급할 것이 없다. 트리 노드를 구조체로 정의하였고 노드 구조체에는 데이터와 왼쪽, 오른쪽 노드를 지칭하는 포인터가 존재한다.

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

typedef struct {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;


int main(){
    TreeNode *n1, *n2, *n3;
    n1 = (TreeNode*)malloc(sizeof(TreeNode));
    n2 = (TreeNode*)malloc(sizeof(TreeNode));
    n3 = (TreeNode*)malloc(sizeof(TreeNode));

    n1->data = 10;
    n1->left = (struct TreeNode*) n2;
    n1->right = (struct TreeNode*) n3;
    
    n2->data = 20;
    n2->left = NULL;
    n2->right = NULL;
    
    n3->data = 30;
    n3->left = NULL;
    n3->right = NULL;
    
    return 0;
}

[Android] Mac 에서 Android NDK 환경 구축 (Eclipse)

1. X-Code를 설치한다.

2. Mac Port를 설치한다. 홈페이지 오른쪽 상단에 Download가 있고 들어가면 각 mac 버전에 맞게 분류되어 있다.

3. 터미널에서 다음 두 명령어를 실행한다.

sudo port selfupdate

sudo port install gmake gawk

 그런데 2번째 터미널 명령어에서 에러가 났다. 찾아보니 X-Code 내부에 있는 Preference메뉴에서 Command Lint Tools를 설치해야 된단다. 

4. 구글 개발자 사이트에서 맥 OS용 Android-NDK를 다운 받아서 압축을 풀어놓는다.

5. 터미널에서 vi .bash_profile 을 쳐서 경로 추가를 해줘야 한다. 경로 추가를 할 때 또 export를 해줄 필요는 없고 이미 추가된 경로에 : 를 붙여서 아까 ndk를 다운받아 푼 경로를 추가시켜 준다.

예를 들어 나는 다음과 같았다.

export PATH=${PATH}:/Users/cdi1318/Documents/eclipse/android-sdk-macosx/platform-tools:/Users/cdi1318/Documents/eclipse/android-ndk-r8b/

6. 터미널에서 source .bash_profile를 쳐준다. 끝.

[Android] Thread Handler 다루기

 Thread에 대한 기본적인 지식은 Java 기본서를 참고하거나 나의 이전 포스트인 [Java] Thread의 개념을 참고하자. 지금 Android Thread를 공부하는 이유는 Handler 사용방식에 대해서 깊게 파기 위해서이다. 

 Android Handler가 어떤 역할을 하는지 잘 그려놓은 사이트가 있어서 가져왔다. 이 포스트를 모두 보고 나면 어느 정도 이해가 갈 것이다. 여기서 Looper에 관해서는 다루지 않는데 궁금하신 분은 출처를 남겨놨으니 가서 보시면 된다 :D

출처 : http://ensider.tistory.com/5

 Handler는 왜 필요할까? 바로 쓰레드간의 커뮤니케이션을 위해서다. 예를 들어 생각해보면, 화면 UI를 담당하는 쓰레드가 존재하고, 연산 작업을 진행중인 쓰레드가 존재한다고 하자. 이때 연산 작업을 끝낸 쓰레드가 그 결과 값을 UI에 적용시키려고 UI를 건드리게 된다. 그러면 이미 UI를 담당하는 쓰레드가 있는데 그 녀석이 무엇을 하는지도 모르는데 그 UI를 건드리게 되는 것이다. 어떤 상황이 될지 알 수 없게 된다. 그래서 android는 그러한 상황을 Sorry! 로 표현하며 에러를 뿜어낸다. 그래서 Handler가 필요하다. 쓰레드 간에 커뮤니케이션을 위해!

  핸들러는 스레드간에 메시지나 Runnable 객체를 통해 메시지를 주고 받는다. 핸들러는 항상 하나의 스레드에 소속된다. 자신을 생성하는 스레드에 결합되어 그 쓰레드의 메시지 큐를 통해 다른 쓰레드와 통신하게 된다. 보통은 다른 쓰레드로부터 전달되는 메시지를 수신하지만 자기 자신이 보낸 메시지도 물론 받을 수 있다. 만약 메시지가 핸들러에게 넘어오게 되면 handleMessage (Message msg)메서드가 호출된다. 여기서 인수로 msg를 받게 되는데 이놈은 통신 내용을 저장하고 있는 하나의 객체다. 여러 개의 필드를 가지는게 특징이다.  

int what : 메시지의 의미를 설명한다.

int arg1, int arg2 : 메시지의 추가 정보

Object obj : 정수만으로 메시지를 기술 할 수 없을 때 쓰는 필드다.

Messenger replyTo : 메시지에 대한 응답을 받을 객체를 지정한다.

 메시지를 보내는 쪽에서는 내용을 Message 객체에 저장하여 핸들러로 전송하는데, 다음의 메서드를 살펴보자.

boolean Handler.sendEmptyMessage (int what) 

위에서 말한 what값만을 전달할 때 ‘간단’하게 사용한다.

boolean Handler.sendMessage(Message msg)

좀 더 복잡한 정보를 보낼 때 사용한다. 메시지는 큐에 순서대로 쌓여 처리된다.

boolean sendMessageAtFrontOfQueue (Message msg)

위의 메서드와 동일하지만 이 메시드를 통해 보내는 메시지는 Queue의 가장 앞에 위치하게 되어 먼저 처리되게 된다.

 메시지를 boolean post (Runnable r) 메서드를 이용해서 보낼 수 있다. 이 Runnable이라는 객체는 작업을 직접 수행하는 객체다. 핸들러로 Runnable 객체를 보내면 run() 메서드가 실행된다. 간단한 작업의 경우 메시지를 보내는 것보다 Runnable을 보내는 것이 더욱 간단하다. 이렇게 쓰이게 되면 handler 쪽에서 수신된 메시지를 처리하는 handleMessage를 굳이 만들 필요가 없다. 

 문제는 Activity와 Thread가 분리 될 경우다. 쓰레드에게 보낼 핸들러를 전달해야 하고, 멤버들을 공유할 수 없기에 핸들러에게 메시지를 보낼 때도 작업 내용을 좀 더 구체적으로 기술해야한다. 이 때에는 Thread에 생성자를 만들어서 핸들러를 받아와야한다. 그런 후에 핸들러에게 변경된 값을 전달 해줘야 한다. 다음의 예제는 아주 전형적인 사용방법에 대해서 기술하고 있으므로 필요할 때 가져다 쓰자.

public class MainActivity extends Activity {

int mMainValue = 0;

TextView mMainText;

TextView mBackText;

BackThread mThread;

    @Override

    public void onCreate(Bundle savedInstanceState) {

        super.onCreate(savedInstanceState);

        setContentView(R.layout.activity_main);

        

        mMainText = (TextView) findViewById(R.id.mainvalue);

        mBackText = (TextView) findViewById(R.id.backvalue);

        Button btn = (Button) findViewById(R.id.increase);

        btn.setOnClickListener(new Button.OnClickListener() {

@Override

public void onClick(View v) {

mMainValue ++;

mMainText.setText("MainValue : "+mMainValue);

}

});

        mThread = new BackThread(mHandler);

        mThread.setDaemon(true);

        mThread.start();

    }

    Handler mHandler = new Handler(){

    public void handleMessage(android.os.Message msg) {

    if(msg.what==0){

    mBackText.setText("BackValue : "+msg.arg1);

    }

    };

    };

}

class BackThread extends Thread {

int mBackValue = 0;

Handler mHandler;

public BackThread(Handler handler) {

mHandler=handler;

}

@Override

public void run() {

while(true){

mBackValue ++;

Message msg = Message.obtain();

msg.what = 0;

msg.arg1 = mBackValue;

mHandler.sendMessage(msg);

try {

Thread.sleep(1000);

} catch (InterruptedException e) {

e.printStackTrace();

}

}

}

}

 여기서 obtain 이라는 메서드가 나왔는데 쓰레드간에 메시지를 주고 받기 위해 매번 new를 이용해서 메시지를 생성하게 되면 메모리가 많이 소모되고 느려진다.(Message 객체는 static이다) 그래서 시스템에 메시지 풀이라는 것이 있다. 시스템의 메시지 풀에서 메시지 객체를 꺼낼 때는 다음 메서드를 사용한다.

static Message obtain([Message orig]);

static Message obtain(Handler h, int what, int arg1, int arg2, Object obj);

void recycle();

 obtain 메서드는 메시지 풀에서 비슷한 메시지를 꺼내 재사용하게 해준다. 위의 예제에서는 인수 없이 obtain()을 사용했는데 빈 메시지 객체 하나를 꺼내주게 된다. 이것은 new 연산자로 생성하는 것보다 빠른 방법이다. 꺼낼때 인수들을 (2번) 지정해주게 되면 메시지 객체를 꺼내서 값을 대입해 주기도 한다. 

 반면 recycle() 메서드는 사용한 메시지를 풀에 다시 집어넣는데 이후 부터는 시스템에서 관리하게 되므로 더 이상 건드려서는 안된다.

[Java] Thread 의 개념

 Thread란 실행 중인 프로그램을 의미한다. 둘 이상의 쓰레드가 실행 될 때 멀티 쓰레드라고 부른다. 아래의 그림은 오늘 포스트 할 내용을 함축적으로 담고 있다. 글을 모두 읽고 나서 보게 되면 이해가 빠를 것이다.

 쓰레드를 구현하는 방법에는 2가지가 있다. 첫번째가 Thread를 상속 받는 것. 두번째가 Runnable Interface를 구현하는 방법이다. 상속을 받던지 구현을 하던지 run()이라는 메서드를 오버라이드 해야만 한다. 차이 점이라면 runnable은 자신을 담아줄 thread가 필요하다는 점이다. thread 상속시에는 그 자체로 하나의 쓰레드가 된다. 

 재밌는 점은 쓰레드를 실행시킬 때에는 start() 메서드를 사용해야 한다는 점이다. 왜 run()이 아니라 start()인가? 사실 start()라는 것은 run()을 실행시킬 장소를 마련해 주는 메서드다. 이 말은 start()를 실행시키면 호출스택이라고 해서 run()을 위한 환경을 구성해주는 역할을 한다. 

 쓰레드는 우선순위 지정이 가능하다. thread.setPriority(우선순위 점수); 를 이용한다. 각각의 쓰레드에 우선순위를 지정해주지 않으면 모두가 같은 우선순위를 가지기 때문에 같은 정도의 시간을 소요하게 된다.

 쓰레드 그룹이라는 것은 보안상의 이유로 탄생했다. 마치 폴더와 같은 개념인데 같은 폴더이거나 하위 폴더에 있는 쓰레드는 변경할 수 있지만 상위 쓰레드는 건드릴 수 없다. 간단하게 ThreadGroup를 사용하면 된다.

 데몬 쓰레드는 일반 쓰레드를 돕는 역할을 한다. 그래서 일반쓰레드가 모두 종료되면 데몬 쓰레드는 자동으로 종료된다. 사실 데몬쓰레드는 CallBack 메서드와 아주 흡사하다. 이놈은 무한 루프와 조건문을 이용해서 실행 후 대기하고 있다가 특정 조건이 만족되면 작업을 수행한다. 사용방법은 쓰레드를 하나 만들어서 setDaemon(boolean on)을 이용하면 데몬 쓰레드로 변경 시킬 수 있다. 데몬 쓰레드는 주쓰레드가 죽으면 같이 죽어버린다. 안드로이드에서 이러한 것을 자주 사용한다.

 사실 쓰레드 프로그래밍이 어려운 이유는 쓰레드들을 실행 제어하는 부분이 까다롭기 때문이다. 여기서 쓰레드 메서드를 이해하는 것이 중요하다. 메서드들은 다음과 같다.

 1. join()

 join()은 그 쓰레드가 끝날 때 까지 다른 쓰레드들을 모두 대기시킨다. 예를 들면 th1.start -> th1.join -> th2.start 를 하면 th1이 종료될때까지 th2는 실행되지 않는다. 

 2. sleep()

 sleep()은 static 멤버다. 이 말은 th1.sleep()을 하건, th2.sleep()을 하건 슬립하는 그 순간은 동일하다는 것이다. 그 외에 yeild() 나 stop(), suspend(), interrupted() 같은 걸 어떻게 사용하는지 예제를 통해 연습하자. 필요할때 가져다 써도 무방하지 싶다.

class MyThreadEx19 implements Runnable{

boolean suspended = false;

boolean stopped = false;

Thread th;

public MyThreadEx19(String name) {

th = new Thread(this, name);

}

@Override

public void run() {

String name = Thread.currentThread().getName();

while(!stopped){

if(!suspended){

System.out.println(name);

try {

Thread.sleep(1000);

} catch (InterruptedException e) {

System.out.println(name +" - interrupted");

}

}else{

Thread.yield();

}

}

System.out.println(name + " - stopped");

}

public void suspend(){

suspended = true;

th.interrupt();

System.out.println("interrupted() in suspend()");

}

public void resume(){

suspended = false;

}

public void stop(){

stopped = true;

th.interrupt();

System.out.println("interrupted() in stop()");

}

public void start(){

th.start();

}

}

 쓰레드는 동기화는 성능에 큰 영향을 미친다. 동기화를 예를 들어 설명하자면 svn에서 하나의 클래스 파일을 오직 한명이 건드리게 해야하는 방식과 같다. 만약에 한명이 파일을 건드리고 있는데 다른 사람이 또 그 파일을 건드리게 되면 데이터가 유실되거나 생각지 않은 방향으로 변경되게 될 것이다. 동기화는 다음과 같은 방법이 있다.

 synchronized은 해당 작업의 공유데이터에 lock을 거는 방식이다. synchronized는 객체에 lock을 걸거나 메서드에 lock을 걸 수 있다. 이 락이 걸린 데이터를 쓰레드 하나가 사용하게 되면 그 synchronized가 걸린 블록이 끝나기 전까지는 lock이 걸려 있게 된다.

 그런데 여기서 의문이 하나 생긴다. 두개의 쓰레드가 lock이 걸린 데이터를 써야 한다면, 하나의 쓰레드가 먼저 데이터를 가져가고 두번째 쓰레드는 첫번째 쓰레드의 작업이 끝날때까지 기다려야만 한다. 이 문제를 어떻게 해결할 것인가?

 이러한 비효율을 개선하기 위해서 wait()와 notify(), notifyAll()를 사용한다. 이 메서드들은 synchronized 블록 내에서만 사용된다. 예들 들어보자.

 하나의 쓰레드가 synchronized 메서드를 이용하는 중에 특정 조건이 되면 wait()가 걸리게 된다. 그러면 그 쓰레드는 waiting pool이라는 대기실에서 잠을 자게 되고, 이 쓰레드가 잡고 있던 synchronized 메서드는 lock이 풀리게 되어 다른 쓰레드가 사용하게 된다. 나중에 필요할 때 notify()를 사용해 깨울 수 있다. 그런데 notify()는 특정 쓰레드를 깨우는게 아니라 우선순위가 높은 쓰레드를 깨우기 때문에 어떤 쓰레드가 깨어날 지 알 수 없다. 그래서 notifyAll()을 사용해서 모든 쓰레드를 깨워놓고 JVM의 쓰레드 스케줄링에 의해서 처리되도록 한다.(그것이 안전)