boj 7453번 문제를 통해 보는 int와 long long 으로 선언했을때의 시행 시간의 차이와 cache hit rate를 높이는 방법에 대하여.

일단 현재 더욱 공부를 해야 할 영역이라는 생각이 드는데, 현재까지 발생했던 문제들과 해결 방법, 그리고 관련되어서 공부한 코드 개선 사항들에 대해서 작성하도록 하겠다. 

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
ll a[4'005];
ll b[4'005];
ll c[4'005];
ll d[4'005];
vector<ll> sums;
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sums.push_back(a[i] + b[j]);
		}
	}
	sort(sums.begin(), sums.end());
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			auto ub = upper_bound(sums.begin(), sums.end(), -c[i] - d[j]);
			auto lb = lower_bound(sums.begin(), sums.end(), -c[i] - d[j]);
			ll cnt = ub - lb;
			ans += cnt;
		}
	}
	cout << ans;
}

처음에, 각각의 숫자별로 (1<<28)까지 가능하기 때문에 합을 연산할때 int 범위를 벗어날 수 있겠다 싶어서

각각의 배열들도 모두 long long 으로 선언하고, 두 배열의 합을 우선적으로 담을 vector도 long long 타입으로 선언했다. 

그리고 로직을 작성해서 제출을 했는데, 처음에 시간초과를 받게 되었다. 

찾다보니 시간초과가 났다고 이 로직이 꼭 맞는건 아니라고 하는데(시간초과가 발생한 케이스가 있으면 중지되기 때문에 그 후에 다른 통과들이 모두 통과한다는 보장을 할 수 없다고 한다), 그래도 내가 생각한 이 로직이 잘못된건 아니라는 생각이 계속 들었고, 계속 생각을 해보다가 더욱 더 어떤식으로 해야 시간초과를 면할 수 있을지 모르겠어서 참고 코드를 확인해보았다. 

그랬더니 나와 결국 로직은 같았고, 차이점이라면 배열을 사용한다는것 정도였다. 그래서 단순하게 배열을 사용한다는것 자체로 그렇게 큰 차이를 만들어낼 정도는 아니라는 생각이 들었고, cache hit rate를 고려하는 참고 코드를 보고나서 든 생각이  거의 모든 관련된 변수들의 타입을 long long으로 선언한 것에서 cache hit rate에 영향을 미칠 수 있지 않을까 싶은 생각에 long long 이지 않아도 되는 것들을 모두 int로 바꾸고 코드를 제출해보았다. 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
int a[4'005];
int b[4'005];
int c[4'005];
int d[4'005];
vector<int> sums;
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sums.push_back(a[i] + b[j]);
		}
	}
	sort(sums.begin(), sums.end());
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			auto ub = upper_bound(sums.begin(), sums.end(), -c[i] - d[j]);
			auto lb = lower_bound(sums.begin(), sums.end(), -c[i] - d[j]);
			int cnt = ub - lb;
			ans += cnt;
		}
	}
	cout << ans;
}

/*
기존에 
ll a[4'005];
ll b[4'005];
ll c[4'005];
ll d[4'005];
vector<ll> sums;
ll ans;
...
ll cnt=ub-lb; 로 작성한 코드를 제출했을때, 시간초과가 발생했다.
캐시 힛 레이트를 높여서 시간을 단축시키는 아이디어에 대해서 듣게되었고
type설정을 크게하면 메모리 페이지를 넘어가는 경우들이 발생하면서
캐시에서 찾지 못하고 메모리에서 다시 찾는 경우들이 발생할 수 있을것 같다는
생각이 들어서 코드를 이렇게 수정하고 시간내로 통과하였다. 
*/

위와같이 type을 바꾸고 나서 제출해보니 통과할 수 있었다. 

그래서 이와 관련된 부분들에 대해서 검색해보게 되었고, 

int 와 long long을 선언하는것이 실제적으로 실행 속도에 영향을 미치는지에 대해서 검색해보았고, 관련된 정보로 읽어볼만한 codeforce 질문내용을 발견하였다. 

 

https://codeforces.com/blog/entry/82238

Does long long int affect time complexity in comparison to the use of int? - Codeforces

 

위 글을 읽어보면 실질적으로 32bit컴퓨터라면 int로 선언할때와 long long으로 선언할때 실행속도에서 차이점이 발생할 수 있다고 하나, 64bit로 넘어오면서 그게 없어졌다고 한다. 

그래서 boj의 채점서버가 32bit인지 64bit인지 궁금해서 그에 대해서 검색해보았고, 실질적으로 최백준님이 6년전에 64bit 로 이전한다고 작성한 글을 발견할 수 있었다. 

https://www.acmicpc.net/board/view/10704

글 읽기 - 채점 서버 64비트로 이사갑니다!

 

그래서 결국 백준 서버는 64bit이므로, int와 long long으로 두는 것 자체에서 발생하는 시간 차이는 아니라는 것이고, 

지금까지의 상황들을 볼때, long long 으로 두는 것이 대략적으로 4000*4000*4000*4000*log(4000*4000) 이라는 많은 케이스들에서 cache hit rate에 영향을 주어서 시간초과를 일으키는 요인으로 작용하는 것이 아닌가 싶다. 

그 외에 혹시 vector가 아니라 array를 사용하는것이 실행속도에 큰 차이를 주는 것인가에 대해서 알아보기 위해서

기존처럼 대부분의 원소들을 long long 으로 선언하고 나서 vector가 아니라 배열을 사용한 풀이로 변경해서 제출해본다면, 

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
ll a[4'005];
ll b[4'005];
ll c[4'005];
ll d[4'005];
ll ab[16'000'005];
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ab[cnt++] = a[i] + b[j];
		}
	}
	sort(ab,ab+n*n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			auto ub = upper_bound(ab,ab+n*n, -c[i] - d[j]);
			auto lb = lower_bound(ab,ab+n*n, -c[i] - d[j]);
			ll cnt = ub - lb;
			ans += cnt;
		}
	}
	cout << ans;
}

마찬가지로 시간 초과가 발생한다. 

그렇다면 여기서 다시 long long을 int로 바꾸어서 배열을 사용한 풀이를 제출해보면, 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
int a[4'005];
int b[4'005];
int c[4'005];
int d[4'005];
int ab[16'000'005];
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ab[cnt++] = a[i] + b[j];
		}
	}
	sort(ab,ab+n*n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			auto ub = upper_bound(ab,ab+n*n, -c[i] - d[j]);
			auto lb = lower_bound(ab,ab+n*n, -c[i] - d[j]);
			int cnt = ub - lb;
			ans += cnt;
		}
	}
	cout << ans;
}

결과로 통과를 얻게된다. 이때에 처음에 vector로 작성한 경우와, 두번째 배열로 작성한 경우의 차이를 보면 메모리 차이가 많이 나고, 시간 차이의 경우는 

144ms의 차이를 얻게된다. 이정도 차이면 결국 vector를 사용해서 시간초과가 발생했다기 보다는 long long 으로 사용한것이 시간초과에 더 큰 영향을 미친것으로 생각하는것이 옳다고 보여진다. 

 

**이때에 메모리 차이에 대해서 알아보기 위해서 c++ vector와 array의 차이에 대해서 검색해보았고, 도움이 될만한 부분이 있는 블로그 글을 찾아서 첨부해본다. 

https://hwan-shell.tistory.com/119

C++ vector사용법 및 설명 (장&단점)

 

**이때 복사생성자에 대해서 검색을 해보자면, 

위의 내용을 참고해서, 내 코드에서는 push_back()을 사용하였는데, 그렇다면 emplace_back()을 사용하여서 코드를 수정하고 제출하면 어떤식으로 변할지에 대해서 궁금해서 동일한 int로 구성된 코드를 emplace_back()으로만 바꿔서 제출해보면, 

 

생각했던 것과는 다르게 push_back()을 쓸때와 emplace_back()을 쓸때 동일한 메모리 사용량을 보인다. 

메모리 사용량을 줄일 수 있는 방법이 emplace_back() 일줄 알았더니 큰 차이가 발생하지 않았다. 

그렇다면 push_back()을 써서 큰 차이가 발생했다기 보다는, 메모리 오버헤드 때문인 것인가. 

이건 아직 완벽하게 파악하지 못했다. 더욱 공부해야겠다. 

 

 

++++++++++++++++++++++++++

추가적으로 cache hit rate를 높이기 위해서, ab뿐만 아니라 cd를 정렬해서 사용하는 형태의 코드를 제출하고 차이가 얼마나 나는지 확인하기 위해서 코드를 작성해보면, 처음 vector를 사용한 형태의 코드에서 c, d의 합을 벡터로 받아서 정렬을 하지 않은 상태로 제출해보면, 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
int a[4'005];
int b[4'005];
int c[4'005];
int d[4'005];
vector<int> sumsAB;
vector<int> sumsCD;
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sumsAB.push_back(a[i] + b[j]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sumsCD.push_back(c[i] + d[j]);
		}
	}

	sort(sumsAB.begin(), sumsAB.end());
	for(int i=0; i<n*n;i++){
			auto ub = upper_bound(sumsAB.begin(), sumsAB.end(), -sumsCD[i]);
			auto lb = lower_bound(sumsAB.begin(), sumsAB.end(), -sumsCD[i]);
			int cnt = ub - lb;
			ans += cnt;
		
	}
	cout << ans;
}

로 작성된 코드에서, 

이런 결과를 얻을 수 있고, 다른 모든 부분은 동일하게 하고 cd를 sort(sumsCD.begin(),sumsCD.end()); 추가해서 제출해보면, 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
int a[4'005];
int b[4'005];
int c[4'005];
int d[4'005];
vector<int> sumsAB;
vector<int> sumsCD;
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sumsAB.push_back(a[i] + b[j]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sumsCD.push_back(c[i] + d[j]);
		}
	}

	sort(sumsAB.begin(), sumsAB.end());
	sort(sumsCD.begin(), sumsCD.end()); // <<=여기만 추가되었다. 
	for(int i=0; i<n*n;i++){
			auto ub = upper_bound(sumsAB.begin(), sumsAB.end(), -sumsCD[i]);
			auto lb = lower_bound(sumsAB.begin(), sumsAB.end(), -sumsCD[i]);
			int cnt = ub - lb;
			ans += cnt;
		
	}
	cout << ans;
}

시간이 매우 많이 줄어든 모습을 볼 수 있다. 

일단 메모리의 경우는 vector 컨테이너가 두배 필요하므로 메모리는 많이 늘었지만 시간은 절반보다 더 적게 줄어든 모습을 볼 수 있다. 

 

이와 관련하여서 참고 코드의 주석 내용을 첨부해보면, 

/*
a[i]+b[j]들을 저장할 ab 배열을 별도로 선언하지 않아도 되지만, 선언해서 정렬한 후 크기 순으로
탐색을 할 경우에는 cache hit이 올라가서 속도가 빨라짐.
코드 : http://boj.kr/8312a3fc055744dab8088197ac57d52a
설명 : https://www.acmicpc.net/board/view/74585
*/

그리고 이와 관련하여서 링크에 제시된 설명 링크를 첨부해보자면

https://www.acmicpc.net/board/view/74585

글 읽기 - upper_bound 사용시에 AB vector의 정렬에 따른 시간차이

 

이를 통해서 cache hit rate를 고려하면서 코드를 작성하는것이 수행 속도에서 아주 큰 차이를 만들어낼 수 있다는걸 알 수 있었다. 인간이 보기에는 불필요해 보이는 코드로 보이는데 컴퓨터의 계층구조를 잘 이해하면 이렇듯 연산속도를 훨씬 줄일 수 있는 프로그램을 작성할 수 있다. 매우 신기하고 재미난 사실이라고 생각된다. 이 케이스에 대해서는 이번 글을 작성할때 뿐만 아니라 지속적으로 공부해보면서 이해하고 cache hit rate를 높일 수 있는 코드를 작성하는것을 중요시 하는것이 좋을것 같다. 

 

+++++++++

추가적으로 시간이 많이 줄어들었으니, 이 두개의 정렬을 통해서 cache hit rate를 높여서 실행시간을 단축시킨 이 코드에 

type의 선언을 다시 다 long long으로 바꾸어서 실행 시간이 얼마나 늘어나는지 비교해보자면, 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
ll a[4'005]; //long long 
ll b[4'005];
ll c[4'005];
ll d[4'005];
vector<ll> sumsAB;
vector<ll> sumsCD;
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sumsAB.push_back(a[i] + b[j]);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sumsCD.push_back(c[i] + d[j]);
		}
	}

	sort(sumsAB.begin(), sumsAB.end());
	sort(sumsCD.begin(), sumsCD.end());
	for(int i=0; i<n*n;i++){
			auto ub = upper_bound(sumsAB.begin(), sumsAB.end(), -sumsCD[i]);
			auto lb = lower_bound(sumsAB.begin(), sumsAB.end(), -sumsCD[i]);
			ll cnt = ub - lb;
			ans += cnt;
		
	}
	cout << ans;
}

시간을 비교해보면 실질적으로 시간이 증가하긴 했는데, 그렇게 큰 차이가 발생하는건 아니라는 생각이 드는 정도의 상승이다

70ms의 차이인데, 이때에 정확하게 채점 했을때에 '메모리', '시간'이 나타내는 수의 의미가 무엇인지 알고 가는것이 좋을것 같아서 백준help에서 제시해주는 정보를 첨부해보자면, 

https://help.acmicpc.net/judge/time-and-memory

시간과 메모리

수행 시간을 의미하는것이라는 생각이 들고, 이때에 

"수행 시간은 각 데이터를 입력했을 때, 프로그램이 실행된 시간의 최대값이며, ms(1/1000초)를 사용합니다.

예를 들어, 어떤 제출이 각각의 데이터에서 32 ms, 28 ms, 44 ms, 16 ms가 걸렸다면, 이 제출의 수행 시간은 44 ms 입니다"

라는걸 통해서, 

내가 받은 결과에서 4100 ms의 의미는, 테스트 케이스에서 가장 오랜 시간이 걸린 경우가 4100ms가 걸렸다는 의미로 보여진다. 

그렇다면 제일 오래 걸린게 4100ms인데, 이걸 long long 으로 바꿨을때 시간 초과가 발생하는건 너무 큰 차이가 발생하는 것이 아닌가 싶은 생각이 든다. 물론 cache hit rate를 고려해서 작성한 것이 영향을 미쳐서 70ms가 늘어났다고 생각할 수 있을것 같은데, 기존에 long long 으로 작성하는것이 왜 9000 ms 대의 제출에서는 영향을 미친 것일까. 

 

이 문제에 대해서는 오늘은(23.6.13) 이정도만 작성하고 다음에 이어서 작성해야겠다. 일단은 cache hit rate를 고려한 풀이의 중요성, 그리고 불필요한 값들까지 모두 long long 으로 작성했을때의 cache hit rate에 미치는 영향, 그리고 시간 초과 발생 가능성에 대해서 생각해볼 수 있는 좋은 경험이었다. 다음에 이어서 공부를 이어가보도록 하자. 

 

+++++++++++++++++++++++++++++++++++++

(23.6.13 - 글을 작성하고 난뒤 추가하는 상황)

 

시간 제한이 12초 인데, int로 변환해서 제출한 코드들이 시간이 9초 중~후반대가 나오고, 그렇다면 12초까지 여유는 대략 2초, 근데 여기서 만약 이걸 cache hit rate를 고려해서 두가지 배열(혹은 vector)를 정렬해서 제출하면 

거의 절반으로 줄어드는데, 그때에 long long 으로 바꾼 코드를 재출했을때의 시간 소요 차이를 생각해보면 대략적으로 70ms의 차이를 보이는데, 만약 이게 곱연산의 영향으로 9초대에서 70ms정도 차이가 나던 연산의 과정이 훨씬 많아지면

12초를 넘는 케이스가 발생하면서 시간 초과가 발생하는 것인가?

그렇다면 혹시 동일한 것들을 계속 제출하다가 시간초과가 발생하지 않는 상태도 나올 수 있는 것인가? 

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
ll a[4'005];
ll b[4'005];
ll c[4'005];
ll d[4'005];
vector<ll> sums;
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sums.push_back(a[i] + b[j]);
		}
	}
	sort(sums.begin(), sums.end());
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			auto ub = upper_bound(sums.begin(), sums.end(), -c[i] - d[j]);
			auto lb = lower_bound(sums.begin(), sums.end(), -c[i] - d[j]);
			ll cnt = ub - lb;
			ans += cnt;
		}
	}
	cout << ans;
}

//시간 초과 재 확인용 제출 코드. 가장 처음 제출한 코드와 동일하다. 
// 이 코드를 조금씩 변경해 보면서 시간 초과가 어디서 얼마나 발생하는지 알아보자.

처음 제출한 코드와 동일한 코드를 다시 제출해보았는데 이번에는 통과를 했다. 

 

 

굉장히 아슬아슬하게 통과했다. 같은 코드여도 시간이 조금씩 달라질때가 있던데, 만약에 조금 달라지면 제한인 12초를 넘어서 통과하지 못할 수준으로 시간이 11.884초가 걸렸다. 

 

혹시 몰라서 처음 제출했을때처럼 주석을 많이 달아서 돌렸는데, 그래도 결국 통과를 했고, 오히려 시간도 많이 줄었다. 

그것도 차이가 많이 난다. 1초 차이가 난다. 동일한 코드인데도. 

 

++처음과 완전 동일한 코드를 제출해보았다. 

/*
A( -45 , -41, -36, -36, 26, -32)
B(22 -27, 53, 30, -38, -54)
C(42,56 , -37, -75, -10, -6)
D(-16, 30 , 77, -46, 62, 45)
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
ll a[4'005];
ll b[4'005];
ll c[4'005];
ll d[4'005];
vector<ll> sums;
ll ans;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			sums.push_back(a[i] + b[j]);
		}
	}
	sort(sums.begin(), sums.end());
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			auto ub = upper_bound(sums.begin(), sums.end(), -c[i] - d[j]);
			auto lb = lower_bound(sums.begin(), sums.end(), -c[i] - d[j]);
			ll cnt = ub - lb;
			ans += cnt;
		}
	}
	cout << ans;
}

/*
a+b=-d-c;
a+b는 2중 for문으로 계산해서 vector에 넣고, 백터의 원소들 중에서 -d-c
와 같은 것을 찾자. 
*/
//가장 첫번째 제출한 코드와 동일하다.

이 코드의 경우 처음 시간초과를 한 코드에 맨 마지막에 //가장 첫번째 제출한 코드와 동일하다. 라는 내용의 주석만 첨부한 코드이다. 

 

이것도 이번에는 통과하게 되었다. 

++++++++++

(23.6.13 ) 

처음 제출했을때 시간초과가 났던 long long 으로 작성한 코드를 지속적으로 제출해보면서 시간초과가 다시 나기를 바라면서 하고 있는데, 계속 통과하는 중이다. 그런데 계속 시간이 차이가 많이 나면서 왔다갔다 거리는 중이다. 

시간초과가 다시 발생한다면 실험이 종료할 수 있는데 아쉽게도 계속 통과중이다. 

 

 

++++++++++++++++

(23.6.13)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int n;
ll a[4'005];
ll b[4'005];
ll c[4'005];
ll d[4'005];
ll ab[16'000'005];
ll ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ab[cnt++] = a[i] + b[j];
		}
	}
	sort(ab,ab+n*n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			auto ub = upper_bound(ab,ab+n*n, -c[i] - d[j]);
			auto lb = lower_bound(ab,ab+n*n, -c[i] - d[j]);
			ll cnt = ub - lb;
			ans += cnt;
		}
	}
	cout << ans;
}

이 코드도 처음 제출할때 시간 초과가 떴었는데, 위의 vector를 이용한 풀이는 계속 통과가 되어서 이걸 제출해보았다. 

이 코드는 두번 시간초과가 뜨고나서, 세번째에 통과해서 맞았습니다를 받게 되었다. 

이로써 동일한 코드도 비효율적인 코드의 경우 어떨때는 통과할 수 있고, 어떨때는 시간초과를 받을 수 있다는걸 알게되었다. 코드를 작성하고, 시간 복잡도를 고려하고, cache hit rate를 잘 고려해서 효율성을 올리고 소요 시간을 줄이는 노력을 해보도록 하자. 

이 얘기를 잘 생각해보면서 코드를 작성하도록 하자. cache hit rate를 높일 수 있는 요소들끼리의 합성이 얼마나 큰 영향을 미칠 수 있는지 배우는 경험이었다.