반복문 어떻게해야 빠른가?
반복문은 빠지지 않고 많이 사용된다.
배열이나 벡터를 전부 다 탐색하는 경우에
어떻게하면 더 빠르게 반복문을 사용할 수 있을까
예제를 보며 바로 답을 찾아보자
모든 경우는 임의의 벡터를 만들어 크기를 10000000로 설정했다.
첫번째 방법
첫번째 방법은 처음부터 벡터의 사이즈만큼 도는 것이다.
1
2
3
4
5
6
7
//첫번째 경우
st = clock();
for (int i = 0; i < arr.size(); i++) {
}
end = clock();
cout << end - st << "\n";
//결과: 262ms
실행할 때마다 변화가 있긴하지만 262ms가 나왔다.
알고리즘 문제를 좀 풀어본 사람들이라면
첫번째 방법을 피해야 한다는 것을 알고있을것이다.
왜냐하면 저런식의 방법은 반복문을 한번 돌 때마다
계속해서 벡터의 크기를 계산해주기 때문에 느릴 수 밖에 없다.
두번째 방법
1
2
3
4
5
6
7
8
//두번째 경우
st = clock();
int len = arr.size();
for (int i = 0; i < len; i++) {
}
end = clock();
cout << end - st << "\n";
//결과: 28ms
이번에는 28ms가 걸렸다.
첫번째 방법과 거의 10배 가까이 차이가 나는데
이 정도면 반복문 때문에 시간초과로 문제를 틀릴 수 있을 정도이다.
세번째 방법
그럼 이 방법보다 시간을 더 줄일 수 있는 마지막 방법을 보자.
1
2
3
4
5
6
7
//세번째 경우
st = clock();
for (int i = arr.size(); i >= 0; i--) {
}
end = clock();
cout << end - st << "\n";
//결과: 20ms
이 방법은 배열을 거꾸로 탐색하는 것이다.
8ms가 줄어서 큰 차이는 없지만 꽤나 신기했다.
배열의 크기를 처음에 한번만 계산해서
처음 방법보다는 빠른걸 알겠는데
왜 반대로 탐색하는게 더 빠른지는 사실 잘 모르겠다.
결국 이 답을 스택오버플로우에서 찾을 수 있었다.
stackoverflow
두번째 경우는 len이라는 변수와 비교를 해야하고
마지막 방법은 상수 0과 비교를 한다.
변수에 접근하는 것 보다 상수에 접근하는 것이 시간적으로 더 빠르다고 한다.
그 차이가 크지는 않지만 그 이유 때문에 시간차이가 발생한 것이다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<time.h>
#include<vector>
using namespace std;
int main() {
vector<int>arr(10000000);
clock_t st, end;
double res1, res2;
//첫번째 경우
st = clock();
for (int i = 0; i < arr.size(); i++) {
}
end = clock();
cout << end - st << "\n";
//결과: 262ms
//두번째 경우
st = clock();
int len = arr.size();
for (int i = 0; i < len; i++) {
}
end = clock();
cout << end - st << "\n";
//결과: 28ms
//세번째 경우
st = clock();
for (int i = arr.size(); i >= 0; i--) {
}
end = clock();
cout << end - st << "\n";
//결과: 20ms
return 0;
}