C++ for vs for_each 반복문 속도 비교

알고리즘 공부를 하면서,

보통 시간제한 1초 이하로 주어진 문제들은 반복문을 1억번 이하로 순회할 수 있다.

 

순서대로 순회하는 일이 필요할 때 보통 배열을 사용하게 되고, 배열을 순회할 때 C++11 이상부터는 다양한 방법을 제공한다.

 

그 중에는 내가 좋아하는 for_each 메쏘드도 있고, 간편한 문법을 제공하는 range-based for 문도 있다.

시간 복잡도는 코더의 역량으로 최대한 최적화 하면 되는 문제인데,

어떤 방법을 사용하여 배열을 순회할 때 최대한 시간적 이득을 볼 수 있을까?

 

---

3가지 배열 순회 방법의 속도 비교

 

이제부터 비교해보겠다.

 

1. 전통적인 for 문 (for int i = 0; i < n; ++i) {}
2. for_each 문 (arr.begin(), arr.end(), [](element &e) {});
3. 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) 를 쓰자..