STL, ATL 등도 이미 콜렉션 클래스들(std.map, std.vector, CFastArray, CAtlArray, CAtlMap 등)을 제공합니다. 하지만 ProudNet은 STL과 ATL을 모두 사용하기 곤란한 상황에서나, 고속의 성능을 요구하는 상황에서 효과적인 클래스들을 제공합니다.

1.1배열 클래스

Proud.CFastArray는 배열 클래스입니다. 2. 빠른 메모리 관리자를 활용하는 것이 가능합니다.

1.2링크드 리스트 클래스

Proud.CFastList는 링크드 리스트 클래스입니다. 2. 빠른 메모리 관리자를 활용하는 것이 가능합니다.

링크드 리스트의 기초 설명

(아래는 리스트의 편협한(?) 개념입니다. 이미 아시는 분은 넘어가셔도 됩니다.)

배열은 1개의 메모리 블럭에 여러 항목들이 나란히 들어가 있습니다. 반면, 링크드 리스트는 각 항목들을 위한 메모리 블럭이 있고, 각 항목들 간에는 인접 항목들을 가리키는 링크(포인터)로 서로 연결됩니다.

링크드 리스트는 배열과 비교해서 다음과 같은 장단점이 있습니다.

• 장점: 배열과 달리 항목들 사이에 새 항목을 넣거나 구 항목을 빼는 과정에서 뒤에 있는 항목들을 하나씩 이동(shift)할 필요가 없습니다. 즉 삽입/제거가 빠릅니다.

• 단점: 배열과 달리 중간에 특정 항목을 찾으려면 맨 처음 항목부터 링크를 따라 하나 하나 쫓아가야 합니다. 즉 삽입/제거가 느립니다.

1.3맵 클래스

Proud.CFastMap은 맵 클래스입니다. The internal link is invalid.를 활용하는 것이 가능합니다.

맵의 기초 설명

(아래는 맵의 편협한(?) 개념입니다. 이미 아시는 분은 넘어가셔도 됩니다.)

배열이나 링크드 리스트의 한계는 '빠른 찾기가 어렵다' 입니다. 배열이나 링크드 리스트에서 원하는 값을 가진 항목이 어디에 있는지 찾으려면 항목의 맨 앞부터 찾을 때까지 하나 하나 값 비교를 해야 합니다. 하지만 맵은 이를 빠르게 찾게 해줍니다.

검색의 주제를 좁은 범위의 정수형 값으로 환산할 수 있다면 빠른 검색을 할 여지가 있습니다.

검색 대상이 될 모든 항목에 대해서, 각 항목의 값을 좁은 범위의 정수형 값으로 환산하고, 같은 값으로 환산되는 항목끼리는 그룹을 모아놓습니다. 그리고 나서, 특정 값을 가진 항목을 검색하려면, 그 값을 정수형 값으로 환산한 후 대응하는 한 개 그룹 내에서만 원하는 항목을 하나 하나 비교하면 됩니다.

여기에서 좁은 범위의 정수형 값으로 환산하는 것을 해싱(hashing)이라고 하고, 환산된 값을 hash value라고 합니다. 그리고 같은 값으로 환산되는 항목만 모은 그룹을 bucket이라고 하고, 이들 그룹을 뭉뚱그려 hash table이라고 합니다.

맵 클래스의 부하

맵 클래스 가 가진 해시 테이블의 크기와 맵 클래스가 가지고 있는 항목의 갯수는 다음과 같은 관계가 있습니다.

•해시 테이블의 크기에 비해 항목의 갯수가 너무 많으면 검색이 느려집니다. 왜냐하면 bucket 안의 항목 갯수가 많아지게 되고 그만큼 값 비교 연산의 횟수가 늘기 때문입니다.

•해시 테이블의 크기에 비해 항목의 갯수가 너무 적으면 해시 테이블 자체가 차지하는 메모리 공간 낭비가 심해집니다.

따라서 항목의 갯수가 해시 테이블의 크기와 비교해서 기복이 너무 커지게 되면 해시 테이블의 크기를 재설정하는 것이 도움될 수 있습니다. 해시 테이블이 지나치게 모자라면 해시 테이블을 충분히 크게 재설정해야 하겠고, 반대로 해시 테이블이 너무 남아돌면 해시 테이블을 작게 재설정하는 것입니다.

예를 들어, 해시 테이블의 크기가 항목 갯수보다 3배 이상 커지게 되거나 10% 이하로 작아지게 되면 해시 테이블을 재설정하되 항목 갯수가 해시 테이블의 크기의 75만큼 두는 것이 적절하다고 생각할 수 있습니다. 이때 3배를 최대 한계 부하, 10를 최소 한계 부하, 75를 최적 부하라고 표현할 수 있습니다.

맵의 이러한 부하 값을 조절하려면 Proud.CFastMap.CFastMap이나 Proud.CFastMap.SetOptimalLoad로 할 수 있습니다.