메모리 풀 vs malloc 속도 비교

삼성 B형 전체 링크

삼성 C형 전체 링크

 

참고

- 메모리 풀 Memory Pool

- 메모리 풀 vs malloc 속도 비교

- 링크드 리스트 Linked List

- 링크드 리스트 Linked List Tail ver

- 더블 링크드 리스트 Double Linked List
- 더블 링크드 리스트 Double Linked List Tail ver

 

먼저 BOJ 1707 이분 그래프 문제(Linked List 만들기)에서 Make 함수를 malloc으로 바꿔보자.

#include <stdio.h>
#include <malloc.h>

int K, V, E;

typedef struct st
{
	int node;
	struct st *next;
}NODE;

NODE HEAD[20200];
//NODE POOL[202000 * 2]; 메모리풀 관련 코드 삭제
//int pcnt;

int check[20200];

void init()
{
	//pcnt = 0;
    
	for (int i = 1; i <= V;i++) HEAD[i].next = 0, check[i] = 0;
}

void Make(int p, int c)
{
	//NODE *nd = &POOL[pcnt++]; 
	NODE *nd = (NODE*)malloc(sizeof(NODE)); /* malloc으로 변경 */

	nd->node = c;

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

int DFS(int node, int color)
{
	check[node] = color;

	for (NODE *p = HEAD[node].next; p; p = p->next)
	{
		if (check[p->node] == color) return 0;
		if (!check[p->node])
		{
			if (!DFS(p->node, 3 - color)) return 0;
		}
	}

	return 1;
}

int main(void)
{
	scanf("%d", &K);

	for (int tc = 1; tc <= K;tc++)
	{
		int flag;
		scanf("%d %d", &V, &E);

		init();

		for (int i = 0; i < E;i++)
		{
			int p, c;

			scanf("%d %d", &p, &c);
			Make(p, c);
			Make(c, p);
		}

		flag = 0;
		for (int i = 1; i <= V;i++)
		{
			if (!check[i])
			{
				flag = DFS(i, 1);
				if (!flag) break;
			}
		}

		if (flag) printf("YES\n");
		else printf("NO\n");
	}

	return 0;
}

 

첫 번째가 메모리 풀로 푼 경우, 두 번째가 malloc을 이용한 경우이다..

 

메모리 해제를 하는 코드가 없으므로 메모리가 9배 정도 더 소요되었다.

B형에서 메모리 해제를 하지 않으면 무조건 memory crash가 일어난다.

따라서 메모리 해제 코드까지 추가하면 404ms보다 더 느려질 것이다.

 

malloc을 써도 관리만 어렵고 속도에도 좋지 않으므로, 메모리 풀 방식으로 문제를 풀어야 한다.