반복문
반복문이란 프로그램 내에서 똑같은 명령을 일정 횟수만큼 반복하여 수행하도록 제어하는 명령문입니다.
프로그램이 처리하는 대부분의 코드는 반복적인 형태가 많으므로, 가장 많이 사용되는 제어문 중 하나입니다.
우리는 반복문을 통해서 여러 번 수행해야 하는 작업을 같은 코드를 여러 번 적지 않고 단순히 한 번만 적어서 처리할 수 있습니다.
대표적으로는 for문과 while 문이 존재하죠
For Loop
for문은 그 중에서도 가장 많이 쓰이는 반복문입니다!! (제 기준에서는...ㅎ)
대표적인 for 문은 다음과 같이 생겼죠
for(int i = 0; i < 10; i ++){
...
}그런데 우리는 for 문을 저렇게만 사용하지 않죠
바로 enhanced-for 를 사용할 때도 있습니다.
for(int a: arr){
...
}Range-based For & Enhanced-For
그런데 자료를 찾던 와중 제 기억 심연 속에 잠들어있던 range-based-for문 이라는 것도 생각이 났습니다...!!1
그리고 그 이아의 생김새도 enhanced-for 문과 비슷했죠!
그런데 둘은 다른데 같은 녀석들 이었습니다...!!
???
Range-base for문은 C++ 에서 부르는 이름이고, Enhanced-For 문은 Java 에서 부르는 이름입니다..
Range based For loop
for (auto& x: arr){ ... }
둘의 성능 차이
각설하고 다시 돌아와서 자바에서 그냥 기본적으로 사용하는 for loop와 enhanced for loop 의 성능 차이가 나는지 궁금해 졌습니다.
그래서 간단한 테스트를 통해 비교를 진행해보려고 합니다.
위와 같은 테스트 코드를 바탕으로 테스트를 진행해 보겠습니다.
사실 이왕 하는 김에 for-each문도 같이 성능을 비교해 보고 싶었으나...
람다식 안에는 final 로 선언된 변수만 넣거나, atomic 한 변수를 넣어 줘야 해서 시간이 비교적 오래 걸렸습니다.
따라서 정확한 비교라고 하기에는 조금 어려울 것 같네요..
둘을 비교해 보면 Enhanced for 문이 크게 앞서는 모습을 볼 수 있습니다!!
그렇다면 반복문을 여러 번 반복해서 시간을 비교해보면 어떨까요??
각각 테스트 코드와 결과를 한 번 보도록 하겠습니다!
BeforeEach 및 메소드 바깥 영역
final static int size = 1000 * 1000 * 100;
List<Integer> arr;
@BeforeEach
void beforeEach() {
arr = new ArrayList<>();
for (int i = 0; i < size; i++) {
arr.add(i);
}
System.out.println("arr size : " + arr.size());
}
basic for result
arr size : 100000000
# 1 time : 152ms
# 2 time : 151ms
# 3 time : 145ms
# 4 time : 145ms
# 5 time : 145ms
# 6 time : 145ms
# 7 time : 145ms
# 8 time : 145ms
# 9 time : 145ms
# 10 time : 145ms
Basic For Loop Average Time : 146ms
------------------------------------------------------------
enhanced for result
arr size : 100000000
# 1 time : 168ms
# 2 time : 301ms
# 3 time : 303ms
# 4 time : 296ms
# 5 time : 300ms
# 6 time : 295ms
# 7 time : 297ms
# 8 time : 295ms
# 9 time : 299ms
# 10 time : 299ms
Enhanced For Loop Average Time : 285ms
------------------------------------------------------------
for each result
arr size : 100000000
# 1 time : 827ms
# 2 time : 799ms
# 3 time : 804ms
# 4 time : 802ms
# 5 time : 808ms
# 6 time : 812ms
# 7 time : 806ms
# 8 time : 796ms
# 9 time : 805ms
# 10 time : 797ms
For Each Loop Average Time : 805ms
------------------------------------------------------------
while with index reuslt
arr size : 100000000
# 1 time : 291ms
# 2 time : 75ms
# 3 time : 65ms
# 4 time : 69ms
# 5 time : 66ms
# 6 time : 66ms
# 7 time : 66ms
# 8 time : 66ms
# 9 time : 66ms
# 10 time : 66ms
While Loop Average Time : 89ms
------------------------------------------------------------
while with iterator result
arr size : 100000000
# 1 time : 126ms
# 2 time : 304ms
# 3 time : 298ms
# 4 time : 297ms
# 5 time : 297ms
# 6 time : 296ms
# 7 time : 296ms
# 8 time : 296ms
# 9 time : 296ms
# 10 time : 295ms
While Loop Average Time : 280ms
------------------------------------------------------------그렇다면 arr이 LinkedList일 경우에는 어떨 까요???
실질적인 테스트 코드는 동일하고 변경된 부분과 결과만 보여드리도록 하겠습니다!!
변경된 부분
final static int size = 1000 * 100; // 사이즈 조절
List<Integer> arr;
@BeforeEach
void beforeEach() {
arr = new LinkedList<>(); // 구현체 변경
for (int i = 0; i < size; i++) {
arr.add(i);
}
System.out.println("arr size : " + arr.size());
}arr size : 100000
# 1 time : 5209ms
# 2 time : 5178ms
# 3 time : 5182ms
# 4 time : 5176ms
# 5 time : 5187ms
# 6 time : 5176ms
# 7 time : 5178ms
# 8 time : 5176ms
# 9 time : 5178ms
# 10 time : 5177ms
While Loop With Index Average Time : 5181ms
------------------------------------------------------------
arr size : 100000
# 1 time : 7ms
# 2 time : 1ms
# 3 time : 2ms
# 4 time : 1ms
# 5 time : 1ms
# 6 time : 1ms
# 7 time : 1ms
# 8 time : 0ms
# 9 time : 1ms
# 10 time : 1ms
For Each Loop Average Time : 1ms
------------------------------------------------------------
arr size : 100000
# 1 time : 4ms
# 2 time : 3ms
# 3 time : 1ms
# 4 time : 1ms
# 5 time : 1ms
# 6 time : 1ms
# 7 time : 1ms
# 8 time : 1ms
# 9 time : 1ms
# 10 time : 0ms
While Loop With Iterator Average Time : 1ms
------------------------------------------------------------
arr size : 100000
# 1 time : 4ms
# 2 time : 3ms
# 3 time : 1ms
# 4 time : 1ms
# 5 time : 1ms
# 6 time : 1ms
# 7 time : 1ms
# 8 time : 1ms
# 9 time : 1ms
# 10 time : 0ms
Enhanced For Loop Average Time : 1ms
------------------------------------------------------------
arr size : 100000
# 1 time : 5212ms
# 2 time : 5187ms
# 3 time : 5188ms
# 4 time : 5184ms
# 5 time : 5187ms
# 6 time : 5186ms
# 7 time : 5187ms
# 8 time : 5187ms
# 9 time : 5194ms
# 10 time : 5190ms
Basic For Loop Average Time : 5190ms
------------------------------------------------------------전체 결과
Size 100,000,000 ArrayList
Size 100,000 LinkedList
이렇게 놓고 보니 둘의 차이점이 확연하게 보이는군요!!
둘의 결과를 비교해보면 다음과 같은 특징이 나타납니다
1. ArrayList의 경우 index를 통해 요소에 접근하는게 더 빠르다
2. LinkedList의 경우에는 반대로 index를 통해 접근한는게 매우 느리다.
3. 테스트 특성상 2배의 일을 하는 것을 감안하면 range-based-for loop와 for-each 문의 작업 수행 시간은 거의 동일하다.
그렇다면 이런 현상은 왜 이렇게 일어난 걸까요??
Array vs LinkedList
단골 기술면접 질문입니다.
둘을 비교하면 다음과 같습니다.
Array
- 컴파일시 배열의 길이가 정해짐 -> 동적으로 수정할 수 없음, 배열의 길이보다 큰 데이터를 넣으려고 시도하거나 올바르지 않은 인덱스로 접근을 시도하면 에러가 발생함
- 논리적인 데이터의 위치와 물리적인 데이터 저장 위치가 동일함.
- 인덱스로 접근할 경우 O(1)의 시간 복잡도로 바로 접근이 가능함(매우 빠름), 인덱스를 모를 경우에는 반복문을 통해서 배열을 순회하면서 찾고자 하는 데이터와 일치하는 데이터를 찾아야 함
- 데이터를 추가하거나 삭제할 경우에는 시간이 다소 걸림. 중간에 있는 데이터를 삭제하거나 중간에 데이터를 추가할 경우, 해당 데이터보다 뒤에 있는 데이터를 전부 뒤로 밀거나(추가했을 경우), 앞으로 당겨야 하기 때문에(삭제의 경우) 최대 O(n)의 시간복잡도가 걸림
LinkedList
- 총 길이는 동적으로 늘어나거나 줄어들 수 있음. Heap 영역에서 관리되기 때문에 동적으로 길이 조정이 가능함
- 논리적인 데이터의 위치와 물리적인 데이터의 위치가 상관이 없음.
- 특정 인덱스로 접근할경우 -> linkedlist의 데이터를 각각 노드라고 불리는데, 각 노드는 자신의 다음 데이터만 알고 있거나(Singly linkedlist), 자신의 앞 뒤 데이터만 알고 있음(doubly linkedlist) 그렇기 때문에 사용자가 찾고자 하는 노드가 나올 때 까지 head(또는 tail)에서 하나 하나 노드들을 거치면서 찾는 방법밖에 없음. 최대 O(n)의 시간 복잡도가 걸림
- 특정 위치에 데이터를 삽입하거나 삭제를 할 경우에는 배열보다는 유리함. 데이터들의 물리적인 위치와 논리적인 위치는 상관이 없기 때문에 특정 위치에 데이터를 삽입할 경우에는 그냥 그 그전에 존재하던 데이터 간의 링크를 끊은 다음 데이터를 넣고 다시 적절하게 연결시켜 주면 되고, 삭제할 경우에도 삭제하고자 하는 데이터를 삭제한 다음, 링크를 끊기만 하면 되기 때문에 속도가 비교적 빠름
우리가 위에서 사용한 자료구조는 각각 ArrayList와 LinkedList이죠.
ArrayList는 동적으로 길이 조절이 가능한 Array입니다.
그리고 내부적으로는 Array를 들고 있죠.
그렇기 때문에 조회에 맞춰진 테스트 특성 덕분에 위 테스트에서는 index를 기반으로 반복문을 순회할 경우가 속도가 매우 빨랐던 겁니다.
물론 enhanced for loop도 충분히 빠르지만,
그에 반해 LinkedList의 경우 인덱스를 통해 접근할 경우 노드를 타고 타고 가서 원하는 노드까지 가야하므로 시간이 매우 오래 걸렸던 것이죠
1 ~ 100,000 까지의 모든 수의 합이 5,000,050,000(약 50억) 인 것을 보면 O(n)의 시간 복잡도가 맞는 것을 확인할 수 있습니다
테스트에서 나타는 1, 2 특성의 이유는 자료 구조의 구조적 차이점에서 찾을 수 있었습니다.
그럼 3번의 특성은 어디서 나타나는 것일까요??
Iterable
자바에서는 Collection Framwork를 통해서 개발자가 여러 자료구조를 다룰 수 있도록 도와줍니다.
iterator를 사용할 수 있는 자료구조의 맨 위로 가다 보면 Iterable이라는 녀석이 등장합니다.
3번의 특성은 바로 여기서 나타나죠!!
...그게 무슨 소리죠??
바로 ArrayList, LinkedList 의 forEach는 둘 다 별도로 오버라이딩 하지 않고, Iterable 인터페이스 내부에서 정의된 형태 그대로를 가지고 오기 때문입니다.
그럼 어떤 식으로 정의되어 있는지 확인해 볼까요?
Iterable void forEach()
![[iterable-foreach.png]]
아하!!
forEach 문은 내부적으로 enhanced-for 문으로 구현되어 있었군요!!
그래서 enhanced-for 문과 실행시간이 거의 동일했던 거였습니다!!
그러면 Iterable 의 자식 클래스들은 모두 위의 forEach문을 사용할까요??
그렇지 않습니다!!
바로 Stack 클래스는 Vector 내부에서 재정의된 forEach문을 사용하고,
해당 forEach문 내부에서는 index 기반의 기본 for 문을 사용하고 있습니다.
하지만 Stack 클래스의 경우 현재는 사용을 지양하는 추세이며 대신 Deque를 사용하는 방식이 권장되고 있습니다.
ArrayList win ?
그럼 처리 속도도 훨씬 빠르고, random access 속도도 훨씬 빠른 ArrayList가 LinkedList 상위 호환일까요??
그냥 List 를 사용하고자 하는 경우에는 ArrayList 사용이 권장됩니다.
하지만 다른 경우에는 그렇지 않죠
바로 Deque, Queue 등을 사용하고자 하는 것과 같이 입출력이 잦은 경우에는 LinkedList가 우월하죠!!
저의 테스트 경우에는 삽입, 삭제가 없고 단순 조회만 있어서 위와 같은 오해를 살 수 있겠지만 우리의 인텔리제이가 추천해 주듯
이럴 경우에는 LinkedList를 구현체로 해야하죠
오늘의 결론
상황에 맞는 자료구조와 알고리즘을 사용해서 최적화를 하자!
