-
C++ for vs for_each 반복문 속도 비교알고리즘 2023. 7. 25. 21:49
알고리즘 공부를 하면서,
보통 시간제한 1초 이하로 주어진 문제들은 반복문을 1억번 이하로 순회할 수 있다.
순서대로 순회하는 일이 필요할 때 보통 배열을 사용하게 되고, 배열을 순회할 때 C++11 이상부터는 다양한 방법을 제공한다.
그 중에는 내가 좋아하는 for_each 메쏘드도 있고, 간편한 문법을 제공하는 range-based for 문도 있다.
시간 복잡도는 코더의 역량으로 최대한 최적화 하면 되는 문제인데,
어떤 방법을 사용하여 배열을 순회할 때 최대한 시간적 이득을 볼 수 있을까?
3가지 배열 순회 방법의 속도 비교
이제부터 비교해보겠다.
- 전통적인 for 문 (for int i = 0; i < n; ++i) {}
- for_each 문 (arr.begin(), arr.end(), [](element &e) {});
- range-based for 문 (for auto &o : arr) {}
void test1() { vector<vector<int>> arr(SIZE, vector<int>(SIZE, 0)); for (int i = 0; i < SIZE; ++i) for (int j = 0; j < SIZE; ++j) arr[i][j] = 42; } void test2() { vector<vector<int>> arr(SIZE, vector<int>(SIZE, 0)); for_each(arr.begin(), arr.end(), [](vector<int> &row) { for_each(row.begin(), row.end(), [](int &n) {n = 42;}); }); } void test3() { vector<vector<int>> arr(SIZE, vector<int>(SIZE, 0)); for (auto &o : arr) for (auto &e : o) e = 42; }
SIZE = 1만 으로 설정했고, 2차원 배열을 순회하며 각 원소에 값을 할당해보았다.
(참고로 SIZE = 100만에서 1차원 배열을 순회할 땐, 세 테스트 모두 1ms 미만의 차이를 보여서 알고리즘 문제를 풀 때 속도차이의 의미가 없었다.)
TEST 1 : 0.502745 TEST 2 : 1.00003 TEST 3 : 0.836647 (단위 : ms)
for_each 메쏘드는 함수의 내부에서 배열을 관리해서 여러모로 안전하고, 코드의 가독성도 뛰어나서 매우 좋아한다.
하지만 알고리즘 문제를 풀 때는, 시간상의 손해를 볼 수 있다.
참고로 for_each 문을 배열의 원소 값을 할당할 때 쓰는 것 자체가 좋은 문법은 아니다.
위의 상황에서는 transform 을 사용하는 것이 바람직하다.
하지만 배열의 중첩이 커질 수록 문법은 더 복잡해지고, 시간적 이득을 많이 볼게 아니라면 그냥 for 문을 쓰는게 낫다.
결론
1차원 배열을 순회할 때 : 아무거나 써도 속도차이가 거의 없음 (1ms 미만)
2차원 이상 배열을 순회할 때 : 전통적인 for 문 사용
알고리즘 문제 풀 때 만큼은 (for int i = 0; i < n; ++i) 를 쓰자..
'알고리즘' 카테고리의 다른 글
다익스트라 알고리즘은 이렇게 쓰는 게 맞다! (0) 2023.08.18