November 13, 2019 19:41

개요

지난 글에서는 문제 풀이에 있어 상수가 가지는 의미와, 상수 차이에 의해 현저히 드러나는 퍼포먼스의 차이를 몇 가지 실험을 통해 보았습니다. 먼저 입출력 방법에 따라 수십 배 이상도 차이가 벌어질 수 있음을 보았고, std::set과 같이 Red–black tree를 쓰는 자료구조는 std::priority_queue에 비해 같은 연산을 하더라도 훨씬 느리다는 것을 보았습니다. 또한 광범위한 영역의 메모리를 빠르게 특정 값으로 채우거나, 복사하거나, 옮기는 데에는 1바이트씩 반복문을 통해 수행하는 것보다 memset, memcpy, memmove 등의 함수를 사용하는 것이 월등히 빠르다는 것도 살펴보았습니다.

이번 글에서는 지난 글에 이어 문제 풀이 상황에서 자주 마주하게 되는, 유용한 상수 줄이기 테크닉을 여러 가지 추가로 소개하고자 합니다.

캐시 히트

컴퓨터의 메모리는 메인 메모리 하나로만 이루어져 있지 않습니다. CPU의 성능에 비하면 주 메모리로부터 데이터를 읽어오고 쓰는 것은 여전히 컴퓨터의 성능의 병목이라고 할 수 있기 때문에, 그 속도를 향상시키기 위한 노력이 하드웨어에 많이 들어가 있습니다. 그 중 하나가 캐시(cache)입니다.

이 글에서 필요한 부분만 간략하게 설명하자면, 데이터를 주 메모리에서 읽기 위해 매번 I/O를 발생시키는 것은 지나치게 많은 시간을 소요하기 때문에, 일반적으로 하드웨어에는 여러 단계의 캐시들을 두어 자주 사용하는 주소의 메모리를 캐시에 매핑시켜두고 찾고자 하는 주소가 캐시에 존재하는 경우 메인 메모리보다 훨씬 빠르게 접근하여 시간을 줄이는 방법을 사용합니다. 문제는 여기서 ‘자주 사용한다는 것’을 어떻게 측정하는가인데, 이에 대해 대표적으로 사용되는 지표가 바로 공간 집약성과 시간 집약성입니다. 공간 집약성은 최근에 사용한 주소와 가까이 있는 주소를 사용할 가능성이 높다는 것이고, 시간 집약성은 최근에 사용한 주소는 금방 다시 사용할 가능성이 높다는 것입니다.

캐시와 메인 메모리 사이에 데이터가 오고 가는 것 역시 많은 시간을 소요하기에, 캐시에는 한 번에 일정량의 주소를 한 번에 매핑해두고 다른 주소에 의해 교체될 때까지 사용하게 됩니다. 접근하고자 하는 주소가 캐시에 매핑되어있는 경우를 캐시 히트(cache hit)라고 하며, 캐시에 존재하지 않아 메인 메모리로부터 데이터를 가지고 와야 하는 경우를 캐시 미스(cache miss)라고 합니다. 이 부분에서 다루고자 하는 것은 바로 이 캐시 히트의 비율을 높이는 것입니다.

위에서 언급한 공간 집약성과 시간 집약성을 높이기 위해서는 기본적으로 코드가 다음과 같은 특징을 가져야 합니다.

좁은 범위의 메모리에서 오래 작업한다.

이를 지키는 것과 지키지 않는 것의 차이를 보기 위해 간단한 실험을 해보겠습니다. 실험 환경은 지난 글과 같습니다.

#include <bits/stdc++.h>
using namespace std;
​
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
​
	int n, m;
	cin >> n >> m;
​
	int *arr = new int[n];
	int *perm = new int[n];
​
	for (int i = 0; i < n; i++)
	{
		arr[i] = 1;
		perm[i] = i;
	}
​
	random_shuffle(perm, perm + n);

	clock_t st = clock();
​
	long long sum = 0;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
			sum += arr[perm[j]];
	}
​
	clock_t ed = clock();
​
	cout << sum << '\n';
	cout << fixed;
	cout.precision(3);
	cout << "Time: " << (ed - st) / double(CLOCKS_PER_SEC) << " seconds.\n";
}

위 코드는 단순히 크기가 n인 int형 배열 arr을 생성하고, perm 배열을 통해 인덱스의 순서를 무작위로 섞은 뒤 그 순서대로 arr의 원소들에 접근하는 것을 m번 반복합니다. 이 코드에서 random_shuffle을 실행하지 않으면 arr의 원소들도 순차적으로 접근하게 됩니다. 두 코드의 실행 결과를 n과 m에 변화를 주면서 실험한 결과는 다음과 같습니다.

• n=100000, m=100000: 9.315s / 6.080s (약 1.53배)
• n=1000000, m=10000: 37.175s / 6.315s (약 5.89배)
• n=10000000, m=1000: 242.114s / 6.373s (약 37.99배)

루프를 도는 총 횟수에는 거의 차이가 없기 때문에, 공간 집약성이 좋은 코드는 수행 시간 역시 크게 변화가 없는 것을 볼 수 있습니다. 반면에 공간 집약성이 나쁜 코드는 원소의 개수인 n이 커질 때마다 수행 시간이 폭발적으로 증가하는 것을 볼 수 있습니다. 배열의 크기가 커질수록 접근하는 인덱스마다 캐시 미스가 날 확률이 매우 커지기 때문입니다.

이 차이를 결코 무시할 수 없다는 것은 확실해 보입니다. 그렇다면 이를 문제 풀이에서 어떻게 활용할 수 있을까요? 가장 자주 만나면서도 쉽게 실천할 수 있는 곳이 바로 다차원 배열입니다. 다차원 배열에서 가장 낮은 차원은 주소가 연속되어 할당되는 반면, 높은 차원은 인덱스 1당 낮은 차원의 크기만큼의 주소 차이가 있기 때문에 캐시에 매핑된 영역을 금방 넘어서게 됩니다. 그래서 다차원 배열을 순회할 때는 항상 높은 차원의 인덱스들은 고정된 채로 가장 낮은 차원을 연속적으로 모두 본 뒤에 그 다음 차원의 다음 인덱스를 보는 것이 이득입니다.

또한 동적으로 주소를 할당받아 사용하는 링크드 리스트 역시 그다지 집약성이 좋지 않은 자료구조로, 리스트의 길이가 길어질수록 그 효율성이 매우 떨어집니다. 실제로 링크드 리스트를 사용하는 std::list는 std::vector나 std::deque와 같이 연속된 공간에 원소를 저장하는 자료구조에 비해 대부분의 연산에 대한 퍼포먼스가 크게 밀린다는 실험 결과도 있습니다.¹

때로는 주어지는 수의 범위가 배열 하나로 충분히 커버가 가능하더라도(예: 100만), 좌표압축을 통해 입력되는 수의 개수 내로 그 크기를 줄이는 것이(예: 10만) 큰 시간 단축을 끌어낼 수도 있습니다.

실수형을 적게 사용하기

일반적으로 문제 풀이에서 실수형을 사용하게 되는 일은 적지만, 간혹 스페셜 저지²를 통해 오차를 허용하고 실수형의 답을 출력하게 하는 경우가 있습니다.³ 하지만 실수형을 사용하는 데에 조심해야 할 것은 오차 뿐만이 아닙니다. 실수형 연산이 정수형 연산에 비해 느리다는 것 또한 주의 깊게 고려해야 할 사항입니다.

실수형이 얼마나 느린지 실험해보기 위해 다음과 같은 프로그램을 작성하고, 테스트해 봅시다.

#include <bits/stdc++.h>
using namespace std;
​
typedef double T;
​
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
​
	int n;
	cin >> n;
​
	T *arr = new T[n];
	for (int i = 0; i < n; i++)
		arr[i] = rand() % (1 << 16);
​
	clock_t st = clock();
	T sum = 0;
	for (int i = 0; i < n; i++)
		sum += arr[i] * arr[i];
	clock_t ed = clock();
​
	cout << sum << '\n';
	cout.precision(3);
	cout << fixed;
	cout << "Time: "<< (ed - st) / double(CLOCKS_PER_SEC) << " seconds.\n";
}

비교할 코드는 위의 typedef double T;에서 double을 long long으로 바꾼 코드입니다. 실험 환경에서 둘의 크기가 같기 때문에 비교적 공정한 비교가 가능해서 나온 선택입니다.

위의 코드에서 각각 5억을 입력으로 넣은 결과는 다음과 같습니다.

• double: 0.605s
• long long: 0.283s

2배가 조금 넘는 차이라 크지 않아 보이기도 하지만, 루프가 돌 때마다 i가 증가되고 n과의 비교를 하는 연산, 그리고 arr[i]에 접근하는 시간이 모두 포함된 시간이라는 것을 감안해야 합니다. 순수하게 산술연산 시간만을 비교하게끔 만드는 것은 어렵지만, 2배보다는 훨씬 큰 차이가 발생할 것임을 충분히 짐작할 수 있습니다.

이와 같은 사실을 활용할 수 있는 상황으로는 대표적으로 두 정수 좌표 사이의 유클리드 거리를 저장해야 하는 경우, 굳이 double형을 사용하여 제곱하고 더한 뒤 루트를 씌우는 행동을 하는 것보다는 그냥 long long형에 제곱하여 더한 상태로만 저장해서 사용하는 것이 훨씬 효율적이라는 것 등이 있습니다. 실수 연산이 필요하지 않다면, 정수 연산으로만 해결이 가능하다면 가능하면 정수만을 사용하는 것이 정확도 면에서나, 속도 면에서나 우월하다는 것을 인지하고 문제를 푸는 것이 좋겠습니다.

정수 나눗셈을 적게 사용하기

하지만 이와 같이 빠른 정수형에도 치명적인 약점이 있으니, 바로 나누기 연산은 빠르게 처리하지 못한다는 것입니다. 이는 CPU가 사칙연산 중 덧셈, 뺄셈, 곱셈은 병렬적인 회로 구성으로 빠르게 연산하는 것이 가능하지만 나눗셈은 마땅한 방법이 없어 여러 단계를 거쳐야 하기 때문입니다. 여기에서 말하는 나누기 연산은 나머지 연산 역시 포함합니다.

이번에는 아래와 같은 코드를 통해 이를 실험해 봅시다.

#include <bits/stdc++.h>
using namespace std;
​
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
​
	int n;
	cin >> n;
​
	long long *arr = new long long[n];
	for (int i = 0; i < n; i++)
		arr[i] = (long long)rand() + 1;
​
	clock_t st = clock();
	long long sum = 0;
	for (int i = 0; i < n - 6; i++)
		sum += (((((arr[i] / arr[i + 1]) % arr[i + 2]) / arr[i + 3]) % arr[i + 4]) / arr[i + 5]) / arr[i + 6];
    //		sum += (((((arr[i] + arr[i + 1]) - arr[i + 2]) + arr[i + 3]) - arr[i + 4]) + arr[i + 5]) - arr[i + 6];
	clock_t ed = clock();
​
	cout << sum << '\n';
	cout.precision(3);
	cout << fixed;
	cout << "Time: "<< (ed - st) / double(CLOCKS_PER_SEC) << " seconds.\n";
}

sum에 더해가는 과정에서 나눗셈 / 나머지 연산자를 사용한 것과, 덧셈 / 뺄셈 연산자를 사용한 것, 그리고 곱셈 연산자만을 사용한 것을 비교해 보았습니다. 과연 얼마나 차이가 날까요? 입력으로 1억을 넣고 실험해 보았습니다.

• 나눗셈 / 나머지: 6.270s
• 덧셈 / 뺄셈: 0.112s
• 곱셈 (오버플로 방지를 위해 원소의 값은 1~10으로 설정): 0.180s

정말 믿을 수 없도록 큰 차이가 납니다! 정수 연산이라고 안심하지 말고, 나눗셈의 횟수 역시 줄일 수 있는 곳이라면 최대한 줄이는 것이 퍼포먼스 향상에 큰 도움이 된다는 것을 인지하는 것이 좋겠습니다.

비트 연산자를 이용한 정수 집합

이번에는 조금 더 구체적인 구현체를 만들어 특정 연산들을 효율적으로 수행해내는 것을 보이려 합니다. 바로 비트 연산자들을 사용하여 std::set<int>의 연산, 또는 그것이 수행하기 어려운 연산들을 수행하는 것입니다. 거의 같은 기능을 std::bitset도 해주지만, 내부 로직을 이해하고 확장성을 높이기 위해 직접 구현해보도록 하겠습니다. 좀 더 다양한 비트 연산자들의 활용법은 이 글에 제시되어 있습니다.

먼저 이를 구현하기 전에 다음과 같은 연산을 수행해야 하는 상황을 가정해 봅시다.

집합의 각 원소는 [1, 100000] 범위의 정수값을 가진다.

• 집합에 x를 추가하는 연산 (이미 존재하면 무시)
• 집합에서 x를 제거하는 연산 (존재하지 않으면 무시)
• 집합에서 x보다 큰 최소의 수를 찾는 쿼리
• 집합에서 x보다 작은 최대의 수를 찾는 쿼리

여기까지는 std::set으로도 충분히 효율적으로 수행할 수 있지만, 비트 연산자를 써도 문제 풀이에 무리가 없는 속도를 낼 수 있습니다. 만일 주어지는 정수의 범위가 더 크다면 쿼리의 개수 내로 좌표압축을 할 수 있습니다.

거기에, 비트셋은 std::set이 할 수 없거나, 매우 느린 연산들을 추가할 수도 있습니다.

• k번째로 작은 원소 찾기

이 연산은 세그먼트 트리나 GNU pbds를 사용하면 역시 효율적으로 찾는 것이 가능합니다. 하지만 아래와 같은 연산을 효율적으로 하는 것은 매우 어렵습니다.

• 두 집합의 합집합을 구하기

비트셋이 이 연산들을 시간 복잡도상 효율적으로 수행하는 것은 아니지만, 때로는 일반적인 생각으로는 절대 통과될 수 없을 것 같은 제한의 문제를 통과할 수 있게 해줄 정도로 빠르게 만들어주기도 합니다. 이 모든 연산을 지원하는 비트셋을 구현한 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;
​
typedef unsigned long long ull;
​
const int sz = 100001 / 64 + 1;
​
struct bset {
	ull x[sz];
	bset()
	{
		memset(x, 0, sizeof x);
	}
​
	bset operator|(const bset &o) const {
		bset a;
		for (int i = 0; i < sz; i++)
			a.x[i] = x[i] | o.x[i];
		return a;
	}
​
	bset &operator|=(const bset &o) {
		for (int i = 0; i < sz; i++)
			x[i] |= o.x[i];
		return *this;
	}
​
	inline void add(int val)
	{
		x[val >> 6] |= (1ull << (val & 63));
	}
​
	inline void del(int val)
	{
		x[val >> 6] &= ~(1ull << (val & 63));
	}
​
	int kth(int k)
	{
		int i, cnt = 0;
		for (i = 0; i < sz; i++)
		{
			int c = __builtin_popcountll(x[i]);
			if (cnt + c >= k)
			{
				ull y = x[i];
				int z = 0;
				for (int j = 0; j < 64; j++)
				{
					z += ((x[i] & (1ull << j)) != 0);
					if (cnt + z == k)
						return i * 64 + j;
				}
			}
			cnt += c;
		}
		return -1;
	}
​
	int lower(int z)
	{
		int i = (z >> 6), j = (z & 63);
		if (x[i])
		{
			for (int k = j - 1; k >= 0; k--)
				if (x[i] & (1ull << k))
					return (i << 6) | k;
		}
		while (i > 0)
			if (x[--i])
				for (j = 63;; j--)
					if (x[i] & (1ull << j))
						return (i << 6) | j;
		return -1;
	}
​
	int upper(int z)
	{
		int i = (z >> 6), j = (z & 63);
		if (x[i])
		{
			for (int k = j + 1; k <= 63; k++)
				if (x[i] & (1ull << k))
					return (i << 6) | k;
		}
		while (i < sz - 1)
			if (x[++i])
				for (j = 0;; j++)
					if (x[i] & (1ull << j))
						return (i << 6) | j;
		return -1;
	}
};

bset이 지원하는 각 연산의 수행 과정을 간단히 살펴보겠습니다.

기본 구조 및 초기화

const int sz = 100001 / 64 + 1;

...

ull x[sz];
bset()
{
	memset(x, 0, sizeof x);
}

이것이 전부입니다. 편의를 위해 unsigned long long의 크기가 8바이트인 환경을 가정하여, 10만까지의 원소를 표현하기 위해 서는 10만 개의 비트가 필요하므로, unsigned long long의 크기의 8배로 나눈 개수만큼만 가지고 있으면 됩니다. k라는 원소는 x[k / 64]의 k % 64번째 비트로 나타낼 수 있습니다.

이전 글에서 언급한 것과 같이 초기화는 memset으로 수행하여 퍼포먼스의 향상을 노리고 있습니다.

원소 추가/제거

우선 가장 기본적인 연산인 단순 원소 추가/제거 연산부터 살펴 보겠습니다. 이 부분에 해당하는 코드는 다음과 같습니다.

inline void add(int val)
{
	x[val >> 6] |= (1ull << (val & 63));
}
​
inline void del(int val)
{
	x[val >> 6] &= ~(1ull << (val & 63));
}

위에서 언급한 것처럼 val번째 원소를 찾아가고 있는데, 여기서도 이전에 나온 것처럼 최대한 나눗셈 연산을 사용하지 않기 위해 모두 비트 연산으로 처리하고 있습니다. 음이 아닌 정수를 64로 나누는 것은 오른쪽으로 6비트 시프트하는 것과 같고, 64로 나눈 나머지는 63(2진법으로 111111)과 AND 연산을 한 것과 같은 효과를 내기 때문입니다.

아래와 같은 테스트 코드를 사용하여 성능을 평가해 보았습니다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
​
	int n;
	cin >> n;
	int *arr = new int[n];
	for (int i = 0; i < n; i++)
	{
		arr[i] = rand() % 100000 + 1;
		if (rand() % 2)
			arr[i] = -arr[i];
	}
​
	clock_t st = clock();
	bset s;
	for (int i = 0; i < n; i++)
	{
		if (arr[i] > 0)
			s.add(arr[i]);
		else
			s.del(arr[i]);
	}
	clock_t ed = clock();
​
	cout.precision(3);
	cout << fixed;
	cout << "Time: " << (ed - st) / double(CLOCKS_PER_SEC) << " seconds.\n";
}

이 코드에 1억의 입력을 주고 테스트한 결과는 0.142초였습니다. 이 연산은 $O(1)$이니 그리 놀랍지 않은 결과입니다.

upper_bound 연산

그러면 이번에는 시간 복잡도가 나쁜 연산들인 upper bound와 lower bound⁴에 대해 살펴 보겠습니다. 이 부분을 bset은 아래와 같이 구현했습니다.

int lower(int z)
{
	int i = (z >> 6), j = (z & 63);
	if (x[i])
	{
		for (int k = j - 1; k >= 0; k--)
			if (x[i] & (1ull << k))
				return (i << 6) | k;
	}
	while (i > 0)
		if (x[--i])
			for (j = 63;; j--)
				if (x[i] & (1ull << j))
					return (i << 6) | j;
	return -1;
}
​
int upper(int z)
{
	int i = (z >> 6), j = (z & 63);
	if (x[i])
	{
		for (int k = j + 1; k <= 63; k++)
			if (x[i] & (1ull << k))
				return (i << 6) | k;
	}
	while (i < sz - 1)
		if (x[++i])
			for (j = 0;; j++)
				if (x[i] & (1ull << j))
					return (i << 6) | j;
	return -1;
}

둘의 동작은 서로 대칭이기 때문에 매우 비슷합니다. upper를 기준으로 설명하자면,

1. z번 원소가 속한 64비트 단위의 칸(i)과 비트 번호(j)를 찾는다.
2. 해당 칸이 0이 아니면 먼저 그 칸을 j + 1번째부터 63번째 비트까지 검사하여 존재하는 원소를 발견하면 바로 반환한다.
3. i + 1번째 칸부터 sz - 1번째 칸까지 검사하여 0이 아닌 칸을 찾고, 찾으면 그 내에서 다시 0번째 비트부터 확인하여 처음으로 켜져 있는 비트를 찾아 해당 값을 반환한다.

이 코드는 분명히 $O(원소범위)$입니다. 이 상황에서는 원소의 수를 10만 이하로 가정했으므로, 대략 10만 번 정도의 연산이 최악의 경우에 필요하게 됩니다. 존재하는 원소를 빨리 찾으면 그만큼 빨라지고, 못 찾으면 그만큼 느려지는 구조입니다.

하지만 문제 풀이라면 결국 중요한 건 그냥 시간 내에 들어오는 것입니다. 최악의 경우를 20만 번 수행하는 쿼리를 시간 내에 반복할 수 있을까요?

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
​
	clock_t st = clock();
	bset s;
	s.add(1);
	int sum = 0;
	for (int i = 0; i < 199999; i++)
		sum += s.upper(1);
	clock_t ed = clock();
​
	cout << sum << '\n';
	cout.precision(3);
	cout << fixed;
	cout << "Time: " << (ed - st) / double(CLOCKS_PER_SEC) << " seconds.\n";
}

최악의 경우를 상정하여, 1 하나만 원소로 넣고 1보다 큰 원소가 존재하는지를 upper 함수로 199999번 찾게 했습니다. 그러면 처음의 if문에 걸려 62개의 비트를 확인하는 헛수고를 한 뒤, 남은 칸들에 대한 검사를 전부 거쳐야 하므로 10만 개의 원소를 다 보는 것이나 다름없을 것입니다. 그런데 이 코드의 실행 시간은 단 0.154초입니다. 어떻게 이게 가능할까요? 그것은 사실 우리가 봐야 하는 칸의 수는 10만이 아닌, 10만을 64로 나눈 개수인 1563 이기 때문입니다. 큰 덩어리를 묶어서 한 번에 보기 때문에 복잡도에는 차이가 없어도 실제로는 훨씬 빠르게 동작합니다.

k번째 원소 찾기

k번째 원소를 찾는 것도 비슷한 과정입니다. 여기에는 약간의 편법이 들어가는데, 각 칸에 켜져있는 비트의 수를 하나씩 세거나, 원소를 추가하거나 제거할 때마다 카운트를 세는 것은 오버헤드가 크므로, __builtin_popcountll이라는 gcc 내장 함수를 사용해서 그 작업을 빠르게 수행합니다.

int kth(int k)
{
	int i, cnt = 0;
	for (i = 0; i < sz; i++)
	{
		int c = __builtin_popcountll(x[i]);
		if (cnt + c >= k)
		{
			ull y = x[i];
			int z = 0;
			for (int j = 0; j < 64; j++)
			{
				z += ((x[i] & (1ull << j)) != 0);
				if (cnt + z == k)
					return i * 64 + j;
			}
		}
		cnt += c;
	}
	return -1;
}

가장 작은 칸부터 시작해서 켜져있는 비트 수를 64개 단위로 센 뒤, k개 넘어가는 순간이 오면 그 칸을 다시 한 비트씩 확인해서 개수를 세어 정확하게 k개가 되는 순간을 찾게 됩니다.

이 코드의 최악의 경우는 집합 내의 원소의 수보다 큰 k, 또는 가장 큰 수에 걸리게 넣었을 때입니다. 이를 위해 다음과 같은 테스트 코드를 돌려봅시다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
​
	clock_t st = clock();
	bset s;
	ull sum = 0;
	s.add(100000);
	for (int i = 0; i < 100000; i++)
		sum += s.kth(1);
	clock_t ed = clock();
​
	cout << sum << '\n';
	cout.precision(3);
	cout << fixed;
	cout << "Time: " << (ed - st) / double(CLOCKS_PER_SEC) << " seconds.\n";
}

0.521초가 나왔습니다. 노트북에서의 실험이기 때문에 보다 좋은 성능의 컴퓨터라면 1초에 20만 번 수행도 가능할 것으로 보입니다.

합집합

이제 지금까지의 연산들 중 가장 강력하다고 할 수 있는 합집합 연산을 수행해 보겠습니다. Disjoint set과 같은 자료구조로 수행하기 어려운 연산들을 위해 정말로 두 집합을 합쳐야 할 때는 결국 모든 원소의 이동을 필요로 하기 때문에 $O(N)$의 시간이 소요되는 것이 불가피한데, 비트셋은 이를 같은 $O(N)$에 대해서도 다른 자료구조에 비해 훨씬 빠르게 수행하는 것을 가능하게 합니다.

이를 위해 두 개의 연산자가 코드에 정의되어 있습니다.

bset operator|(const bset &o) const {
	bset a;
	for (int i = 0; i < sz; i++)
		a.x[i] = x[i] | o.x[i];
	return a;
}
​
bset &operator|=(const bset &o) {
	for (int i = 0; i < sz; i++)
		x[i] |= o.x[i];
	return *this;
}

단순히 sz개의 칸 모두에 대해 비트 OR 연산자로 결과물을 만들게 됩니다. 원래 원소는 10만개이지만, 실제로는 1563개의 칸에 대해서만 수행하기 때문에 상당히 빠릅니다.

이 연산도 20만 번 수행해 보겠습니다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
​
	clock_t st = clock();
	bset s, t;
	t.add(100000);
	for (int i = 0; i < 199999; i++)
		s |= t;
	clock_t ed = clock();

	cout << s.kth(1) << '\n';
	cout.precision(3);
	cout << fixed;
	cout << "Time: " << (ed - st) / double(CLOCKS_PER_SEC) << " seconds.\n";
}

시간은 0.153초가 나옵니다. 일반적으로 절대로 될 것 같지 않아 보이는 약 200억 개의 원소 이동이 이 짧은 시간 내에 수행된 것입니다. 마찬가지로 교집합 연산이나 XOR 연산 역시 같은 방법으로 손쉽게 구현이 가능합니다.

결론

이번 글에서는 크게 네 가지의 상수 최적화 기법을 살펴보았습니다. 먼저 캐시 히트율을 높여 성능을 올리는 방법을 보았고, 실수 연산 대신 정수 연산을 많이 사용하는 것, 정수 나눗셈 대신 다른 사칙연산을 위주로 사용하는 것, 그리고 마지막으로 비트 연산자를 사용한 집합 연산들을 구현하여 속도를 엄청나게 향상시킬 수 있다는 것을 보았습니다.

자료구조의 무게 뿐만 아니라, 이처럼 CPU나 다른 하드웨어들의 특성을 잘 고려하여 코드를 만들면 같은 시간 복잡도로 같은 결과물을 내더라도 그 차이가 하늘과 땅만큼이 될 수 있다는 것을 염두에 두고 문제를 풀면 좋을 것입니다.