for vs iterator

원인 문제

문제의 문제
이 문제를 풀다가 팀원분과 각자의 코드를 리뷰하는 시간을 가졌다. 결과 코드는 나와 비슷해서 성능도 그럴줄 알았는데 속도면에서 꽤 차이가 났다. 그래서 원인을 분석해봤는데 나는 일반 for loop를 사용하고 팀원분은 향상된 for loop를 사용한게 차이였다. 그 반복문을 변경하니까 속도가 바뀌었다. 그래서 뭐가 다른지 한 번 검색해봤다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean isPrime = true;
		// 소수의 배열을 만든다.
        ArrayList<Integer> list = new ArrayList<>();
        list.add(2);
	    // 수를 처음부터 n까지 소수의 배열을 하나씩 꺼내서 나눈다.
        // 나눠진다면 소수가 아니므로 continue 실행
	    // 다 통과한다면 그 수는 소수이므로 소수의 배열에 추가
        for (int i = 2; i < n+1; i++) {
            double root = Math.sqrt(i);
//            for (Integer integer : list) {
//                if(i % integer == 0){
//                    isPrime = false;
//                    break;
//                }
//                if(integer > root)
//                    break;
//            }
            for (int j = 0; j < list.size() ; j++) {
                if(i % list.get(j) == 0 ){
                    isPrime = false;
                    break;
                }
                if(list.get(j) > root)
                    break;
            }
            if(isPrime)
                list.add(i);
            isPrime = true;
        }
        return list.size();
    }
}

---

foreach

향상된 for문이라고도 불리는 이 친구는 근본적으로 iterator를 사용하는 메서드다.

foreach 구문은 컴파일한 바이트 코드를 확인해보면 iterator를 사용하새 로직을 실행한다.

결국은 근본적으로 iterator를 사용한다는 점에서는 for과 iterator만 비교하려고 한다.

우선 둘을 검색해보면 ArrayList와 LinkedList에 대한 결과를 많이 찾아 볼 수 있다.

결론적으로는 ArrayList에서는 for문이 빠르고 LinkedList에서는 iterator가 빠르다.

그 이유를 살펴보자.

LinkedList

LinkedList는 특정 값을 찾을 때 헤더에서 시작해서 차례대로 값을 찾아 떠난다.

문제는 for문을 사용하여 get을 하면 값을 불러올 때 마다 헤더에서 출발해 값을 찾으로 가는 것이다.

이와 달리 iterator는 이전 값을 저장해서 다시 헤더부터 값을 탐색하는 일이 없다.

그래서 LinkedList는 for문보다 iterator가 더 빠르다.

ArrayList

ArrayList에서 iterator보다 for문이 빠른 이유는 정확히 모르겠다. 검색을 해봐도 명확한 이유를 찾아내지 못했다.

iterator는 concurrent modification verification를 구현해야하기 때문에 느리다 라고는 하는데 저 말의 뜻을 아직 이해하지 못했다.

그래서 추측해보자면 ArrayList는 인덱스가 주어지면 시간복잡도가 O(1)이다.

for문을 사용하면 항상 인덱스값이 주어지므로 반복마다 시간복잡도가 O(1)을 유지할 것이다.

하지만 iterator는 과정이 추가된다.

다음 자리에 값이 있는지 확인하고 있으면 값을 출력하고 이전 값을 저장하는 사이클이 한 과정이다.

과정만 보더라도 인덱스 입력해서 값을 가져오는 방법보다 시간이 더 걸릴 것을 예상할 수 있다.

그래서 그렇지 않을까. 어디까지나 나의 추측이다.

---

참고

https://medium.com/javarevisited/which-is-faster-for-loop-or-foreach-in-java-aaf1d65154e1