IT's me

[C++ STL] C++의 선형 검색

전 포스팅에서 보았던 C로 작선된 find1은 char 형식의

배열만을 검색할 수 있었다. C++의 경우에는 템플릿을

이용해서 함수 인수의 형식을 매개변수화할 수 있으므로,

find1을 char 이외의 형식에 대해 일반화하는 것이 가능하다.

template <typename T>

T* find2 (T* first , T* last, T value);

상당히 명백하고도 직관적인 일반화이다.

하지만 STL은 약간은 덜 명백한 일반화를 사용한다.

template <typename Iterator. typename T>

Iterator find (Iterator first, Iterator last, const T& value){

while (first != last && *first != value)

++first;

return first;

}

이런 형태의 find가 find2보다 나은 점은 무엇일까?

find가 더욱 일반적이라는 데 있다. find2에는 

first, last가 포인터이어야 한다는 테한이 있지만,

find에는 그런 제한이 없다. 물론 포인터 연산의

구문을 사용하기는 하지만, Iterator가 반드시

포인터이어야 하는 것은 아니다. 

Iterator가 포인터 같은 인터페이스를 지원하기만 하면 된다.

find는 1차원적인 요소들의 순차열이라는 개념을 지원하는

임의의 자료구조에 대해 검색을 수행하는 하나의 일반적 알고리즘이다.

1. 선형 검색을 위해 필요한 것은, 하나의 요소를 조사하고,

2. 다음 요소로 넘어가고, 3. 모든 요소들을 처리했는지 판정하는 것이다.

[C++ STL] C의 선형 검색

선형적인 구간에 대해 작동하는 알고리즘의

중요한 아이디어에 대해 이야기해보자.

선형적인 구간이란, 하나의 첫 번째 요소와 하나의 마지막

요소가 존재하며, 마지막 요소를 제외한 모든 요소들에는 '그 다음 요소'가 있고,

첫 번째 요소에서 시작해서 다음 요소들을 계속 따라가다 보면 마지막 요소에

도달하게 되는 1차원적인 요소들의 모음을 말한다. 이러한 선형적인 구간들에

대해 작동하는 알고리즘들이 STL의 핵심부를 이루고 있다.

C의 선형 검색

C의 라이브러리 함수 strchr을 보도록 하자.

char* strchr(char* s, int c);

char* strchr( char* s, int c){

while ( *s != '\0' && *s != c)

++s;

return *s == c ? s : (char*) 0;

}

선형 검색의 일반적인 아이디어는

1. 순차열의 시작에서부터 요소 하나씩 거쳐가면서 주어진 값다 비교한다

2. 현재 요소가 주어진 값과 같으면, 알고리즘은 순차열 안에서의 현재 요소를 리턴

3. 같지 않다면 다음 요소로 넘어간다.

4. 다음 요소가 없다면 실패했음을 알리는 뭔가를 리턴

이러한 선형 검색을 구현할 때에는 몇 가지 이슈가 있다.

1. 검색하고자 하는 순차열을 어떻게 지정할 것인가?

2. 순차열 안의 한 위치를 어떻게 표현할 것인가?

3. 다음 요소로 넘어가려면 어떻게 할 것인가?

4. 순차열의 끝에 도달했음을 어떻게 알아낼 것인가?

5. 실패했음을 알리는 값으로 무엇을 사용할 것인가?

1. ctrchr 함수를 호출할 때 검색할 문자열의 첫 번째 요소를

가리키는 포인터를 넘겨준다.

2. 문자열 안의 한 위치 또한 포인터로 나타낸다.

3. 포인터 연산을 통해 접근한다.

4. 검색할 순차열은 하나의 C문자열, 즉 널로 끝나는 문자열이다.

때문에 현재 포인터가 \0을 가르킨다면 끝에 도달한 것

5. 선형 검색을 하는 동안 해당 문자를 찾지 못했다면

포인터는 문자열의 끝에 가 있을 것이므로 널 포인터를 리턴.

하지만 strchr은 일반적이지 않다. 이 함수는 char들의 배열 안에서

하나의 char를 검색하는 데에만 사용할 수 있다.

그리고, strchr의 첫 번째 인수는 널 종료 문자 배열을 가리키는

하나의 포인터이어야 하는데, 이는 보기보다 일반적이지 않다.

C에서는 널 종료 문자열이 대부분이긴하지만 부분문자열을

표현하려한다면 문제각 생기는 것도 사실이다.

부분 문자열을 지원하기 위해 strchr의 인터페이스를 수정해보자.

검색할 배열의 끝을 가리키는 포인터를 또 다른 인수로 지정해 보자.

char* find1 (char* first, char* last, int c){

while (first != last && *first != c)

++first;

return first;

}

이 find1 구현은 배열의 끝을 루프 반복의 종료 조건으로 해서

포인터로 배열을 훑는, 흔히 볼 수 있는 C관용구를 이용한다.

이 루프는 first가 last와 같으면 즉시 끝나며, 따라서 last는

역참조 되지 않는다. 즉, last 바로 전까지 모든 요소를 검색한다.

위의 함수에서는 3가지 포인터들이 사용된다.

1. 역참조할 수 있는 보통의 포인터

2. NULL 같은 유효하지 않은 포인터

3. 역참조할 수 없지만 포인터 산술에 사용할 수 있는 끝을 넘어선 포인터

char A[N];

C의 모든 배열에는 끝을 넘어선 포인터가 하나 존재한다. (A+N)

아무것도 가리키지 않기 때문에 역참조해서는 안되며,

딱 하나만 있으므로 포인터를 증가시키려 해서도 안된다.

오직 포인터 산술 연산에만 사용된다. (시작 이전 포인터 같은 것은 없다. A-1과 같은 ... )

[C#] 가비지 컬렉터 (Garbage Collector) 의 원리, 동작 메커니즘

CLR은 어떻게 메모리에 객체를 할당하는가?

C#으로 작성한 소스코드를 컴파일하고 이 파일을 실행하면,

CLR은 이 프로그램을 위한 일정 크기의 메모리를 확보한다.

C-런타임처럼 메모리를 쪼개는 일은 하지 않는다.

넓은 메모리 공간을 통째로 확보해서 하나의 관리되는 힙 (Managed Heap)을

마련한다. 그리고 CLR은 이렇게 확보한 관리되는 힙의 첫 번째 주소에

"다음 객체를 할당할 메모리의 포인터"를 위치 시킨다.

여기에 첫 번째 객체를 할당해보자.

object A = new object();

CLR이 코드를 실행하면 "다음 객체를 할당할 메모리의 포인터"가

가리키고 있는 주소에 A객체를 할당하고 포인터를 A 객체가

차지하고 있는 공간 바로 뒤로 이동시킨다.

또 다른 객체를 하나 만들어보자.

object B = new object();

보시다시피 CLR은 객체가 위치할 메모리를 할당하기

위해 메모리 공간을 쪼개 만든 연결 리스트를 탐색하는 시간과

재조정하는 작업도 필요하지 않다. 그저 메모리만 할당할 뿐

그렇다면 언제, 어떻게 메모리에서 해제될까?

일단 쓰레기인지 아닌지를 판별해야 하지 않을까?

if (true){

object a = new object();

}

객체의 내용물은 힙에, A가 위치한 힙 메모리 주소는 a에 있다.

if 의 블록이 끝나면 a는 없어지게 된다.

그렇다면 A는..?

a를 잃은 채 힙에 남아 있는 객체 A는 이제 코드의 어디에서도

접근할 수 없기 때문에 더 이상 사용할 수 없게 되었다.

즉 쓰레기가 되고, 가비지 컬렉터가 집어가게 된다.

가비지 컬렉터의 원리, 동작 메커니즘

사라져버린 a처럼 할당된 메모리의 위치를 참조하는 객채를 일컬어

루트(Root)라고 부른다. 루트는 a의 경우처럼 스택에 생성될 수도 있고

정적 필드처럼 힙에 생성될 수도 있다. .NET 에플리케이션이 실행되면

jit 컴파일러가 이 루트들을 목록으로 만들고, CLR은 이 루트 목록을

관리하며 상태를 갱신한다. 이 루트가 중요한 이유는 가비지 컬렉터가

CLR이 관리하고 있던 루트 목록을 참조해서 쓰레기를 수집하기 때문.

1. 작업을 시작하기 전에, 가비지 컬렉터는 모든 객체가 쓰레기라고 가정.

루트 목록 내의 어떤 루트도 메모리를 가리키지 않는다고 가정.

2. 루트 목록을 순회하면서 각 루트가 참조하고 있는 힙 객체와의

관계 여부를 조사. 루트가 참조하고 있는 힙의 객체가 또 다른 힙 객체를

참조하고 있다면 이 역시도 해당 루트와 관계가 있는 것으로 판단.

어떤 루트와도 관계가 없다면 쓰레기로 간주.

3. 쓰레기 객체가 차지하고 있던 메모리는 이제 '비어있는 공간'

4. 루트 목록에 대한 조사가 끝나면, 가비지 컬렉터는 이제 힙을

순회하면서 쓰레기가 차지하고 있던 '비어있는 공간'에 쓰레기의

인접 객체들을 이동시켜 차곡차곡 채워 넣는다.

가비지 컬렉터의 원리, 동작 메커니즘에 대해 살펴보았다.

다음 포스팅에서는 가비지 컬렉션의 성능을 높이기 위한

'세대별 가비지 컬렉션' 알고리즘에 대해 알아보겠다.