'분류없음'에 해당되는 글 224건

2011.05.04 레드 블랙 트리
2011.04.10 11.4.10 ... 여러 생각들..
2011.04.03 <input> cin(), get(), getline() 함수 차이.
2011.03.25 C++ Preprocessor: Always Assert Your Code Is Right
2011.03.22 [펌] 프로그래밍 공부법
2011.03.14 ostream/istream
2011.03.14 연산자 오버로딩
2011.03.09 Skip list _ wikipedia
2011.03.09 atal error C1083: 포함 파일을 열 수 없습니다. 'fstream.h': No such file or directory 1
2011.03.09 C++ 에서 setw(int num) 함수를 이용하여 깔끔하게 출력하기!

2011. 5. 4. 17:17

레드 블랙 트리

출처 : 위키페디아(http://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC)

레드-블랙 트리는 내부적으로 균형을 이룬(self-balancing) 이진 탐색 트리(binary search tree)로써, 대표적으로는 연관 배열(associative array) 등을 구현하는 데 쓰이는 자료구조이다. 최초의 구조는 1972년 루돌프 바이어가 창안했으며, 이를 "대칭형 이진 B-트리"(symmetric binary B-tree)라고 불렀고, 1978년 Leo J. Guibas와 로버트 세지윅이 발표한 논문에서 현재의 이름이 등장하게 되었다. 레드-블랙 트리는 복잡한 자료구조이지만, 실 사용에서 효율적이고, 최악의 경우에도 상당히 우수한 실행 시간을 보인다: 트리에 n개의 원소가 있을 때 O(log n) 의 시간복잡도로 삽입, 삭제, 검색을 할 수 있다.

용어

레드-블랙 트리는 이진 트리의 특수한 형태로써, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다. 이진 트리에서는 각각의 자료가 '노드(node, 분기점)'에 저장이 된다. 이 노드 중 하나는 시작점이 있는데, 시작점은 다른 어떤 노드의 자식(child)노드가 될 수 없다; 이 시작점을 root node, 또는 root라고 부른다.

노드는 자신과 연결되는 최대 두 개의 자식 노드를 가질 수 있다. 각각의 자식 노드도 역시 자신과 연결되는 최대 두 개의 자식 노드를 가질 수 있으며, 이런식으로 계속 연결된다. 그러므로, root node는 자신으로부터 이 트리에 속한 모든 노드에 도달할 수 있는 경로(path)가 있다.

어떤 노드에 자식 노드가 없다면, 그 노드를 leaf node라고 부르는데, 이는 그 노드가 말 그대로 트리의 변방(또는 맨 끝)에 있기 때문이다. 부분트리는 어떤 노드에서부터 시작되는 트리의 일부분이며, 그 자체가 트리이기도 하다. 레드-블랙 트리에서는 leaf node들은 비어있다(null)고 가정한다; 다시 말해서, 자료를 가지고 있지 않는다는 말이다.

레드-블랙 트리를 포함한 이진 탐색 트리는, 모든 노드에 대해 '자신이 가진 자료(data)는 자신보다 오른쪽에 위치한 부분트리가 가지고 있는 모든 data에 대해서 작거나 같고, 자신보다 왼쪽에 위치한 부분트리가 가지고 있는 모든 data에 대해서 크거나 같다' 라는 조건을 만족한다. 이런 특성 때문에 특정 값을 빠르게 찾아 낼 수 있으며, 각 구성원소(elements)간의 효율적인 in-order traversal이 가능하다.

용도와 장점

레드-블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees). 이는 실시간 처리(real-time applications)와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-블랙 트리를 기반으로 만들어져 있다.

AVL 트리는 레드-블랙 트리보다 더 엄격하게 균형이 잡혀 있기 때문에, 삽입과 삭제를 할 때 최악의 경우에는 더 많은 회전(rotations)이 필요하다.

레드-블랙 트리는 함수형 프로그래밍(functional programming)에서 특히 유용한데, 함수형 프로그래밍에서 쓰이는 연관 배열(associative array)이나 집합(set)등을 내부적으로 레드-블랙 트리로 구현해 놓은 경우가 많다. 이런 구현에는 삽입, 삭제시 O(log n)만큼의 시간이 필요하다.

레드-블랙 트리는 2-3-4 트리와 등장변환이 가능하다(isometry). 다시 말해서, 모든 2-3-4 트리에는 구성 원소와 그 순서(order)가 같은 레드-블랙 트리가 최소한 하나 이상 존재한다는 말이다. 2-3-4 트리에서의 삽입, 삭제 과정은 레드-블랙 트리에서의 색 전환(color-flipping)과 회전(rotation)과 같은 개념이다. 그러므로 2-3-4 트리는 레드-블랙 트리의 동작 과정(logic)을 이해하는 데 많은 도움을 주며, 이런 이유로 많은 알고리즘 교과서들이 실제로는 잘 쓰이지 않음에도 불구하고 2-3-4 트리를 레드-블랙 트리가 나오기 바로 전에 소개하고 있다.

특성(Properties)

레드-블랙 트리의 예

레드-블랙 트리는 각각의 노드가 레드 나 블랙 인 색상 속성을 가지고 있는 이진 탐색 트리이다. 이진 탐색 트리가 가지고 있는 일반적인 조건에 다음과 같은 추가적인 조건을 만족해야 유효한(valid) 레드-블랙 트리가 된다:

노드는 레드 혹은 블랙 중의 하나이다. (A node is either red or black.)
루트 노드(시작점)은 블랙이다. (The root is black.)
모든 leaf node는 블랙이다. (All leaves are black. (The leaves are the NIL children.))
레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. 한편 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다. (Both children of every red node are black. Therefore, a black node is the only possible parent for a red node.)
어떤 노드로부터 시작되어 leaf node에 도달하는 모든 경로에는 leaf node를 제외하면 모두 같은 개수의 블랙 노드가 있다.(Every simple path from a node to a descendant leaf contains the same number of black nodes. (Not counting the leaf node.))

위 조건들을 만족하게 되면, 레드-블랙 트리는 가장 중요한 특성을 나타내게 된다: 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 레드-블랙 트리는 개략적(roughly)으로 균형이 잡혀 있다(balanced). 따라서, 삽입, 삭제, 검색시 최악의 경우(worst-case)에서의 시간복잡도가 트리의 높이(또는 깊이)에 따라 결정되기 때문에 보통의 이진 검색 트리에 비해 효율적이라고 할 수 있다.

왜 이런 특성을 가지는지 설명하기 위해서는, 네 번째 속성에 따라서, 어떤 경로에도 레드 노드가 연이어 나타날 수 없다는 것만 알고 있어도 충분하다. 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나오는 것이 될 것이다. 다섯 번째 속성에 따라서, 모든 경로에서 블랙 노드의 수가 같다고 했기 때문에 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 두배 이상이 될 수 없다.

트리 구조를 나타낼 때, 어떤 노드는 자식(child)를 하나만 가질 수도 있고, leaf node는 데이터를 담고 있을 수 있다. 레드-블랙 트리도 이와 같은 방법으로 나타내 볼 수도 있지만, 그런 표현 방식으로는 레드-블랙 트리의 특성이 변하게 되고, 알고리즘과 상충되게 나타날 수 있다. 그래서, 이 문서에서는 "nil leaves" 나 "null leaves"를 사용하고 있는데, 이 "null leaf"는 위의 그림에서와 같이 자료를 가지고 있지 않으며, 트리의 끝을 나타내는 데만 쓰인다. 트리 구조를 그림으로 표현할 때, 종종 이 "null leaf"를 생략하고 그리는 경우가 많은데, 그렇게 되면 그림상으로는 레드-블랙 트리의 특성을 만족하지 못하는 것처럼 보일 수 있으나 실제로는 그렇지 않다. 이렇게 함으로써, 모든 노드들은 설령 하나 또는 두개의 자식이 "null leaf" 일지라도, 두개의 자식(children)을 가지게 된다.

간혹 레드-블랙 트리를 노드가 아닌 붉은색 또는 검은색 선분(edge)으로 설명하기도 하는데, 실제로는 같은 이야기이다. 어떤 노드의 색은 노드와 그 부모를 연결하는 선분의 색에 대응되기 때문인데, 차이점이 있다면 레드-블랙 트리의 두 번째 속성에서 언급된 root node가 선분으로 설명할 경우 존재하지 않는다는 점이다.

동작

레드-블랙 트리의 읽기 전용(read-only) 동작(검색 등)은 이진 탐색 트리의 읽기 전용 동작의 구현을 변경하지 않아도 되는데, 이는 레드-블랙 트리가 이진 탐색 트리의 특수한 한 형태이기 때문이다. 그러나 삽입(insertion)과 삭제(removal)의 경우 이진 탐색 트리의 구현에 따른 동작만으로는 레드-블랙 트리의 특성을 만족하지 못하게 된다. 레드-블랙 트리의 특성을 다시 만족하게 만들기 위해서는 O(log n) 또는 amortized O(1)번의 색 변환과(실제로는 매우 빨리 이루어진다) 최대 3회의 트리 회전(tree rotation)이 필요하다(삽입의 경우 2회). 삽입과 삭제는 복잡한 동작이지만, 그 복잡도는 여전히 O(log n)이다.

[편집] 삽입(Insertion)

레드-블랙 트리의 삽입은 단순 이진 탐색 트리에서 하는 것과 같이 노드를 삽입하고, 색을 붉은색으로 정하는 것으로 시작한다. 그 다음 단계는, 그 주위 노드의 색에 따라 달라진다. 여기서 '삼촌 노드' 라는 것을 도입할텐데, 이는 같은 높이에 있는 옆 노드(다시 말해, 사촌)의 부모 노드(삼촌)를 뜻한다. 여기서 레드-블랙 트리의 특성이 추가된다 :

특성 3 (null node를 포함한 모든 leaf node는 검정색이다)는 언제나 변하지 않는다.
특성 4 (적색 노드의 모든(두) 자식은 검정색이다)는 적색 노드의 추가, 검정색 노드의 적색 노드로의 전환, 회전(rotation)에만 의해서 제대로 지켜지지 않는 상황이 된다.
특성 5 (어떤 노드로부터 시작되어 leaf node에 도달하는 모든 경로에는 모두 같은 개수의 블랙 노드가 있다)는 검정색 노드의 추가, 적색 노드의 검정색 노드로의 전환, 회전(rotation)에만 의해서 제대로 지켜지지 않는 상황이 된다.

주의: 삽입하는 원소를 N, N의 부모 노드를 P, P의 부모를 G, 마지막으로 N의 삼촌 노드를 U로 나타내기로 한다. 설명 도중 각 노드의 역할과 이름이 바뀌지만, 각각의 경우 노드에 붙은 이름(label)은 각 경우에 최초의 상황에서의 이름을 나타낸다. 도표에서 보여지는 색상은 각각의 경우에 예상되는 색이거나, 예상된 색에 의해 유추된 색이다.

또한 각각의 경우를 C 으로 만든 예제를 통해 보여줄 것이다. 삼촌 노드와 할아버지 노드는 다음과 같은 함수(function)에 의해 나타낼 수 있다:

node grandparent(node n) {
    return n->parent->parent;
}

node uncle(node n) {
    if (n->parent == grandparent(n)->left)
        return grandparent(n)->right;
    else
        return grandparent(n)->left;
}

첫 번째 경우: N 이라고 하는 새로운 노드가 트리의 시작(root)에 위치한다. 이 경우, 레드-블랙 트리의 첫 번째 속성(트리의 시작은 검정색이다)을 만족하기 위해서, N을 검정색으로 표시한다. 이 경우, 시작점으로부터 뻗어나가는 모든 경로에 검정색 노드를 하나 추가한 셈이 되기 때문에 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)은 여전히 유효하다.

void insert_case1(node n) {
    if (n->parent == NULL)
        n->color = BLACK;
    else
        insert_case2(n);
}

두 번째 경우: 새로운 노드의 부모 노드 P가 검정색이므로, 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식 노드는 검정색이다)은 유효하다. 그러므로 두 번째 경우에도 이 트리는 적절한 레드-블랙 트리이다. 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)도 별 문제가 없는데, 이는 새로운 노드 N은 두개의 검정색 노드를 leaf node로 가지고 있기 때문이다. 비록 N이 붉은색 노드라고 해도 N이 들어간 자리에 원래 위치했던 노드의 색이 검정색이었으므로, N의 자식 노드에게서 시작되는 경로들은 모두 같은 수의 검정색 노드를 가지게 되고, 결과적으로 다섯 번째 속성은 유지되게 된다.

void insert_case2(node n) {
    if (n->parent->color == BLACK)
        return; /* Tree is still valid */
    else
        insert_case3(n);
}

주의: 위의 경우, N은 할아버지 노드 G를 가지고 있다고 가정해도 되는데, N의 부모 노드가 붉은색이라면 그 부모 노드가 root node가 될 수 없고, 붉은색 노드의 부모 노드는 검정색 노드 밖에 될 수 없기 때문이다.

또한 N은 삼촌 노드가 있다고 가정할 수 있는데, 위의 네 번째, 다섯 번째 노드에서는 leaf node에 해당한다.

세 번째 경우: 만약 부모 노드 P와 삼촌 노드 U가 모두 붉은색 노드라면, 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)을 유지하기 위해서, P와 U를 모두 검정색으로 바꾸고 할아버지 노드 G를 붉은색으로 바꾼다. 이렇게 함으로써 붉은색 노드인 N은 검정색 부모 노드를 가지게 된다. 그런데 이번에는 할아버지 노드 G가 레드 블랙 트리의 두 번째 속성(root node는 검정색이다)이나 네 번째 속성(붉은색 노드의 두 자식 노드는 검정색이다)을 만족하지 않을 수 있다(네 번째 속성은 G의 부모 노드가 붉은색일 경우 만족하지 않는다). 이를 해결하기 위해서 G에 대해 지금까지 설명한 첫 번째 경우부터 세 번째 경우까지를 재귀적으로(recursively) 적용한다. 이 작업은 삽입 과정 중에 발생하는 유일한 재귀 호출(recursive call)이며, 회전(rotation) 작업을 하기 전에 적용해야 한다는 것에 주의한다.(이는 일정한 횟수의 회전 작업만이 필요하다는 것을 증명한다.)

void insert_case3(node n) {
    if (uncle(n) != NULL && uncle(n)->color == RED) {
        n->parent->color = BLACK;
        uncle(n)->color = BLACK;
        grandparent(n)->color = RED;
        insert_case1(grandparent(n));
    }
    else
        insert_case4(n);
}

주의: 이 후의 단계에서는 부모 노드 P가 할아버지 노드 G의 왼쪽 자식이라고 가정하고 진행하도록 한다. 만약 P가 G의 오른쪽 자식이라고 했을 때는 네 번째, 다섯 번째 경우에서 왼쪽과 오른쪽을 바꿔서 진행하면 된다. 소스 코드에서는 이를 이미 고려해서 작성되었다.

네 번째 경우: 부모 노드 P가 붉은색인데, 삼촌 노드 U는 검정색이다; 또한 새로운 노드 N은 P의 오른쪽 자식 노드이며, P는 할아버지 노드 G의 왼쪽 자식 노드이다. 이 경우, N과 P의 역할을 변경하기 위해서 왼쪽 회전을 하게 된다; 그 후, 부모 노드였던 P를 다섯 번째 경우에서 처리하게 되는데, 이는 레드-블랙 트리의 네 번째 속성(붉은색 노드의 모든 자식은 검정색 노드이다)을 아직 만족하지 않기 때문이다. 회전 작업은 몇몇 경로들("1" 이라는 이름이 붙어 있는 부분 트리(sub-tree))이 이전에는 지나지 않았던 노드를 지나게 하는데, 그럼에도 양쪽 노드가 모두 붉은색이므로, 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)을 위반하지 않는다.

void insert_case4(node n) {
    if (n == n->parent->right && n->parent == grandparent(n)->left) {
        rotate_left(n->parent);
        n = n->left;
    } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
        rotate_right(n->parent);
        n = n->right;
    }
    insert_case5(n);
}

다섯 번째 경우: 부모 노드 P는 붉은색이지만 삼촌 노드 U는 검정색이고, 새로운 노드 N이 P의 왼쪽 자식 노드이고, P가 할아버지 노드 G의 왼쪽 자식 노드인 상황에서는 G에 대해 오른쪽 회전을 한다. 회전의 결과 이전의 부모 노드였던 P는 새로운 노드 N과 할아버지 노드 G를 자식 노드로 가지게 된다. G가 이전에 검정색이었고, P는 붉은색일 수밖에 없기 때문에, P와 G의 색을 반대로 바꾸면 레드-블랙 트리의 네 번째 속성(붉은색 노드의 두 자식 노드는 검정색 노드이다)을 만족하게 된다. 레드-블랙 트리의 다섯 번째 속성(한 노드에서부터 뻗어나가는 모든 경로에 대해 검정색 노드의 수는 같다)은 계속 유지되는데, 이는 이전에 P를 포함하는 경로는 모두 G를 지나게 되고, 바뀐 후 G를 포함하는 경로는 모두 P를 지나게 되기 때문이다. 바뀌기 전에는 G가, 바뀐 후에는 P가 P, G, N중 유일한 검정색 노드이다.

void insert_case5(node n) {
    n->parent->color = BLACK;
    grandparent(n)->color = RED;
    if (n == n->parent->left && n->parent == grandparent(n)->left) {
        rotate_right(grandparent(n));
    } else {
        /* Here, n == n->parent->right && n->parent == grandparent(n)->right */
        rotate_left(grandparent(n));
    }
}

삽입 동작은 치환 작업인데, 이는 모든 호출(call)이 tail recursion이기 때문이다.

'자료구조' 카테고리의 다른 글

[Sorting] Sort algorithm 설명 동영상(Insertion, shell, bubble, selection, Quick, Shaker..) (0)	2011.07.16
Skip list _ wikipedia (0)	2011.03.09

Posted by Triany

2011. 4. 10. 22:23

11.4.10 ... 여러 생각들..

Simple's..../일상

좀더 많은 글을 읽고, 생각의 지평을 넓혀야 된다는 생각이 든다.
자국의 역사, 철학, 그리고 세계사,..

전공지식을 쌓는 것도 중요하지만,
생각의 지평을 넓히는 것도 중요하다는 생각이 들었다.

책을 많이 읽고, 신문을 읽어야 겠다.
모니터로 보는 것보다는 신문을 통해 보는 것이 더 좋을 듯 싶다.

게으름을 버리고, 조금 더 부지런하고 성실하게 살자.
요행을 바라지 말자. 요행은 결국은, 어느 것도 남기지 못한다.

경제학 관련 과목을 6개나 들었는데,
과연 그것이 내 머리속에 얼마나 들어있는지?
교양까지 합쳐서 8과목을 들었는데, 듣고 흘려버린 게 더 많지 않은지.
증권시장 관련 과목을 들었는데, 과연 그것을 활용하고 있는지.
세계경제의 흐름을 과연 읽고 있는지.
학문을 하는 건지, 지식을 쌓는건지. 아니면 책만 늘리는 건지.

좀더 궁구하고 생각하는 삶을 살자.
이 시간을 그저 흘러가는 시간들로 여기며 살지 말자.
흘러가는 시간의 순간 순간들을 잡자.

'Simple's.... > 일상' 카테고리의 다른 글

다시 3개월 시작. (0)	2012.09.25
[존경할 인물] 콜롬비아 대학교 청소부 - '오전에 수업, 오후에 근무' 콜롬비아대 청소부 20년만에 학사 학위 받아 (0)	2012.05.12
3학년의 마지막 나날들 (0)	2011.12.17
[펌] 프로그래밍 공부법 (0)	2011.03.22
새 컴(Desk top) 장만 (0)	2011.02.19

Posted by Triany

2011. 4. 3. 23:43

<input> cin(), get(), getline() 함수 차이.

Language/C++

<cin> : 문자와 문자열 모두 입력 받을 수 있다.
- 엔터가 나오면 입력종료로 간주.(공백도 마찬가지)

#include <iostream>
void main()
{
char a, b;
char str[10];

cin>>a; //1
cout<<a<<endl; //2

cin>>a; //3
cin>>b; //4
cout<<a<<" "<<b<<endl; //5

cin>>str; //6
cout<<str<<endl;; //7
}

1번에서 p를 입력하고 엔터
2번 출력 결과 => p

3,4번에서,
x입력후 엔터, y입력후 엔터
5번 출력 결과 => x y

6번에서 loving you 엔터
7번에서 출력 결과 =>loving

<get> : get()은 문자만 입력받을 수 있다.
- 이 함수는 개행문자를 입력 큐에 그대로 남겨둔다.

#include <iostream.h>
void main()
{
char a, b, c;
a = cin.get(); //cin.get(a) 가능
b = cin.get();
c = cin.get(); //1
cout<<a<<" "<<b<<" "<< c<<endl; //2
}

1번까지
x입력후 엔터, y입력후 엔터
[2번 출력 결과]
x
y
-즉 엔터도 입력받을 문자로 간주한것으로 볼 수 있습니다.(공백또한 문자로 간주)
x + Enter(개행) + y

cf)cin은 엔터가 나오면 입력 종료로 간주.

cf)getline와 get함수가 다른 점은 get함수는 개행문자를 읽어서 버리지 않고 입력큐에 그대로 남겨둔다는 점이다.
즉, cin.get(str1, hi);
cin.get(str2, hello);
라는 두 문장이 있다면 입력큐에 개행문자가 그대로 있어서 두번째 호출은 개행문자를 첫 문자로 만나게 된다.
굳이 get()을 써야 한다면,
cin.get(str1, hi);
cin.get();
cin.get(str2, hello);
이렇게 두 문장사이에 get()을 하나 더 삽입하면 된다.

파일에서 읽어들여 올때.. 간단한 사용법

read ( ifstream *input_file )
{
char c;
while (1)
{
  input_file->get(c);
  if ( input_file->eof() )
   break;
  else
   cout<<c;
}
}

//or
read ( ifstream *input_file )
{
char c;

input_file->get(c);
while (!input_file->eof())
{
cout<<c;
input_file->get(c);
}
}

//or ... 이게 제일 편한 방법인듯.
read ( ifstream *input_file )
{
char c;

while ( input_file->get(c) )
cout<<c;
}

<getline> : getline()은 문자열만 입력 받는다.
getline(변수의 주소, 최대입력가능 문자수, 종결문자);
-getline()gkatnsms Enter키가 전달하는 개행문자를 입력의 끝으로 인식하여 한줄 전체를 읽는다.
-종결문자 생략시 엔터로 간주된다. 그리고 종결문자를 NULL문자로 바꾼다. 따라서 종결문자전까지 출력하게 된다.
최대입력가능 문자수보다 많은 문자를 입력한 경우 n-1개만큼만 받아들이고 n번째 문자는 null문자로 취급한다.
-cin.getline(a,20); //이때 입력한 문자의 개수는 19개이하이여야 한다.(마지막 1문자는 null문자 삽입)

#include<iostream>
void main()
{
char a[10];
cin.getline(a,10); //1
cout<<a<<endl; //2

cin.getline(a, 10, 'u'); //3
cout<<a<<endl; //4

}

1번에서 so cute! 입력후 엔터
2번 결과 => so cute!
cf)cin의 경우 공백이 나오면 입력이 끝났다고 간주, but getline은 공백(ascii 32)도 문자로 받아들임

3번에서 so cute! 입력후 엔터
4번 결과 => so c

파일에서 읽어올 경우.. infile->getline(이 위치로, 문자수, 종결문자) 형식.
read(ifstream *infile)
{

SMS S;
while(!infile->eof())
{
  infile->getline(S.phone,21,'\n');
  infile->getline(S.msg, 97,'\n');
  S.time = currentTime();
  insert(S);
}
}

'Language > C++' 카테고리의 다른 글

[c++] 레퍼런스, reference, int &ref = val; 레퍼런스 변수, 별명! (0)	2014.06.17
포인터의 용도 / 동적할당메모리 (0)	2013.04.29
C++ Preprocessor: Always Assert Your Code Is Right (0)	2011.03.25
ostream/istream (0)	2011.03.14
연산자 오버로딩 (0)	2011.03.14

Posted by Triany

2011. 3. 25. 17:54

C++ Preprocessor: Always Assert Your Code Is Right

Language/C++

출처 : http://www.devarticles.com/c/a/cplusplu ··· right%2F
출처:http://webdizen.new21.net/blog/3110

Are you looking for a way to speed up the debugging process in C++? This article explains how to use asserts to do just that, showing that not all macros are evil.

If a man begins with certainties, he shall end in doubts;

But if he will be content to begin with doubts,

He shall end in certainties.

[Francis Bacon 1561-1626]

Assertive Programming

If there is one thing I have learned over the past few years, it is not to underestimate the power of assert(). It comes with your compiler and can be found either in cassert or assert.h.

The reason I love assert is because it looks after me and helps me find bugs I was sure weren’t there. I mean, we all write bugfree software, right? Yeah right. Well there have been many Kodak moments when an assert fired on something I was dead sure could never happen; I should be a rich man as the look on my face was priceless.

If you are not familiar with asserts, you should start using them right now. Use assert to check that your code is working the way you expect it to or be prepared to pay the price. No not for my face, but for long nights behind the debugger, ticking away possible problem sources until you have your own Kodak moment.

When do you use assert, you ask? Simple… whenever you can use it to verify the truth of a situation: ‘this pointer can never be null’, ‘this number is never smaller than zero’, ‘there is always at least one customer stored in this list’, ‘this code won’t be used the next millennium, two digits are fine’.

Use proper error handling when you can check for things that can go wrong. Use asserts on things you are sure can’t go wrong.

Trust me… the sillier the assert… the more valuable it is. I tested this once myself, grinning, thinking ‘this is ridiculous, want to bet it will never fire?’, only to have it triggered a couple of months later! And because the assert was so preposterous and silly I immediately knew which conditions were breaking my code.

assert.

To state or express positively, affirm: asserted his innocence
To defend or maintain (one’s rights, for example)

The important thing to remember is that asserts are only compiled into your code when the NDEBUG macro is not defined. So in the final optimized version of your application, they are not there to bloat or to slow things down! The only investment you have to make is typing them out while you are working on those classes and functions. It will pay you back greatly when it helps you shorten the time it takes to track down bugs.

Face it… we all write code on assumptions we make about the situation the code will be running in. Assert you are in that situation, because your code base will grow beyond the picture you have of it in your mind.

Though we will be implementing our customized version of assert here, all you need to do is include assert.h and you are ready to use the assert macro that comes with it:

// assert.h
#ifndef NDEBUG
void __assert(const char *, const char *, int);
#define assert(e) \
((e) ? (void)0 : __assert(#e,__FILE__,__LINE__))
#else
#define assert(unused) ((void)0)
#endif

The __assert helper function prints an error message to stderr and the program is halted by calling abort(). It is possible that the implementation that comes with your compiler varies slightly, but you get the idea.

Lets use a simple example function:

void writeString(char const *string) {
assert( 0 != string );
...
}

In the unfortunate situation that the pointer to string is NULL, execution will halt and you will be offered the possibility of opening the debugger and jumping to the location in the source where the assertion failed. This can be very handy as you can examine the call stack, memory, registers, and so forth, and are likely to catch the perpetrator red handed!

Although I am ranting about why you should use assert, this article is aimed at showing you how to implement your own version using preprocessor macros.

Here is a very basic version that doesn’t even halt execution:

#ifndef NDEBUG
# define ASSERT( isOK ) \
( (isOK) ? \
   (void)0 : \
   (void)printf(“ERROR!! Assert ‘%s’ failed on line %d ” \
   “in file ‘%s’\n”, #isOK, __LINE__, __FILE__) )
#else
# define ASSERT( unused ) do {} while( false )
#endif

Notice that we don’t need a helper function to get information onto the screen. (I am sticking to printf in the following examples, but there is nothing stopping you from using fprintf and stderr instead.) The stringize macro operator (#) names the condition for us in the printf statement, adding quotes as well and the predefined __LINE__ and __FILE__ macros help to identify the location of the assert.

The do { } while ( false ) statement for the unused version of assert, I used to make sure that the user cannot forget to conclude his assert statement with a semicolon. The compiler will optimize it away, and I consider it a slightly better way to say that I am not doing anything.

We are only one step away from halting our application’s execution (don’t forget to include stdlib.h):

#ifndef NDEBUG
# define ASSERT( isOK ) \
if ( !isOK ) { \
(void)printf(“ERROR!! Assert ‘%s’ failed on line %d “ \
“in file ‘%s’\n”, #isOK, __LINE__, __FILE__) ); \
abort(); \
}
#else
# define ASSERT( unused ) do {} while ( false )
#endif

In case writeString is called with a NULL pointer now, we are told what went wrong, where it went wrong and the application is halted.

When you are using the Microsoft Visual C++ 7.1 compiler, you’ll be presented with a dialog screen:

After pressing Retry you are presented with more dialogs and finally... you end up in the debugger.

The problem with abort() is that it doesn’t let you resume execution after you’ve concluded that the assert was benign; or maybe you are interested in what happens immediately after the assert? You need to disable the assert (never a good thing), recompile and restart your application.

There are other ways to halt execution and you will have to look in your compiler’s documentation to discover what the correct call is, but with Visual C++ it’s an interrupt call:

__asm { int 3 }

When our application halts again on the writeString function, we’ll encounter the following dialog (did you recognize it? We actually came across this dialog when halting the application with the abort() function!) :

It is not a problem to continue execution now, if we think this is responsible… that is you are often recommended to implement your own assert functionality.

Wouldn’t it be nice to be able to add some hints or remarks along with the location of the assert? When the assert fires and you don’t have a debugger available, this message might still tell you what the problem is:

void writeString(char const *string) {
assert(0!=string, “A null pointer was passed to writeString()!”);
...
}

The simplest solution is to just expand the assert macro and make it accept a message as well as a condition:

#ifndef NDEBUG
# define ASSERT( isOK, message ) \
if ( !(isOK) ) { \
(void)printf(“ERROR!! Assert ‘%s’ failed on line %d “ \
“in file ‘%s’\n%s\n”, \
#isOK, __LINE__, __FILE__, #message); \
__asm { int 3 } \
}
#else
# define ASSERT( unused, message ) do {} while ( false )
#endif

Again the stringize operator helps us to stuff the message we want into the printf statement. We could call it a day now, but I am a very lazy coder… I do not want to be forced to put messages into the assert, sometimes I just want to assert.

Of course it is possible to write an ASSERT(condition) and an ASSERTm(condition, message) macro, but did I mention I am a forgetful coder too? I’d much rather have a single ASSERT statement that can do both.

The first thing that comes to mind is the fact I could do this easily with a function:

void MyAssert(bool isOK, char const *message=””) {
if ( !isOK ) {
(void)printf(“ERROR!! Assert ‘%s’ failed on line %d “
“in file ‘%s’\n%s\n”,
__LINE__, __FILE__, message);
__asm { int 3 } \
}
}

So maybe if I declared another function:

void NoAssert(bool isOK, char const *message=””) {}

And then defined assert as:

#ifndef NDEBUG
# define ASSERT MyAssert
#else
# define ASSERT NoAssert
#endif

While this seems like a quick solution, I have completely lost my extra debug information! The line information is the same now for every assert… oh… the compiler substitutes __LINE__ with the actual line number it is compiling at that moment, and since we are making a function call – all line numbers lead to the MyAssert function!

Alexandrescu demonstrates a great way around this problem [Alexandrescu]. (It is also a great article showing how you can take assertions to a higher level after this one, by making them throw exceptions!)

#ifndef NDEBUG
#define ASSERT \
struct MyAssert { \
MyAssert(bool isOK, char const *message=””) { \
if ( !isOK ) { \
(void)printf(“ERROR!! Assert failed in “ \
“file ‘%s’\n%s\n”, __FILE__, message); \
__asm { int 3 } \
} \
} \
} myAsserter = MyAssert
#endif

For some reason my Visual C++ 7.1 compiler will not accept the __LINE__ macro next to the __FILE__ macro in the code above. The strange thing is that the __FILE__ macro works fine, but with __LINE__ it complains:

error C2065: '__LINE__Var' : undeclared identifier

It is never easy, but I do not want to give up at this point. Since the macro is expanded as a single line into the place where we are calling it, and since the compiler apparently has no objection to me assigning __LINE__ as a default parameter in a constructor, let's try again:

#ifndef NDEBUG
#define ASSERT \
struct MyAssert { \
int mLine; \
MyAssert(int line=__LINE__) : mLine(line) {} \
MyAssert(bool isOK, char const *message=””) { \
if ( !isOK ) { \
(void)printf(“ERROR!! Assert failed on “ \
“line %d in file ‘%s’\n%s\n”, \
MyAssert().mLine, __FILE__, message); \
__asm { int 3 } \
} \
}\
} myAsserter = MyAssert
#endif

Now that we have our line information back, we are nearly there; as soon as we add a second assert, the compiler complains that we are redefining the struct MyAssert! If only we could keep the struct declaration local… and again Alexandrescu shows us how [Alexandrescu]:

#ifndef NDEBUG
#define ASSERT \
if ( false ) {} else struct LocalAssert { \
int mLine; \
LocalAssert(int line=__LINE__) : mLine(line) {} \
LocalAssert(bool isOK, char const *message=””) { \
if ( !isOK ) { \
(void)printf(“ERROR!! Assert failed on “ \
“line %d in file ‘%s’\n%s\n”, \
LocalAssert().mLine, __FILE__, message); \
__asm { int 3 } \
} \
} myAsserter = LocalAssert
#else
#define ASSERT \
if ( true ) {} else struct NoAssert { \
NoAssert(bool isOK, char const *message=””) {} \
} myAsserter = NoAssert
#endif

There is a lot of fun to be had with macros and sometimes it is possible to create the wildest incantations with them [Niebler/Alexandrescu]. I hope you are convinced that despite the fact that they can be considered evil, there is something magical about them as well.

As a final example I will show you how to create personal and customizable debug streams in the next article… all with macros.

References

[STL] – The Standard Template Library

< comes standard with your compiler but this one is very portable>

http://www.stlport.org

[BOOST] – Boost C++ Libraries

http://www.boost.org

[ACE] – The ADAPTIVE Communication Environment

http://www.cs.wustl/edu/~schmidt/ACE.html

[Niebler] – Eric Niebler

“Conditional Love: FOREACH Redux”

http://www.artima.com/cppsource/foreach.html

[Alexandrescu] – Andrei Alexandrescu

Assertions

http://www.cuj.com/documents/s=8248/cujcexp2104alexandr/

'Language > C++' 카테고리의 다른 글

포인터의 용도 / 동적할당메모리 (0)	2013.04.29
<input> cin(), get(), getline() 함수 차이. (0)	2011.04.03
ostream/istream (0)	2011.03.14
연산자 오버로딩 (0)	2011.03.14
C++ 에서 setw(int num) 함수를 이용하여 깔끔하게 출력하기! (0)	2011.03.09

Posted by Triany

2011. 3. 22. 00:04

[펌] 프로그래밍 공부법

Simple's..../일상

프로그래머의 지식 투자

수많은 세계의 석학들은 미래사회는 지식 중심 사회가 될 것이라고 예견했고, 그 예측은 거의 맞아 들어가고 있는 것 같다. 몇몇 특수한 상황을 제외하곤, 지금 당장 가장 수익률이 좋고 안정성이 보장되는 투자는 지식에 대한 투자다. 한번 제대로 획득하면 잃어버릴 일이 거의 전무하기 때문이다. 프로그래머와 같은 지식 산업 종사자들은 ( 자신들은 단순 노무직이라고 부인할 지라도) 자신의 지식 투자를 효과적, 효율적으로 관리할 수 있어야 한다. 이것이 미래에 대비하는 길이다.

앞서 소개한 헌트와 토마스는 이것을 지식 포트폴리오(Knowledge Portfolio)로 설명하고 있다. 지식 투자 관리는 어떤 면에서 재무 투자 관리와 상당히 유사하다.

- 정기적으로 투자하는 것을 습관화한다
- 분산 투자가 장기 성공의 열쇠다
- 자신의 포트폴리오를 안전한 것과 위험성이 큰 것을 고루 갖추도록 균형을 잡는다
- 싸게 사서 비싸게 판다.
- 주기적으로 포트폴리오를 재평가한다

첫 번째, 정기적 투자는 자신의 지식을 위해 '정기적'으로 '조금씩' 새로운 지식을 습득하는 것을 말한다. 예를 들어 매년 새로운 프로그래밍 언어(가능하면 다른 패러다임의 언어)의 습득을 목표로 세운다든지, 매 분기마다 새로운 기술 서적을 한 권 씩 읽기로 약속한다든지, 비기술 서적(컴퓨터와 관련 없어 보이는 것일수록 좋다)을 정기적으로 읽고 통신 동호회에 가입해 스터디를 한다든지, 새로운 플랫폼을 시도해 보거나, 매달 잡지와 저널을 구독하는 노력을 모두 꾸준히 조금씩 해주는 것이 중요하다.지금 당장 필요하지 않은 혹은 향후 수십 년간 사용할 것 같지도 않은 언어를 배우면서 자꾸 의혹 속에 괴로워하지 마라. 설령 그 언어를 사용하진 않더라도 다른 문제 해결에 분명 도움이 될 것이다. 또 경계를 넘어선 '가로지르기'도 필요하다. 갑이라는 기술을 배웠고 전혀 다른 분야에서 을이라는 지식을 얻었을 경우 둘 사이에 존재하는 상관관계, 응용 방법 등을 깊이 생각해 보는 것은 지식을 체화시키면서 실질적인 소득도 얻을 수 있는 기회다.
두 번째, 분산 투자는 한마디로 서로 다른 것을 더 알게 될수록 자신은 더욱 가치 있어질 것이라는 얘기다. 하지만 기본적으로 어떤 것이 저무는 태양이고, 어떤 것이 떠오르는 것인지에 대한 정보를 갖춰야 할 것이다. 그렇다고 자신을 너무 내몰지는 마라. 어제 떠오른 것이 오늘 지고, 어제 졌던 것이 오늘 뜨는 현상이 이 분야에 한 두 번 있는 일이던가.
세 번째, 위험 관리다. 아마도 '계란을 한 곳에 담지 마라'는 말을 들어봤을 것이다. 안정성이 보장되는 지식만 좇는 것이나, 위험성이 너무 큰 (실효가 입증되지 않은) 지식만 추구하는 것은 모두 문제가 있다. 균형을 유지해야 한다.
네 번째, 싸게 사서 비싸게 팔아 차익을 크게 만들어라. 자바가 처음 등장했을 때 그것을 배우는 일은 상당히 위험성이 높았을 것이다. 하지만 초기 개발자들이 결국은 얼마나 비싸게 자신의 지식을 팔아 이득을 얻었는가. 서점에 널린 기술은 이미 비싸게 사서 싸게 팔 확률이 높은 것들이다.
다섯 번째, 이 분야는 매우 동적이다. 지난달에 인기가 치솟았던 것이 이번 달엔 곤두박질 칠 수도 있다. 너무 유행에 민감한 것도 문제겠지만, 그렇다고 자신의 포트폴리오를 몇 달 간 다시 들여다보지 않는 것처럼 위험한 것도 없다. 먼지가 쌓이고 녹슬어 가는 지식이라면 기름칠을 해야 할 것이고, 새로운 지식이 필요하다고 판단되면 과감이 뛰어들어야 한다.

이 다섯 가지 중에서 뭐니뭐니 해도 가장 중요한 것은 첫 번째 항목인 '자신의 포트폴리오에 정기적인 투자'가 될 것이다.

@프로그래머의 자기 수련

:: 서적

다음의 서적들은 프레드 브룩스, 팀 버너스리, 앨런 쿠퍼, 제임스 고슬링, 브라이언 커니건, 스티브 맥코넬, 앤드류 타넨바움, 윌리엄 스톨링, 제럴드 웨인버그 등과 같은 컴퓨터 역사에 이름이 남을 만한 유명인으로부터 실전에서 이십 년 이상을 구르고 베테랑으로 알려진 프로그래밍의 노장과 달인들이 공통적으로 '자신에게 가장 많은 영향을 준 컴퓨터 관련 책'으로 꼽는 것을 필자가 몇 년에 걸쳐 수집하고 추려낸 것이다. 재밌게도 컴퓨터와는 별 관련 없어 보이는 책들도 몇 권 있다. 역시 유행과 동떨어졌기에 유행에서 살아남을 수 있었던 것이리라. 여기 나열된 책들은 대부분 처음 출판된 지 10년이 넘은 것이고 어떤 것은 30년이 넘은 것도 있다. 이런 고생대의 화석이 아직까지도 우리 시대에 유효할 수 있다는 것 자체가 경이로울 뿐이다. 정말 좋은 책이란 읽을 때마다 새로운 맛이 소록소록 나오고, 자신이 가진 문제에 늘 다양한 해답을 제공해 줄 것이다. 수천 년을 면면히 이어 내려온 노자 도덕경이 인류 곁을 아직 떠나지 않는 이유일지도 모르겠다. 전문 프로그래머라면 항상 기술 중심적이고 구체적인 책을 한 손에 들고 공부하면서도, 이런 일반적이고 유행과 상관없는 책을 다른 손에서 놓치지 않아야 할 것이다.

◆ The Art Of Computer Programming (TAOCP), Knuth, Donald
알고리즘과 자료구조에 관한 최고의 책이다. 프로그래머로서 정말 충실하게 공부해 둬야만 나중에 좌절을 맛보는 경험을 피할 수 있다. 현재 세 권까지 출판돼 있고, 1997년에 세 번째 판이 나왔다.

읽을 자신이 없다면 최소한 이 책들의 목차만이라도 봐두자. 상대적으로 좀 가벼운 책으로는 로버트 세드게윅(Robert Sedgewick)이나 토마스 코멘 외 2인 공저의 'Introduction to Algorithms'를 참고하라.

◆ Programming Pearls, Bentley, Jon Louis
실질적인 코드(C, C++)와 함께 알고리즘 개선, 코드 최적화 등을 다룬다. CACM에 연재됐던 것을 모으고 좀 더 덧붙인 것이다. 현재 프로젝트에서 알고리즘이나 자료구조에서 문제가 생기면 일단 마음을 차분히 가라앉히고 조용한 곳에서 이 책을 읽어보라.

◆ Structure and Interpretation of Computer Programs, Abelson, Harold, et al.
미국 MIT 대학에서 십 년이 넘도록 입문 코스용 교과서로 사용되고 있는 유명한 고전이다. 비록 수년이 흘렀고, Scheme이라는 그다지 대중적이지 못한 언어를 사용했지만, 이 책은 여전히 고전으로서의 가치가 빛나고 있다. 세월이 가도 변치 않을 프로그래밍의 근본 원리 전달을 목적으로 집필됐기 때문일 것이다. 이 책은 겉 표지에 마법사 그림이 있어서 마법사 책이라고 불리며, 에릭 레이먼드의 해커 사전에도 등재돼 있다.

◆ Design Patterns, Gamma, Erich, et al.
하나의 디자인 패턴은 특정한 종류의 문제를 해결하는, 프로그래밍 언어보다는 좀 더 추상적인 차원에서 일반적인 방법을 서술한다. 저자들은 '네 명의 동지들(Gang of Four)'로 더 알려져 있다. 국내 서점에서도 바닥이 날 정도로 잘 팔리는 베스트 셀러다.

◆ A Pattern Language: Towns, Buildings, Construction, Alexander, Christopher
패턴 언어는 원래 건축학에서 온 개념이다. 건물을 짓는 것과 소프트웨어를 만드는 것(영어로는 모두 build라고 한다) 간에는 상당한 유사점이 있다. 디자인 패턴을 본 사람이라면 이 개념의 원류를 공부해 보는 것이 매우 유익할 것이다.
이 책과 함께 많이 읽히는 'Timeless Way of Building'은 좀 더 철학적(노장사상과 관계가 깊다)이고 사변적이다. 이것을 읽는다면 세상을 보는 관점이 바뀔 것이다.
흔히 알렉산더의 이론에 대한 반대로 실증적인 결과와 예가 없다는 것인데, 그의 'The Production of Houses'를 꼭 읽어보길 권한다. 필자는 이 책에서 프로젝트 관리와 적응적 개발(adaptive development) 등의 가능성을 발견했다.

◆ How Buildings Learn: What Happens After They're Built, Brand, Stewart
비교적 최근에 출간된 책으로 건축학적인 개념에서 어떻게 건물이 '진화'하고 스스로 변화시켜 나가는지를 보여주며, 진화하기 좋은 건축물은 어떤 것인가에 대한 진지한 고찰이 들어있다. 우리 프로그래머들이 고민하는 문제와 동일하다. 따라서 프로그래밍을 새로운 관점에서 볼 수 있을 것이다.

◆ The Mythical Man-Month: Essays on Software Engineering, Brooks, Frederick
더 이상 설명할 필요가 없는 책이다. 진행중인 프로젝트 팀에 더 많은 인원을 쏟아 부으면 오히려 제품 출시가 더욱 늦어진다는 점을 밝힌 것으로 유명하다. 소프트웨어 공학에 관심이 없거나 기반 지식이 전무한 사람도 읽어볼 만한 책이다.

◆ Code Complete, McConnell, Steve
소프트웨어 구축 과정에 관한 한 거의 모든 사항을 '코드 중심으로' 모아둔 집적체다. 필자는 아직까지 이 주제를 다루면서 이 정도로 포괄적이면서 동시에 가치있는 책을 보지 못했다. 특히 33장의 참고자료는 더 많은 자료를 원하는 사람에게 매우 유용하다.

◆ How to Solve It, Polya, George
문제 해결에 관한 한 최고의 베스트 셀러다. 한글 번역판이 있는데, 국내에서 이 책의 가치가 제대로 평가되지 못하고 수학 시험 준비 서적으로 분류되고 있는 점이 아쉽다. 비단 수학뿐만 아니라 거의 모든 '문제 해결'이라고 할 만한 것(프로그래밍을 포함)에 대해 건강한 경험적 가이드라인(휴리스틱스, heuristics)을 제시하는 책으로 교육적 가치도 높다. 이 책을 공부하고('읽고'가 아니라) 나면 한층 똑똑해진 자신을 발견할 수 있다.

◆ Godel, Escher, Bach: An Eternal Golden Braid, Hofstadter, Douglas R.
GEB라고도 불리는 이 책은, 저자 호프슈테더 교수에게 풀리처상을 안겨줬다. 아마 컴퓨터 관련 직종뿐만 아니라 자연과학, 철학 쪽에서까지 널리 읽히는 인기 서적이 아닐까 한다. 수학의 괴델과, 회화의 에셔, 음악의 바흐 작품을 비교하며 공통점을 찾는다. 전산학의 시원이라 할 수 있는 튜링 컴퓨터에 대한 설명이 있다.

◆ Computer Architecture: A Quantitative Approach, Patterson, David A., et al.
전문 프로그래머라면 하드웨어적인 지식도 절대 놓쳐서는 안된다. 이러한 지식을 아는 사람과 그렇지 못한 사람의 프로그래밍 능력과 몸값은 엄청난 차이가 있다. 컴퓨터 아키텍처에 관한 한 최고의 양서로 평가받는 이 책은 학부생이나 평범한 프로그래머들이 보기엔 다소 난해할 수 있다. 그럴 경우에 같은 저자의 'Computer Organization and Design'을 보는 것이 좋다.

◆ Elements of Style, Strunk, William and E.B. White
영미권에서 작문 관련 서적으로 가장 많이 팔린 책이다. 브라이언 커니건과 플로거가 쓴 'The Elements of Programming Style'은 이 책의 제목을 흉내낸 것이다.
영미인과 문법이나 철자법 등에 대한 논쟁을 하다가도 "스트렁크와 화이트의 책에 따르면"이라는 한마디면 종지부를 맺을 수 있을 정도로 권위적인 책이다. 특히 5장 스타일에 대한 가이드는 기술적 문서를 작성할 때는 물론이고 프로그래밍을 할 때에도 참고가 될 것이다.

◆ The Psychology of Computer Programming, Weinberg, Gerald M.
이 책은 에릭 레이먼드가 썼던 '성당과 시장'에서 비자아적 프로그래머(egoless programmer)에 관한 언급으로 국내에 많이 알려졌지만, 사실 영미권에서는 이미 베스트 셀러의 반열에 오른 지 몇 십 년이 됐다.
프로그래밍을 인간 활동의 하나로 인식하고 심리학적인 접근을 통해 새로운 분야를 세운 기념비적인 책이다. 아직까지도 ACM이나 IEEE 회원들이 가장 많이 구입하는 책 중 하나이며, 최근 실버 기념판이 출판됐다.

◆ ACM Turing Award Lectures : The First Twenty Years : 1966 to 1985
튜링상은 컴퓨터 분야의 노벨상이다. 우리가 실제로 사용하고 있는 거의 모든 기술의 원천은 튜링상 수상자들의 작품이다. 이 책은 튜링상 수상시 함께 하도록 돼있는 강의 내용을 20년간 모은 것이다. 한눈에 컴퓨터계의 발전 역사를 조망할 수 있으며, 선지자들이 조심스럽게 말하는 앞으로의 발전 방향도 엿볼 수 있다.
특별히 엣져 다익스트라(Edsgar Dijkstra)의 'The Humble Programmer'와 도널드 크누쓰의 'Computer Programming as an Art'는 꼭 읽어볼 만하다. 각각 72년, 74년에 한 강의이지만, 많은 부분이 오늘날에도 유효하다는 사실이 그 페이퍼의 질을 보장해 준다.

소개한 책들은 이미 십년 이상을 살아 남았고 앞으로도 최소 오년 이상 가치를 유지할(혹은 더 높아질) 책이 대부분이다. 그런데 모아 놓고 보니 모두가 원서다. 참 슬픈 일이다. 아직까지 우리나라에 그 가치가 최소 오년 이상 되는 책이 쓰여지고 있지 않다는 것은 짧은 역사와 기술 도입만으로는 설명하기 힘들다. 게다가 필자가 아는 한 그나마 두 권(GEB, How to Solve It)을 빼놓고는 모조리 번역 작업조차 되지 않았다.

멀리 보지 못하고, 멀리 볼 겨를도 없는 우리 신세가 안타깝지만, 조만간 이런 작업들이 진행되리라는 일말의 희망을 걸어본다.

@정기 간행물

필자는 과거를 보려면 서점에 나가보고, 현재를 보려면 정기 간행물이나 논문을 살펴보고, 미래를 보려면 현장 (아카데미아와 기업계)을 뛰어다녀 봐야 한다고 생각한다.
이미 서점에 판을 치고 있는 기술들은 그 정보가치가 많이 하락한 것들이고 소위 '끝물'일 확률이 높다. 주식의 "소문에 사고 뉴스에 팔아라"는 말이 적용되는 것이다. 잡지 같은 것은 비교적 출간 사이클이 짧고, 이에 따라 현실 세계를 조금 더 빨리 반영한다. 국내에도 물론 좋은 잡지와 저널이 많이 있지만 여기서는 언급을 피하도록 하겠다.

◆ Software Development(www.sdmagazine.com)
이 잡지는 특정 기술이나 팁보다는 전문 프로그래머가 접하는 일반적인 프로그래밍 관련 이슈를 다룬다. 소프트웨어 공학, 개발 방법론, 프로그래머란 직업에 대한 기사들 혹은 프로젝트 관리자에게 도움이 될만한 것들이 많고, 개발 툴 리뷰도 유익하다. 특히 일년에 한번씩 있는 졸트상 수상은 꼭 놓치지 말아야할 좋은 정보다

◆ Dr. Dobb's Journal(www.ddj.com)
제목에는 저널이라고 되어 있지만 그다지 아카데믹한 내용은 아니다. 비교적 이론적이고 코드 지향적인 성격의 잡지라고 보면 된다. 알고리즘 분야에 상당히 강하다. 도구나 기술 사용법의 연마도 중요하지만 도구/기술의 이면에 있는 이론으로 중무장하는 것은 '전문 프로그래머'가 되기 위해선 반드시 해야할 일이다.

◆ Information Week(www.informationweek.com)
아무리 개발자라고 해도 비즈니스적인 변화는 늘 감지하고 있는 것이 좋다. 어떤 기술이 잘 팔리고 향후 어떤 기술이 주목을 받을지, 지금 내가 의지하고 있는 배가 침몰 중이지는 않은지 등을 말이다.

◆ Communications of ACM(www.acm.org)
가장 오래되고, 또 가장 인정(?)받는 컴퓨터 관련 저널 중 하나. IEEE Computer처럼 다루는 분야가 매우 넓기 때문에 대부분의 기사가 자신의 관심사 밖의 것일 수도 있는데, 컴퓨터 관련 이론/기술의 원류가 되는 만큼 자신의 분야를 막론하고 꼭 구독해 볼 가치가 있는 잡지이다. 이곳에 기사가 실리고 몇 년 지나야 비로소 관련 내용을 여타 잡지에서 확인하는 경우도 종종 있다.

◆ IEEE Software(www.computer.org)
격월 잡지로 소프트웨어 개발 방법론이나 여타 소프트웨어 관련 주제를 다룬다. 전문 프로그래머들에게 도움이 될만한 실질적인 기사가 많이 있다. IEEE Computer는 앞서 소개한 CACM과 비슷한 성격인데, IEEE Software보다는 다루는 주제의 범위가 훨씬 넓다.

@모임

컴퓨터 분야에는 현재 두 개의 '세계 수준의' 전문가 모임이 존재한다. ACM(Association for Computing Machinery)과 IEEE 컴퓨터 소사이어티가 그것이다. 전문 프로그래머(세계 수준의)라면 최소한 둘 중 하나에는 가입되어 있는 것이 일반적이다. 국내에도 다양한 전문가 단체가 있는데, 자신의 관심 분야 한 곳과 일반적인 한 곳은 꼭 가입을 해두는 것이 좋다.
또한 통신 동호회나 스터디 그룹과 같은 비격식적인 모임에도 참여를 하고, 자신과 다른 분야에서 일을 하는 전문가들과 지속적인 접촉을 유지하는 것이 세상에 뒤쳐지지 않는 방법이다. 항상 다른 사람들이 '현재 고민하는 것'이 무엇이고, '성취하고자 하는 것'이 무엇이며, '과거에 어떤 교훈을 얻었는지'의 세 가지를 탐지할 일이다.

@효과적인 공부법

심리학에서 스키너 박스는 행동주의(Behaviorism)의 대표적인 실험인데, 상자 안에 생쥐를 가둬두고 그 놈이 버튼 혹은 레버를 누를 때마다 구멍으로 먹이를 보내준다. 처음에는 그 버튼이, 레버가 무슨 의미인지를 알지 못하다가 우연히 그것을 누르고는 먹이를 먹는다. 물론 당시에는 그 두 가지 사건을 연관지어 생각하지 못한다. 하지만 시간이 갈수록 학습을 하게 되고, 배가 고플 때면 버튼을 알아서 누른다. 인간의 학습에 대한 이런 스키너 박스식 접근은 이미 폐기 처분된 지 오래지만, 여전히 유효한 것들이 몇 가지 있다. 이 실험에서 버튼이 눌려진 때와 먹이를 보내주는 때의 시간 차이를 늘려주면 학습이 느려지거나 혹은 아예 학습이 일어나지 않는다. 우리가 학습을 할 때 피드백이라는 것은 아주 중요한 역할을 한다. 내가 무엇을 잘못했는지, 제대로 했는지를 즉각적으로 알 수 있으면 바로 자신의 이전 행동에 대한 수정이 가능하고 이는 새로운 학습으로 이어질 수 있다. 이런 면에서 파이썬이나 스몰토크 같은 대화형 인터프리터 언어는 중요한 위치를 차지한다. 난생 처음 파이썬을 대하는 사람이 단박에 문자열을 출력해 본다든지, 사칙연산을 해본다든지 하는 경험은 다른 컴파일러 언어에서 쉽게 체험할 수 없는 '놀라운 학습'의 경험인 것이다.
주변에서 보면 처음부터 모든 완벽을 기하려는 사람보다 조금씩 시도해 보고 또 수정하고, 다시 시도하는 소위 점진적 접근법을 행하는 사람들이 더 빨리 학습하는 경우가 많이 있다. 예컨대, HTML을 공부할 때 처음부터 태그를 외우고 프로토콜의 정의를 이해하고, 문법을 외우는 등 '정규 코스'를 밟은 후에 각종 HTML 에디터를 공부하는 경우와, 나모 같은 소프트웨어를 통해 손쉽게 만들어 본 것을 바로 확인해 보고 또 수정하고 하는 식으로 일단 감을 잡은 사람이 차후에 태그나 문법을 공부하는 경우를 비교해 볼 수 있다. 규칙 중심적 학습은 경험 중심적 학습에 비해 훨씬 더 어렵고 비효율적일 수밖에 없다. 규칙은 '데이터'가, 실제 경험이 이미 내 안에 있는 이후에나 의미가 있다. 아담이 말을 보고 '말'이라고 이름 지은 것은 말을 보기 전이 아니라 그 후였음을 생각해 봐야 할 것이다.
자신이 사고하는 것에 대해 사고하는 것, 이 이차적 사고를 메타인지(meta-cognition)라고 한다. 자신의 잘못을 스스로 인식하고 그것에 대해 생각해 보는 것도 훌륭한 학습의 경험이 된다. 예컨대, 25-16을 19라고 대답한 학생과 41이라고 대답한 학생을 생각해 보자. 만약 학생들이 독학하는 것이 아니고 '보통' 선생님의 가르침을 받고 있다고 치면, 그 둘은 똑같이 틀렸다는 말을 듣고 자신의 실수를 잊어버릴 것이다. 하지만 두 번째 학생의 경우 명백히 뺄셈 대신 더하기를 했다는 것을 알 수 있고, 첫 번째 학생의 경우도 뺄셈을 하되 십의 자리에서 뭔가 문제가 있었다는 것을 알 수 있다. 이런 정보를 기반으로 개개인에게 좀 더 훌륭한 학습의 기회를 제공할 수 있다. 혼자 프로그래밍을 공부하는 사람이라면 자신의 프로그램이 제대로 돌지 않는 경우, 자신의 잘못을 분석하고 어떤 '사고의 틀'이 문제를 일으켰는지 생각해 봐야 한다. 한마디로 '자기 자신을 볼 줄 알아야 한다'는 것이다. 이것이 남보다 빨리 학습하는 비결이다.

'Simple's.... > 일상' 카테고리의 다른 글

다시 3개월 시작. (0)	2012.09.25
[존경할 인물] 콜롬비아 대학교 청소부 - '오전에 수업, 오후에 근무' 콜롬비아대 청소부 20년만에 학사 학위 받아 (0)	2012.05.12
3학년의 마지막 나날들 (0)	2011.12.17
11.4.10 ... 여러 생각들.. (0)	2011.04.10
새 컴(Desk top) 장만 (0)	2011.02.19

Posted by Triany

2011. 3. 14. 20:24

ostream/istream

Language/C++

출처:http://www.cplusplus.com/reference/iostream/istream/

Output Stream

ios_base	ios	ostream	iostream
			ofstream
			ostringstream

ostream objects are stream objects used to write and format output as sequences of characters. Specific members are provided to perform these output operations, which can be divided in two main groups:

Formatted output
These member functions interpret and format the data to be written as sequences of characters. These type of operation is performed using member and global functions that overload the insertion operator (operator<<).
Unformatted output
Most of the other member functions of the ostream class are used to perform unformatted output operations, i.e. output operations that write the data as it is, with no formatting adaptations. These member functions can write a determined number of characters to the output character sequence (put, write) and manipulate the put pointer (seekp, tellp).

Additionaly, a member function exists to synchronize the stream with the associated external destination of characters: sync.

The standard objects cout, cerr and clog are instantiations of this class.

The class inherits all the internal fields from its parent classes ios_base and ios:

Formatting information

format flags: a set of internal indicators describing how certain input/output operations shall be interpreted or generated. The state of these indicators can be obtained or modified by calling the members flags, setf and unsetf, or by using manipulators.
field width: describes the width of the next element to be output. This value can be obtained/modified by calling the member function width or parameterized manipulator setw.
display precision: describes the decimal precision to be used to output floating-point values. This value can be obtained/modified by calling member precision or parameterized manipulator setprecision.
fill character: character used to pad a field up to the field width. It can be obtained or modified by calling member function fill or parameterized manipulator setfill.
locale object: describes the localization properties to be considered when formatting i/o operations. The locale object used can be obtained calling member getloc and modified using member imbue.

State information

error state: internal indicator reflecting the integrity and current error state of the stream. The current object may be obtained by calling rdstate and can be modified by calling clear and setstate. Individual values may be obtained by calling good, eof, fail and bad.
exception mask: internal exception status indicator. Its value can be retrieved/modified by calling member exceptions.

Other

event function stack: stack of pointers to callback functions that are called when certain events occur. Additional callback functions may be registered to be called when an event occurs, using member function register_callback.
internal extensible arrays: two internal arrays to store long objects and void pointers. These arrays can be extended by calling member function xalloc, and references to these objects can be retrieved with iword or pword.
pointer to tied stream: pointer to the stream object which is tied to this stream object. It can be obtained/modified by calling member function tie.
pointer to stream buffer: pointer to the associated streambuf object. It can be obtained/modified by calling member function rdbuf.

Public members

(constructor)

Construct object (constructor member)

(destructor)

Destruct object (destructor member)

Formatted output:

operator<<

Insert data with format (public member function)

Unformatted output:

put

Put character (public member function)

write

Write block of data (public member function)

Positioning:

tellp

Get position of put pointer (public member function)

seekp

Set position of put pointer (public member function)

Synchronization:

flush

Flush output stream buffer (public member function)

Prefix/Suffix:

sentry

Perform exception safe prefix/suffix operations (public member classes)

Member functions inherited from ios

good

Check if the state of the stream is good for i/o operations. (public member function)

eof

Check if eofbit is set (public member function)

fail

Check if either failbit or badbit is set (public member function)

bad

Check if badbit is set (public member function)

operator!

Evaluate stream object (public member function)

operator void*

Convert to pointer (public member function)

rdstate

Get error state flags (public member function)

setstate

Set error state flag (public member function)

clear

Set error state flags (public member function)

copyfmt

Copy formatting information (public member functions)

fill

Get/set the fill character (public member function)

exceptions

Get/set exception mask (public member function)

imbue

Imbue locale (public member function)

tie

Get/set the tied stream (public member function)

rdbuf

Get/set the associated stream buffer (public member function)

narrow

Narrow character (public member function)

widen

Widen character (public member function)

Member functions inherited from ios_base

flags

Get/set format flags (public member function)

setf

Set specific format flags (public member function)

unsetf

Clear specific format flags (public member function)

precision

Get/Set floating-point decimal precision (public member function)

width

Get/set field width (public member function)

imbue

Imbue locale (public member function)

getloc

Get current locale (public member function)

xalloc

Return a new index for the internal extensible array [static] (public static member function)

iword

Get reference to integer element of the internal extensible array (public member function)

pword

Get reference to pointer of the internal extensible array (public member function)

register_callback

sync_with_stdio

Activate/deactivate synchronization of iostream and cstdio streams [static] (public static member function)

istream

class

<istream>

Input stream

ios_base	ios	istream	iostream
			ifstream
			istringstream

istream objects are stream objects used to read and interpret input from sequences of characters. Specific members are provided to perform these input operations, which can be divided in two main groups:

Formatted input
These functions extract data from a sequence of characters that may be interpreted and formatted to a value of a certain type. These type of operation is performed using member and global functions that overload the extraction operator ().
Unformatted input
Most of the other member functions of the istream class are used to perform unformatted input, i.e. no interpretation is made on the characters got form the input. These member functions can get a determined number of characters from the input character sequence (get, getline, peek, read, readsome), manipulate the get pointer i(ignore, seekg, tellg, unget) or get information of the last unformatted input operation (gcount).

Additionaly, a member function exists to synchronize the stream with the associated external source of characters: sync.

The standard object cin is an instantiation of this class.

The class inherits all the internal fields from its parent classes ios_base and ios:

Formatting information

format flags: a set of internal indicators describing how certain input/output operations shall be interpreted or generated. The state of these indicators can be obtained or modified by calling the members flags, setf and unsetf, or by using manipulators.
field width: describes the width of the next element to be output. This value can be obtained/modified by calling the member function width or parameterized manipulator setw.
display precision: describes the decimal precision to be used to output floating-point values. This value can be obtained/modified by calling member precision or parameterized manipulator setprecision.
fill character: character used to pad a field up to the field width. It can be obtained or modified by calling member function fill or parameterized manipulator setfill.
locale object: describes the localization properties to be considered when formatting i/o operations. The locale object used can be obtained calling member getloc and modified using member imbue.

State information

error state: internal indicator reflecting the integrity and current error state of the stream. The current object may be obtained by calling rdstate and can be modified by calling clear and setstate. Individual values may be obtained by calling good, eof, fail and bad.
exception mask: internal exception status indicator. Its value can be retrieved/modified by calling member exceptions.

Other

event function stack: stack of pointers to callback functions that are called when certain events occur. Additional callback functions may be registered to be called when an event occurs, using member function register_callback.
internal extensible arrays: two internal arrays to store long objects and void pointers. These arrays can be extended by calling member function xalloc, and references to these objects can be retrieved with iword or pword.
pointer to tied stream: pointer to the stream object which is tied to this stream object. It can be obtained/modified by calling member function tie.
pointer to stream buffer: pointer to the associated streambuf object. It can be obtained/modified by calling member function rdbuf.

Public members

(constructor)

Construct object (constructor member)

(destructor)

Destruct object (destructor member)

Formatted input:

operator>>

Extract formatted data (public member function)

Unformatted input:

gcount

Get number of characters extracted by last unformatted input operation (public member function)

get

Get unformatted data from stream (public member function)

getline

Get line from stream (public member function)

ignore

Extract and discard characters (public member functions)

peek

Peek next character (public member function)

read

Read block of data (public member function)

readsome

Read block of data available in the buffer (public member function)

putback

Put character back (public member function)

unget

Decrement get pointer (public member function)

Positioning:

tellg

Get position of the get pointer. (public member function)

seekg

Set position of the get pointer (public member function)

Synchronization:

sync

Synchronize input buffer with source of characters (public member function)

Prefix/Suffix:

sentry

Perform exception safe prefix/suffix operations (public member class)

Member functions inherited from ios

good

Check if the state of the stream is good for i/o operations. (public member function)

eof

Check if eofbit is set (public member function)

fail

Check if either failbit or badbit is set (public member function)

bad

Check if badbit is set (public member function)

operator!

Evaluate stream object (public member function)

operator void*

Convert to pointer (public member function)

rdstate

Get error state flags (public member function)

setstate

Set error state flag (public member function)

clear

Set error state flags (public member function)

copyfmt

Copy formatting information (public member functions)

fill

Get/set the fill character (public member function)

exceptions

Get/set exception mask (public member function)

imbue

Imbue locale (public member function)

tie

Get/set the tied stream (public member function)

rdbuf

Get/set the associated stream buffer (public member function)

narrow

Narrow character (public member function)

widen

Widen character (public member function)

Member functions inherited from ios_base

flags

Get/set format flags (public member function)

setf

Set specific format flags (public member function)

unsetf

Clear specific format flags (public member function)

precision

Get/Set floating-point decimal precision (public member function)

width

Get/set field width (public member function)

imbue

Imbue locale (public member function)

getloc

Get current locale (public member function)

xalloc

Return a new index for the internal extensible array [static] (public static member function)

iword

Get reference to integer element of the internal extensible array (public member function)

pword

Get reference to pointer of the internal extensible array (public member function)

register_callback

sync_with_stdio

Activate/deactivate synchronization of iostream and cstdio streams [static] (public static member function)

'Language > C++' 카테고리의 다른 글

<input> cin(), get(), getline() 함수 차이. (0)	2011.04.03
C++ Preprocessor: Always Assert Your Code Is Right (0)	2011.03.25
연산자 오버로딩 (0)	2011.03.14
C++ 에서 setw(int num) 함수를 이용하여 깔끔하게 출력하기! (0)	2011.03.09
virtual 함수, [static binding/dynamic binding] (0)	2011.03.09

Posted by Triany

2011. 3. 14. 20:23

연산자 오버로딩

Language/C++

p + 3

==

p.operator+(3)

class Point {
private:
int x, y;
public:
Point(int _x=0, int _y=0):x(_x), y(_y){}
void ShowPosition();
void operator+(int val); //operator+라는 이름의 함수
};
void Point::ShowPosition()
{
cout<<x<<" "<<y<<endl;
}
void Point::operator+(int val)
{
x+=val;
y+=val;
}//operator+라는 이름의 함수

int main(void)
{
Point p(3,4);
p.ShowPosition();
//p.operator +(10);
p+10;
p.ShowPosition();
return 0;
}

<연산자를 오버로딩하는 방법>
1. 멤버 함수에 의한 오버로딩
2. 전역 함수에 의한 오버로딩

1. 멤버함수에 의한 오버로딩

class Point {
private:
int x, y;
public:
Point(int _x=0, int _y=0):x(_x), y(_y){}
void ShowPosition();
void operator+(int val); //operator+라는 이름의 함수
Point operator+(const Point & p);
};
void Point::ShowPosition()
{
cout<<x<<" "<<y<<endl;
}
void Point::operator+(int val)
{
x+=val;
y+=val;
}//operator+라는 이름의 함수

Point Point::operator+(const Point & p)
{
Point temp(x+p.x, y+p.y);
return temp;
}

int main(void)
{
Point p1(1, 2);
Point p2(2, 1);
Point p3=p1+p2;
p3.ShowPosition();
return 0;
}

2. 전역 함수에 의한 오버로딩
클래스에 있는 private로 선언된 변수를 직접 접근하기 위해선,
클래스 내에 friend 선언을 해 두어야 한다.

<오버로딩이 불가능한 연산자>
. .* :: ?: sizeof

++p -> p.operator++()
p++ -> p.operator++(int)

'Language > C++' 카테고리의 다른 글

C++ Preprocessor: Always Assert Your Code Is Right (0)	2011.03.25
ostream/istream (0)	2011.03.14
C++ 에서 setw(int num) 함수를 이용하여 깔끔하게 출력하기! (0)	2011.03.09
virtual 함수, [static binding/dynamic binding] (0)	2011.03.09
키워드 explicit & mutable (0)	2011.03.07

Posted by Triany

2011. 3. 9. 23:10

Skip list _ wikipedia

자료구조

From Wikipedia, the free encyclopedia

Jump to: navigation, search

Part of a series on Probabilistic data structures
Bloom filter · Skip list
Random trees
Random binary tree · Treap Rapidly-exploring random tree
Related
Randomized algorithm
Computer science Portal ·v · d · e

A skip list is a data structure for storing a sorted list of items, using a hierarchy of linked lists that connect increasingly sparse subsequences of the items. These auxiliary lists allow item lookup with efficiency comparable to balanced binary search trees (that is, with number of probes proportional to log n instead of n).

Each link of the sparser lists skips over many items of the full list in one step, hence the structure's name. These forward links may be added in a randomized way with a geometric / negative binomial distribution ^[1]. Insert, search and delete operations are performed in logarithmic expected time. The links may also be added in a non-probabilistic way so as to guarantee amortized (rather than merely expected) logarithmic cost.

[hide]

[edit] Description

A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p (two commonly-used values for p are 1/2 or 1/4). On average, each element appears in 1/(1-p) lists, and the tallest element (usually a special head element at the front of the skip list) in $\log_{1/p} n\,$ lists.

A search for a target element begins at the head element in the top list, and proceeds horizontally until the current element is greater than or equal to the target. If the current element is equal to the target, it has been found. If the current element is greater than the target, the procedure is repeated after returning to the previous element and dropping down vertically to the next lower list. The expected number of steps in each linked list is at most 1/p, which can be seen by tracing the search path backwards from the target until reaching an element that appears in the next higher list or reaching the beginning of the current list. Therefore, the total expected cost of a search is $(\log_{1/p} n)/p,\,$ which is $\mathcal{O}(\log n)\,$ when p is a constant. By choosing different values of p, it is possible to trade search costs against storage costs.

[edit] Implementation details

The elements used for a skip list can contain more than one pointer since they can participate in more than one list.

Insertions and deletions are implemented much like the corresponding linked-list operations, except that "tall" elements must be inserted into or deleted from more than one linked list.

Θ(n) operations, which force us to visit every node in ascending order (such as printing the entire list), provide the opportunity to perform a behind-the-scenes derandomization of the level structure of the skip-list in an optimal way, bringing the skip list to $\mathcal{O}(\log n)$ search time. (Choose the level of the i'th finite node to be 1 plus the number of times we can repeatedly divide i by 2 before it becomes odd. Also, i=0 for the negative infinity header as we have the usual special case of choosing the highest possible level for negative and/or positive infinite nodes.) However this also allows someone to know where all of the higher-than-level 1 nodes are and delete them.

Alternatively, we could make the level structure quasi-random in the following way:

make all nodes level 1
j ← 1
while the number of nodes at level j > 1 do
  for each i'th node at level j do
    if i is odd 
      if i is not the last node at level j
        randomly choose whether to promote it to level j+1
      else
        do not promote
      end if
    else if i is even and node i-1 was not promoted
      promote it to level j+1
    end if
  repeat
  j ← j + 1
repeat

Like the derandomized version, quasi-randomization is only done when there is some other reason to be running a Θ(n) operation (which visits every node).

The advantage of this quasi-randomness is that it doesn't give away nearly as much level-structure related information to an adversarial user as the de-randomized one. This is desirable because an adversarial user who is able to tell which nodes are not at the lowest level can pessimize performance by simply deleting higher-level nodes. The search performance is still guaranteed to be logarithmic.

It would be tempting to make the following "optimization": In the part which says "Next, for each i'th...", forget about doing a coin-flip for each even-odd pair. Just flip a coin once to decide whether to promote only the even ones or only the odd ones. Instead of Θ(n lg n) coin flips, there would only be Θ(lg n) of them. Unfortunately, this gives the adversarial user a 50/50 chance of being correct upon guessing that all of the even numbered nodes (among the ones at level 1 or higher) are higher than level one. This is despite the property that he has a very low probability of guessing that a particular node is at level N for some integer N.

This article may contain original research. Please improve it by verifying the claims made and adding references. Statements consisting only of original research may be removed. More details may be available on the talk page. (May 2008)

The following proves these two claims concerning the advantages of quasi-randomness over the totally derandomized version. First, to prove that the search time is guaranteed to be logarithmic. Suppose a node n is searched for, where n is the position of the found node among the nodes of level 1 or higher. If n is even, then there is a 50/50 chance that it is higher than level 1. However, if it is not higher than level 1 then node n-1 is guaranteed to be higher than level 1. If n is odd, then there is a 50/50 chance that it is higher than level 1. Suppose that it is not; there is a 50/50 chance that node n-1 is higher than level 1. Suppose that this is not either; we are guaranteed that node n-2 is higher than level 1. The analysis can then be repeated for nodes of level 2 or higher, level 3 or higher, etc. always keeping in mind that n is the position of the node among the ones of level k or higher for integer k. So the search time is constant in the best case (if the found node is the highest possible level) and 2 times the worst case for the search time for the totally derandomized skip-list (because we have to keep moving left twice rather than keep moving left once).

Next, an examination of the probability of an adversarial user's guess of a node being level k or higher being correct. First, the adversarial user has a 50/50 chance of correctly guessing that a particular node is level 2 or higher. This event is independent of whether or not the user correctly guesses at some other node being level 2 or higher. If the user knows the positions of two consecutive nodes of level 2 or higher, and knows that the one on the left is in an odd numbered position among the nodes of level 2 or higher, the user has a 50/50 chance of correctly guessing which one is of level 3 or higher. So, the user's probability of being correct, when guessing that a node is level 3 or higher, is 1/4. Inductively continuing this analysis, we see that the user's probability of guessing that a particular node is level k or higher is 1/(2^(k-1)).

The above analyses only work when the number of nodes is a power of two. However, because of the third rule which says, "Finally, if i is odd and also the last node at level 1 then do not promote." (where we substitute the appropriate level number for 1) it becomes a sequence of exact-power-of-two-sized skiplists, concatenated onto each other, for which the analysis does work. In fact, the exact powers of two correspond to the binary representation for the number of nodes in the whole list.

A skip list, upon which we have not recently performed either of the above mentioned Θ(n) operations, does not provide the same absolute worst-case performance guarantees as more traditional balanced tree data structures, because it is always possible (though with very low probability) that the coin-flips used to build the skip list will produce a badly balanced structure. However, they work well in practice, and the randomized balancing scheme has been argued to be easier to implement than the deterministic balancing schemes used in balanced binary search trees. Skip lists are also useful in parallel computing, where insertions can be done in different parts of the skip list in parallel without any global rebalancing of the data structure. Such parallelism can be especially advantageous for resource discovery in an ad-hoc Wireless network because a randomized skip list can be made robust to the loss of any single node^[2].

There has been some evidence that skip lists have worse real-world performance and space requirements than B trees due to memory locality and other issues.^[3]

[edit] Indexable skiplist

As described above, a skiplist is capable of fast Θ(log n) insertion and removal of values from a sorted sequence, but it has only slow Θ(n) lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of random access indexed lookups can be improved to Θ(log n).

For every link, also store the width of the link. The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links.

For example, here are the widths of the links in the example at the top of the page:

     1                                         10
  o-----> o-----------------------------------------------------------------------------> o    TOP LEVEL
     1               3                   2                           5
  o-----> o---------------------> o-------------> o-------------------------------------> o    LEVEL 3
     1           2           1           2                           5
  o-----> o-------------> o-----> o-------------> o-------------------------------------> o    LEVEL 2
     1       1       1       1       1       1       1       1       1       1       1
  o-----> o-----> o-----> o-----> o-----> o-----> o-----> o-----> o-----> o-----> o-----> o    BOTTOM LEVEL
                                                                                                
Head   Node1   Node2   Node3   Node4   Node5   Node6   Node7   Node8   Node9   Node10   NIL

Notice that the width of a higher level link is the sum of the component links below it (i.e. the width 10 link spans the links of widths 3, 2 and 5 immediately below it). Consequently, the sum of all widths is the same on every level (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 5).

To index the skiplist and find the i-th value, traverse the skiplist while counting down the widths of each traversed link. Descend a level whenever the upcoming width would be too large.

For example, to find the node in the fifth position (Node 5), traverse a link of width 1 at the top level. Now four more steps are needed but the next width on this level is ten which is too large, so drop one level. Traverse one link of width 3. Since another step of width 2 would be too far, drop down to the bottom level. Now traverse the final link of width 1 to reach the target running total of 5 (1+3+1).

 function lookupByPositionIndex(i)
     node ← head
     i ← i + 1                           # don't count the head as a step
     for level from top to bottom do
          while i ≥ node.width[level] do  # if next step is not too far
              i ← i - node.width[level]  # subtract the current width
              node ← node.next[level]    # traverse forward at the current level
          repeat
     repeat
     return node.value
 end function

This method of implementing indexing is detailed in Section 3.4 Linear List Operations in "A skip list cookbook" by William Pugh.

Also, see Running Median using an Indexable Skiplist for a complete implementation written in Python and for an example of it being used to solve a computationally intensive statistics problem. And see Regaining Lost Knowledge for the history of that solution.

[edit] History

Skip lists were invented in 1990 by William Pugh. He details how they work in Skip lists: a probabilistic alternative to balanced trees in Communications of the ACM, June 1990, 33(6) 668-676. See also citations and downloadable documents.

To quote the inventor:

Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.

[edit] Usages

List of applications and frameworks that use skip lists:

QMap template class of Qt that provides a dictionary.
Redis is an ANSI-C open-source persistent key/value store for Posix systems, using skip lists in its implementation of ordered sets.
skipdb is an open-source database format using ordered key/value pairs.
Running Median using an Indexable Skiplist is a Python implementation of a skiplist augmented by link widths to make the structure indexable (giving fast access to the nth item). The indexable skiplist is used to efficiently solve the running median problem (recomputing medians and quartiles as values are added and removed from a large sliding window).
ConcurrentSkipListSet and ConcurrentSkipListMap in the Java 1.6 API.

[edit] References

^ Pugh, William (June 1990). "Skip lists: a probabilistic alternative to balanced trees". Communications of the ACM 33 (6): 668–676. doi:10.1145/78973.78977.
^ Shah, Gauri Ph.D.; James Aspnes (December 2003) (PDF). Distributed Data Structures for Peer-to-Peer Systems. http://www.cs.yale.edu/homes/shah/pubs/thesis.pdf. Retrieved 2008-09-23.
^ http://resnet.uoregon.edu/~gurney_j/jmpc/skiplist.html

[edit] External links

Skip Lists: A Probabilistic Alternative to Balanced Trees - William Pugh's original paper
"Skip list" entry in the Dictionary of Algorithms and Data Structures
Skip Lists: A Linked List with Self-Balancing BST-Like Properties on MSDN in C# 2.0
SkipDB, a BerkeleyDB-style database implemented using skip lists.
Skip Lists lecture (MIT OpenCourseWare: Introduction to Algorithm)

Demo applets

Skip List Applet by Kubo Kovac
Thomas Wenger's demo applet on skiplists

Implementations

Retrieved from "http://en.wikipedia.org/wiki/Skip_list"

Categories: Linked lists | Probabilistic data structures

Personal tools

Interaction

Toolbox

Print/export

Languages

'자료구조' 카테고리의 다른 글

[Sorting] Sort algorithm 설명 동영상(Insertion, shell, bubble, selection, Quick, Shaker..) (0)	2011.07.16
레드 블랙 트리 (0)	2011.05.04

Posted by Triany

2011. 3. 9. 22:08

atal error C1083: 포함 파일을 열 수 없습니다. 'fstream.h': No such file or directory

tip

c++ 코딩시
visual studio 2008버전에서
atal error C1083: 포함 파일을 열 수 없습니다. 'fstream.h': No such file or directory
라는 오류가 발생하게 되면

visual studio 2008 sp1을 깔면 해결된다.

http://www.microsoft.com/downloads/ko-kr/confirmation.aspx?displaylang=ko&FamilyID=fbee1648-7106-44a7-9649-6d9f6d58056e

NONO!! 이게 해결책이 아니다!!!!!!!!
헤더가 잘못된것...!!!
C++에서는 .h붙는 헤더들을 거의 사용 안한다.
fstream.h 가 아닌 ->> fstream 으로 바꿔줘야 함.
이와 더불어, fstream헤더에 포함된 함수정의로,, 사용해야..
예를 들자면
기존의 6.0버전이 이런 식으로 사용했다면..
void read ( ifstream input_file )
{
listData c;

while ( input_file.get(c) ) {
if (c != ' ' && c != '\n' )
insert(c);
}
}

이렇게 바꿔줘야. (포인터 식으로!)
void read ( ifstream *input_file )
{
listData c;

while ( input_file->get(c) ) {
if (c != ' ' && c != '\n' )
insert(c);
}
}

<답 찾았던 원문참조.>
Sep 26th, 2004

fstream.h, I thought it was a standard header....

Expand Post »

I'm trying to write a simple file output program for my class. The error I recieve when I try to compile in VS .net 2003 is the following.

fatal error C1083: Cannot open include file: 'fstream.h': No such file or directory

The code to my program is extremely straight forward as I always test a concept before incorporating it into the final solution. It's as follows:

C++ Syntax (Toggle Plain Text)
#include <math.h>
#include <fstream.h>
#include <iomanip.h>
 
void main()
{
	int a[25];
	double s[25];
 
	for(int n=0; n < 25; n++)
		s[n] = sin(3.14159265*(a[n]=n*15)/180);
 
	ofstream out("SineDataV2.txt", ios::out);
 
	for(n=0;n<25;n++)
		out << setw(5) << a[n] <<''<<setw(12)<<s[n]<<'\n';
 
	out.close();
}
#include <math.h>
#include <fstream.h>
#include <iomanip.h>

void main()
{
	int a[25];
	double s[25];

	for(int n=0; n < 25; n++)
		s[n] = sin(3.14159265*(a[n]=n*15)/180);

	ofstream out("SineDataV2.txt", ios::out);

	for(n=0;n<25;n++)
		out << setw(5) << a[n] <<''<<setw(12)<<s[n]<<'\n';

	out.close();
}

Any ideas why I can't include it? I'm pretty sure I'm including the correct file as MSDN reference tells me so: http://msdn.microsoft.com/library/de...m_ofstream.asp

Thanks in advance to those that help!

C#Coder

Reputation Points: 11

Solved Threads: 0

Newbie Poster

Offline

19 posts
since Sep 2004

Permalink

Sep 26th, 2004

Re: fstream.h, I thought it was a standard header....

>Any ideas why I can't include it?
Yes, fstream.h is not a standard C++ header. Nor is iomanip.h. Come to think of it, void main isn't standard either (regardless of what your compiler's documentation says). If you want to go fully standard, use C headers with the .h dropped and prefix them with C, and use C++ headers with the .h dropped. Then prefix every standard name with std:: (or you can use using namespace std if you want) because all standard names are in the std namespace. Also, there's no need to manually close the file. ofstream's destructor will handle that for you. Lastly, you had a bug where the first loop declares a variable yet you try to use it after the loop. This is wrong because the variable is declared within the scope of the loop and when the loop ends the variable is destroyed. You can do what you were doing with older versions of Visual C++, but not anymore:

C++ Syntax (Toggle Plain Text)
#include <cmath>
#include <fstream>
#include <iomanip>
 
int main()
{
  int a[25];
  double s[25];
 
  for(int n=0; n < 25; n++)
    s[n] = std::sin(3.14159265*(a[n]=n*15)/180);
 
  std::ofstream out("SineDataV2.txt", std::ios::out);
 
  for(int n=0;n<25;n++)
    out << std::setw(5) << a[n] <<' '<<std::setw(12)<<s[n]<<'\n';
}
#include <cmath>
#include <fstream>
#include <iomanip>

int main()
{
  int a[25];
  double s[25];

  for(int n=0; n < 25; n++)
    s[n] = std::sin(3.14159265*(a[n]=n*15)/180);

  std::ofstream out("SineDataV2.txt", std::ios::out);

  for(int n=0;n<25;n++)
    out << std::setw(5) << a[n] <<' '<<std::setw(12)<<s[n]<<'\n';
}

Narue

Team Colleague

Reputation Points: 4652

Solved Threads: 1046

Code Goddess

Offline

9,544 posts
since Sep 2004

Permalink

Sep 26th, 2004

Re: fstream.h, I thought it was a standard header....

Greetings,

» Any ideas why I can't include it?
It sometimes depends. fstream is part of the C++ standard, fstream.h isn't.

The difference between fstream and fstream.h
fstream is somewhat more restrictive than the older fstream.h. One would possibly avoid problems by careful use of namespaces, but it would be a lot smarter to stick with one or the other.

You should avoid using the *.h version as much as possible, because some implementations have bugs in their *.h version. Moreover, some of them support non-standard code that is not portable, and fail to support some of the standard code of the STL.

Furthermore, the *.h version puts everything in the global namespace. The extension-less version is more stable and it's more portable. It also places everything in the std namespace.

Conclusion
fstream.h is an old style method of including std C++ headers, and in opposite to fstream you don't have to declare that you're using the std namespace.

It is sometimes recommended to use:

(Toggle Plain Text)

#include <fstream>
using namespace std;

Hope this helps,
- Stack Overflow

Stack Overflow

Reputation Points: 26

Solved Threads: 4

C Programmer

Offline

185 posts
since Sep 2004

Permalink

Sep 26th, 2004

Re: fstream.h, I thought it was a standard header....

Thanks Narue and Stack Overflow for your quick and accurate replies!!

All is now good and I can get on with the rest of the lab

C#Coder

Reputation Points: 11

Solved Threads: 0

Newbie Poster

Offline

19 posts
since Sep 2004

Permalink

Jun 1st, 2010

-1

Re: fstream.h, I thought it was a standard header....

출처: http://www.daniweb.com/software-development/cpp/threads/11430

'tip' 카테고리의 다른 글

[tips][한글2010] _ 표 위치 설정~(뒷 페이지로 넘어가게 하기 / 페이지 유지한채 표 넘어가게 하기 등등~) (0)	2011.09.15
Win7 에서 텔넷 사용하기 (0)	2011.07.29
win7 자동재부팅 문제. (0)	2011.02.26
한영 통합자막 만들기 (5)	2011.02.26
[cd -> mp3]WinMP(윈도우미디어플레이어) 사용 CD파일을 mp3파일로 리핑(변환)하기 (0)	2010.09.25

Posted by Triany

2011. 3. 9. 21:06

C++ 에서 setw(int num) 함수를 이용하여 깔끔하게 출력하기!

Language/C++

C에서는 출력양식에서 prinf("%2d", a);
이런 식의 출력양식이 있어서 출력할때 제법 깔끔했다.

하지만, C++언어로 들어온뒤
cout<<a;
식으로 출력할때 %d와 같은 출력 형식을 지정하지 않은 것은 편했지만, 예쁘게(?) 출력이 안되는게 고민이었다.
이때 해결책이 setw(int num) 함수다.ㅎ

setw(int num)
헤더 : #include <iomanip.h>

가령
cout<<setw(7)<<"Hey~"<<endl;
라고 입력하게 되면,
"Hey~ " 이렇게 3자리 공백과 함께 출력된다.

잘만 사용하면 제법 깔끔해 보이는 프로그래밍을 할 듯 싶다.

'Language > C++' 카테고리의 다른 글

ostream/istream (0)	2011.03.14
연산자 오버로딩 (0)	2011.03.14
virtual 함수, [static binding/dynamic binding] (0)	2011.03.09
키워드 explicit & mutable (0)	2011.03.07
static 멤버변수 / 멤버함수(클래스 변수, 클래스 함수) (0)	2011.03.07

Posted by Triany

1 ···12 13 14 15 16 17 18 ···23

'분류없음'에 해당되는 글 224건

[편집] 삽입(Insertion)

'자료구조' 카테고리의 다른 글

'Simple's.... > 일상' 카테고리의 다른 글

'Language > C++' 카테고리의 다른 글

'Language > C++' 카테고리의 다른 글

'Simple's.... > 일상' 카테고리의 다른 글

Public members

Member functions inherited from ios

Member functions inherited from ios_base

istream

Public members

Member functions inherited from ios

Member functions inherited from ios_base

'Language > C++' 카테고리의 다른 글

'Language > C++' 카테고리의 다른 글

Contents

[edit] Description

[edit] Implementation details

[edit] Indexable skiplist

[edit] History

[edit] Usages

[edit] References

[edit] External links

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

Interaction

Toolbox

Print/export

Languages

'자료구조' 카테고리의 다른 글

fstream.h, I thought it was a standard header....

Re: fstream.h, I thought it was a standard header....

Re: fstream.h, I thought it was a standard header....

Re: fstream.h, I thought it was a standard header....

Re: fstream.h, I thought it was a standard header....

'tip' 카테고리의 다른 글

'Language > C++' 카테고리의 다른 글

카테고리

공지사항

태그목록

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함

링크

달력

티스토리툴바