글 읽기 - 문제에 한정된 질문이 아닙니다. 구조체의 속도 차이에 관한 질문입니다.

kinssang 4년 전 0

60ms 코드와 436ms 코드 사이의 차이점은 구조체로 묶은 것과 안 묶은 것 정도의 차이 밖에 없는데 속도 차이가 어마무시하게 납니다.

이런 현상이 발생하는 이유가 무엇인지 가르쳐주시면 감사하겠습니다.

// 436ms
#include <stdio.h>

int n, w, h, m;

struct jenga
{
	bool deleted[10001];
	long long sum[2];
	int mn;
	int mx;
	int mass;
};

jenga level[5001];

int main()
{
	scanf("%d %d %d %d", &n, &w, &h, &m);

	for (int i = 1; i <= h; i++)
	{
		level[i].sum[0] = level[i].sum[1] = n*n;
		level[i].mn = 1;
		level[i].mx = n;
		level[i].mass = n;
	}

	for (int i = 1; i <= m; i++)
	{
		int lev, block;

		scanf("%d %d", &lev, &block);

		level[lev].sum[lev % 2] -= (2 * block - 1);
		level[lev].sum[1 - (lev % 2)] -= n;
		level[lev].mass--;
		level[lev].deleted[block] = true;

		while (level[lev].mx >= 1 && level[lev].deleted[level[lev].mx]) level[lev].mx--;
		while (level[lev].mn <= n && level[lev].deleted[level[lev].mn]) level[lev].mn++;
		if (level[lev].mn > level[lev].mx) return !printf("yes\n%d\n", i);

		long long cur_y_sum = 0, cur_x_sum = 0, cur_mass = 0;

		for (int j = h - 1; j >= 1; j--)
		{
			cur_mass += level[j + 1].mass;
			cur_y_sum += level[j + 1].sum[1];
			cur_x_sum += level[j + 1].sum[0];

			if (!cur_mass) continue;

			long long cur_sum = cur_x_sum;
			if (j % 2) cur_sum = cur_y_sum;
			if (2 * (level[j].mn - 1)*cur_mass >= cur_sum || cur_sum >= 2 * level[j].mx*cur_mass) return !printf("yes\n%d\n", i);
		}
	}
	return !printf("no\n");
}

//60ms
#include <stdio.h>

int n, w, h, m;

bool deleted[5001][10001];
int mn[5001], mx[5001], sum[5001][2], mass[5001];

int main()
{
	scanf("%d %d %d %d", &n, &w, &h, &m);

	for (int i = 1; i <= h; i++)
	{
		sum[i][0] = sum[i][1] = n*n;
		mn[i] = 1;
		mx[i] = mass[i] = n;
	}

	for (int i = 1; i <= m; i++)
	{
		int lev, block;

		scanf("%d %d", &lev, &block);

		sum[lev][lev % 2] -= (2 * block - 1);
		sum[lev][1 - (lev % 2)] -= n;
		mass[lev]--;
		deleted[lev][block] = true;

		while (mx[lev] >= 1 && deleted[lev][mx[lev]]) mx[lev]--;
		while (mn[lev] <= n && deleted[lev][mn[lev]]) mn[lev]++;
		if (mn[lev] > mx[lev]) return !printf("yes\n%d\n", i);

		long long cur_y_sum = 0, cur_x_sum = 0, cur_mass = 0;

		for (int j = h - 1; j >= 1; j--)
		{
			cur_mass += mass[j + 1];
			cur_y_sum += sum[j + 1][1];
			cur_x_sum += sum[j + 1][0];

			if (!cur_mass) continue;

			long long cur_sum = cur_x_sum;
			if (j % 2) cur_sum = cur_y_sum;
			if (2 * (mn[j] - 1)*cur_mass >= cur_sum || cur_sum >= 2 * mx[j] * cur_mass) return !printf("yes\n%d\n", i);
		}
	}
	return !printf("no\n");
}

chogahui05 4년 전 1

대략적으로 보았을 때에는 캐시 hit 때문에 그런 것으로 보입니다.

1번째 for loop 말고 안쪽 for loop를 보았을 때..

kinssang 4년 전 0

@chogahui05

가희님 안쪽 for loop라는게 초기화 부분 말고 81번 줄 - 110번 줄 말씀하시는거죠?

캐시 히트는 그냥 어설프게 배열을 시퀀싱하면 주변 원소까지 같이 가져와서 접근이 빨라진다 정도로 생각했는데

이런 식으로 구조체 크기가 너무 크거나 하면 캐시 히트도 잘 안나게 되는 건가요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제에 한정된 질문이 아닙니다. 구조체의 속도 차이에 관한 질문입니다.

kinssang 4년 전 0

chogahui05 4년 전 1

kinssang 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말