C로 자료구조를 짤때 노드들의 크기를 변경 가능하게 할 수 있는
글쓴이: thisnome / 작성시간: 금, 2004/01/16 - 11:45오전
B Tree를 구현한다고 하면, 다음과 같이 기본 구조를 잡게 되는데요.. (코드를 자세히 보실 필요는 없구요.. 설명은 아래에.. ^^)
#define M 2
#define MM (M*2+1)
#define STR_SIZE 32
typedef struct _BNODE
{
int n;
char key[MM][STR_SIZE];
struct _BNODE* ptr[MM+1];
} BNODE;
typedef struct _BTREE
{
BNODE* root;
} BTREE;
실제 C코드에서 insert 하는 부분에는 노드가 하나 추가될때마다 malloc 하게 되는데 이런경우 사이즈에 문제가 있습니다.
제가 프로그램상에서 트리를 3~4가지의 각각 다른 용도로 사용하는 경우 어떤 인덱스 키는 길이가 16자리(IP --;), 어떤 경우는 64자리까지도 됩니다.
이런경우 위에 define 되어있는 STR_SIZE를 변경해야 할텐데 프로그램 실행 중간중간에 동적으로 변경될 수 있는 값도 아니고.. 좀 난감합니다.
제가 처한 상황을 글로 표현하자니 참 답답하네용.. C++이나 Java 였다면 쉽게 해결 가능할텐데.. --;
저 파일 자체를 여러가지 다른이름 복사해서 함수 이름들을 모두 다른 이름으로 (예: insert_key_32(), insert_key_16(), insert_key_64()) 하는 무식한 방법말고는 좀더 스마트~ 한 것은 없는지요..
부탁드립니다.
Forums:
key 를 pointer 로 하고 동적할당하면 될 거 같습니다.
실행도중에 크기를 변경하자고 하자면 동적할당 이외에는 방법이 없겠죠.
하지만 이렇게 되면 node 의 동적할당과 복사가 번거롭습니다.
node 하나 동적할당할려면 node 를 malloc 으로 얻고, key 문자열의 크기만큼 key 에 char 배열을 동적할당해야하죠.
복사역시 C++ 는 struct, class 의 member 단위복사와는 달리 통으로 복사되므로 깊은 복사(deep copy) 를 직접 구현하셔야 합니다.
물론 C++ 에서도 key 문자열을 string 으로 만들지 않고 char * 로 만들었다면 마찬가지지요.
insert_key 함수에 대해서는 key 문자열의 크기를 매개변수로 넘겨주는 방식을 생각해 볼 수 있고, 다른 방법으로는 key 문자열을 아예 C 식 문자열인 Null 문자로 끝나는 문자열로 만드는 것이죠.
그러기 위해서는 key 문자열에 Null 문자를 위한 1byte 를 추가확보하셔야 합니다.
이렇게 한다면 strcpy 로 간단히 해결할 수 있습니다.
이래저래 C++, Java 를 쓰시는 분들한테 귀찮고, 복잡한 방식입니다.
하지만 예전에 'C 언어 펀더멘탈'의 저자 전웅씨(18일에 C99 두번째 발표를 KLDP 작은 conference 에서 하죠.)가 말하기를 C 는 그만큼 hidden cost 없다라고 말했던게 기억납니다.
전웅씨 영향을 받아서인지 C++ STL 에 빠져있던 저도 C 의 간결한 style 의code 에 다시 매료되고 있죠.
어쨌든 STL 은 code 가 참 길죠. typedef 써서 줄일 수 있습니다만 저는 작은 source 밖에 작성을 안해서... -_-
한가지 의문이 있습니다. 솔직히 file 처리는 공부를 안해서 잘 모릅니다만 B, B+ tree 는 대용량자료처리에 적합한 것으로 알고 있고, 그래서 file 처리에 많이 사용하는 것으로 아는데요. file 처리에 사용하실 거라면 동적할당을 통한 방법보다는 고정길이로 정해놓고 하는 것이 낫지 않나요?
혹시 program 이 다른 종류의 node 를 같는 tree 를 다양한게 만드나요?
union
union을 사용하세요.
멤버부분이 variable size 라면 역시 malloc 을 하는 것이
멤버부분이 variable size 라면 역시 malloc 을 하는 것이 맞습니다. 하지만 많이들 잘 알고 계시다시피 malloc 는 꽤 cost가 높은 연산이므로 보통 이런식으로 노드가 많으면서 성능이 중요한 프로그램의 경우에는 메모리풀을 따로 작성하는 것이 원칙이라고 해도 좋습니다. 한번 만들어 두시면 두고두고 유용하게 쓰시게 될 테니 이번 기회에 하나 장만하시는게 어떨까요. :-)
C99부터 지원되는 flexible array member를 이용하셔도
C99부터 지원되는 flexible array member를 이용하셔도 될듯합니다..
아래는 간단한 예제입니다..
struct _fam { int a; int b[]; }; struct _fam *fam=malloc(sizeof(struct _fam)+10*sizeof(int)); fam->a=20; for(int i=0;i<10;i++) fam->b[i]=i; printf("fam->a=%d\n",fam->a); for(int i=0;i<10;i++) printf("fam->b[i]=%d\n",fam->b[i]); free(fam);지금 수행중인 프로젝트는 VOIP쪽의 서버인데, 기존 제품이 너무 빈번히
지금 수행중인 프로젝트는 VOIP쪽의 서버인데, 기존 제품이 너무 빈번히 DB에 접속하는 관계로 성능이 않좋다고 하여, 안정화 작업에 새롭게 참여하게 되었습니다. 총 가입 단말정보수를 10만건 정도로 보고 작업했기 때문에 윗분들이 조언해주신 내용처럼 B+Tree 를 메모리풀을 엮어서 사용하였고, 그결과 성능은 만족할만 하게 나온 상태이나..
몇가지 문제가 있었서.. 위에 질문 드렸던 것이구요..
제가 질문을 너무 엉망으로 드렸던것 같네요..
근데 윗분들중에 union을 사용해보라고 하신것은 어떤걸 의미하는지요?
그리고..
위에 부분에서 스트럭쳐가 다음과 같이 변하면..
struct _fam { int a; int b[]; char c[][]; int d[]; };위와같이 변해도 모두 적용 가능한가요?
malloc 할때 스트럭쳐가 a의 크기 + b의 크기 + c의 크기 + d의 크기 합으로 할당되어서 나오지 않을테고 (정렬 안되는 경우에 말입니다..)
b야 문제될게 없지만, c나 d의 경우 시작 주소를 컴퓨터가 어떻게 알고 줄 수 있는지 신기하기만 하네요.. 답변 감사드리고 조금더 도움 주세요~
[/code]
아는데까지 답변.
flexible array member 는 마지막 member 에만 허용되는 예외입니다.
따라서 2개 이상의 member 는 불가능합니다.
union 을 사용하시라는 말씀은 이런 것으로 보입니다.
union key { char name[20]; char ip[64]; }이렇게 한후 struct 안에 key 를 놓고, 64개의 문자가 필요하면 ip 로 20개의 문자가 필요하면 name 으로 쓰라는 뜻이겠죠.
하지만 사실 key 의 type size 는 큰 쪽으로 맞춰지기 때문에 항상 64byte 를 차지하겠죠.
원래 union 은 다른 type 을 하나의 이름과 type 으로 통일하기 위해서 사용하기 때문에 잘못되었다고 말하기는 그렇지만 이상한 방법입니다.
ip 와 name 은 둘다 array of char 이니까요.
마지막으로 memory 에 올리고 작업하면 성능은 올라가겠지만 만약 작업이 복잡하지 않다면 database 의 최적화를 생각해보시는 것도 좋을 것 같습니다.
현업 programmer 시군요. 가끔 능력도 안되는 제가 이런 분들한테 답변을 하면 묘한 기분이 듭니다.
union.
일단 union을 써보라고 한것은 코딩의 편리성을 위해서 권해드린것입니다.
예를 들어..
char key[MM][STR_SIZE];
를
union{
char key16[MM][STR_SIZE16];
char key64[MM][STR_SIZE64];
}ukey;
이렇게 하시면 malloc시에는 "항상" 최대 크기인 STR_SIZE64로
하시면 되고, 길이 16 인덱스를 처리할때는 key16을 , 64일때는
key64를 사용하시면 되겠죠..
위의 답변은.. 님께서 malloc시에 STR_SIZE를 변경하기 어렵다는 점을
해결하는 것에 중점을 두고 답변한 것입니다.
하지만 위와 같이 union을 쓸경우 메모리 낭비가 물론 있겠죠.
key16만을 사용하고 싶어도, key64만큼의 공간을 소비하니까요.
메모리를 줄이는 것이 님의 최대의 목적이라면..
char * key[MM]; 와 같이 선언하세요.
이렇게 하면 노드 추가시 malloc할때
STR_SIZE는 고려할 필요가 없지요
그대신 실제로 노드에 인덱스의 값을 넣기 직전에.
key[i] = malloc(인덱스 길이); 하시면 됩니다.
(MM이 2니까 위의 i는 0 이나 1 이 겠네요)
제가 질문을 잘 이해하고 쓴건지 모르겠네요 8)
답변들 주셔서 감사드립니다.스키마가 그리 복잡한편이 아니어서 디비
답변들 주셔서 감사드립니다.
스키마가 그리 복잡한편이 아니어서 디비쪽의 최적화작업은 잘 되어있는다기 보다 크게 할 것이 없다고 봐야 되구요 (1 call당 디비접속이 4번정도 X 1000건정도 테스트하면 처리하는데 10초 정도는 걸리더군요..)
메모리로 처리하면, 테이블들을 몇개 만들고, 해쉬나 트리등을 덕지덕지 붙여서 인덱싱 하더라도 1초가 한참 안걸리네요.. (대략 50배이상) :shock:
처음 질문의 의도는 5~6 byte짜리 키를 위해 65 byte 키를 사용하는데에 메모리 낭비가 너무 큰게 아닌가 (약간의 속도 손실도 있겠죠..) 하는 것이었습니다.
moonzoo님이 언급하신방법이 유일한 방법인것 같긴 한데 그렇게 하려면 키생성/삭제때에 key에대한 메모리만을 malloc/free 하거나, 그쪽역시 메모리풀을 사용하여 따로 관리하여야 하니 속도에서 어느정도 손해를 볼지 모르겠구요... 사실 그렇게 바꾸려면 머리도 아프고.. (제가 짠 자료구조인데도 다시보면 항상 처음 짜는것 같아요 :lol: )
아~ 시간은 별루 없고.. 다 안해보구 알 수 있는 방법은 없나용? ㅋㅋ
정리하는 의미의 글이었습니다.. 주말 잘 보내세요
ps. 사실 어제밤에 트리쪽의 파일을 모두 복사해서 파일 이름부터 각종 함수들과 사용하는 스트럭쳐들 모두의 이름을 끝에 _8 (의미 : 8byte 키) 을 붙이는 미친짓을 했답니다. --;
킥. 피곤한 일을 하고 계시는군요. 항상 트리 비슷하게 생겨먹은 놈을 컴
킥. 피곤한 일을 하고 계시는군요. 항상 트리 비슷하게 생겨먹은 놈을 컴퓨터에서 쓰기란 피곤 그 자체. 역시 컴퓨터와 variable size 는 공존하기가 힘든게 아닌가 싶어요. 다음세대 컴퓨터는 variable size가 아주 자연스러웠으면 좋겠네요. 흐흐...
댓글 달기