Array vs Linked list를 비교
Array와 Linked List의 주된 차이점들은 메모리 구조에 있다. Array는 메모리상에서 연속적으로 데이터를 저장하고, Linked List는 불연속적으로 저장한다. 메모리 구조의 차이로 인해 operation구현 방법이 다르고 시간복잡도도 다르다. 또한 메모리 활용도에서도 차이가 있다. 상황에 따라 메모리를 효율적으로 사용할 수 있는 자료구조가 달라진다는 것이다
Array는 메모리 상에서 연속적으로 데이터를 저장하는 자료구조 다. Linked List는 메모리상에서는 연속적이지 않지만, 각각의 원소가 다음 원소의 메모리 주소값을 저장해 놓음으로써 논리적 연속성을 유지한다.
그래서 각 operation의 시간복잡도가 다르다. 데이터 조회는 Array의 경우 O(1), Linked List는 O(n)의 시간복잡도를 갖는다. 삽입/삭제는 Array O(n), Linked List O(1)의 시간복잡도를 갖는다.
따라서 얼마만큼의 데이터를 저장할지 미리 알고있고, 조회를 많이 한다면 Array를 사용하는 것이 좋다.
반면에 몇개의 데이터를 저장할 지 불확실하고 삽입 삭제가 잦다면 Linked list를 사용하는 것이 유리하다.
조회 (lookup)
- Array는 메모리상에서 연속적으로 데이터를 저장하였기 때문에 저장된 데이터에 즉시 접근(random access O(1))할 수 있다.
- Linked List는 메모리 상에서 불연속적으로 데이터를 저장하기 때문에 순차 접근(Sequential Access)만 가능하다. 즉, 특정 index의 데이터를 조회하기 위해 O(n)의 시간이 걸리게 된다.
삽입/삭제 (insert/delete)
Array의 경우 맨 마지막 원소를 추가/삭제하면 시간복잡도가 O(1)이다. 하지만 맨 마지막 원소가 아닌 중간에 있는 원소를 삽입/삭제하면 해당 원소보다 큰 인덱스의 원소들을 한 칸씩 shift 해줘야 하는 비용(cost)이 발생한다. 따라서 이 경우에는 시간복잡도가 O(n)이 된다.
Linked List는 어느 원소를 추가/삭제 하더라도 node에서 다음주소를 가르키는 부분만 다른 주소 값으로 변경하면 되기 때문에 shift할 필요 없어 시간복잡도가 O(1)이다.
하지만 Linked list의 경우 추가/삭제를 하려는 index까지 도달하는데 O(n)의 시간이 걸리기 때문에, 실질적으로 Linked List도 추가/삭제 시에 O(n)의 시간이 걸린다고 볼 수 있다.
memory
Array의 주된 장점은 데이터 접근과 append가 빠르다는 것이다. 하지만 메모리 낭비라는 단점이 있다. 배열은 선언시에 fixed size를 설정하여 메모리 할당한다. 즉, 데이터가 저장되어 있지 않더라도 메모리를 차지하고 있기 때문에 메모리 낭비가 발생한다.
이와 반면 Linked List는 runtime중에서도 size를 늘리고 줄일 수 있다. 그래서 initial size를 고민할 필요 없고, 필요한 만큼 memorry allocation을 하여 메모리 낭비가 없다.
정리
Q. 어느 상황에 Linked list를 쓰는게 Array보다 더 나을까?
- O(1)으로 삽입/삭제를 자주 해야 될 때
- LinkedList 의 삽입 삭제가 O(1)이지만 실질적으로는 O(n)의 시간복잡도를 가지는데, 삽입 삭제를 자주해야할 때 LinkedList와 Array는 같은 것이 아닐까?
- linked list는 상황에 따라서, 구현방법에 따라서 실질적으로 O(1)가 되는 경우도 종종 있다.
예를 들면 current_node를 하나 설정해서, 계속 한 자리에서 삽입삭제만 진행하는 상황에서 그런식으로 코드를 구현한다면 실질적으로 O(1)가 되기도 한다.
삽입/삭제를 자주 해야 한다면 보통 동일한 위치에서 삽입/삭제가 일어나는 경우들이 있다. 그런경우 linked list를 사용하면 된다.
- 얼마만큼의 데이터가 들어올지 예측을 할 수 없을 때
- 조회 작업을 별로 하지 않을 때
Q. 어느 상황에 Array를 쓰는게 Linked list보다 더 나을까?
- 조회 작업을 자주 해야될 때
- Array를 선언할 당시에 데이터의 갯수를 미리 알고 있을때
- 데이터를 반복문을 통해서 빠르게 순회할 때
- Random Access로 인해 조회 시간 복잡도가 O(1) 이므로
- 메모리를 적게 쓰는게 중요한 상황일 때. Linked list보단 Array가 메모리를 적게 차지 하기 때문에 미리 들어올 데이터의 양을 알고만 있다면 Array가 메모리를 더 효율적으로 사용한다.
Q. Array와 Linked List의 memory allocation은 언제 일어나며, 메모리의 어느 영역을 할당 받나?
- Array는 compile 단계에서 memory allocation이 발생한다. 이를 Static Memory Allocation이라고 한다. 이 경우 Stack memory영역에 할당된다.
- Linked List의 경우 runtime 단계에서 새로운 node가 추가될 때마다 memory allocation이 발생한다. 이를 Dynamic Memory Allocation이라고 부른다. Heap메모리 영역에 할당된다.
LinkedList vs ArrayList 특징 비교
LinkedList가 각기 노드를 두고 주소 포인터를 링크하는 식으로 자료를 구성한 이유는 ArrayList가 배열을 이용하여 요소를 저장함으로써 발생하는 단점을 극복하기 위해 고안되었기 때문이다.
| ArrayList | LinkedList | |
| 컬렉션 구성 | 배열을 이용 | 노드를 연결 (linked) |
| 데이터 접근 시간 | 모든 데이터 상수 시간 접근 | 위치에 따라 이동시간 발생 |
| 삽입 / 삭제 시간 | 삽입/삭제 자체는 상수 시간 | |
| 삽입/삭제 시 데이터 이동이 필요한 경우 추가시간 발생 | 삽입/삭제 위치에 따라 그 위치까지 이동하는 시간 발생 | |
| 리사이징 필요 | 공간이 부족할경우 새로운 배열에 복사하는 추가 시간 발생 | - |
| 데이터 검색 | 최악의 경우 리스트에 있는 아이템 수 만큼 확인 | |
| CPU Cache | 캐시 이점을 활용 | - |
ArrayList의 문제점
ArrayList는 배열 공간(capacity)가 꽉 차거나, 요소 중간에 삽입을 행하려 할때 기존의 배열을 복사해서 요소를 뒤로 한칸씩 일일히 이동해야 하는 작업이 필요하다.
이러한 부가적인 연산은 시스템의 성능 저하로 이어져 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 치명적일 수 있다. 그리고 자료들이 지속적으로 삭제되는 과정에서 ArrayList에서는 그 공간 만큼 낭비되는 메모리가 많아지게 되고 또한 ReSizing 처리에서 시간이 소모된다.
LinkedList의 장단점
반면, LinkedList는 불연속적으로 존재하는 데이터를 서로 연결(link)한 형태로 구성되어있기 때문에 공간의 제약이 존재하지 않으며, 삽입 역시 노드가 가리키는 포인터만 바꿔주면 되기 때문에 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없어 삽입 / 삭제 처리 속도가 빠르다. 따라서 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는것이 바람직하다
하지만 LinkedList 에도 만능이 아니며 단점이 존재한다.
요소를 get 하는 과정에서 ArrayList와 굉장한 성능 차이를 보이는데, ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만이 가능하기 때문이다.
예를 들어 n개의 자료를 저장할 때, ArrayList는 자료들을 하나의 연속적인 묶음으로 묶어 자료를 저장하는 반면, LinkedList는 자료들을 저장 공간에 불연속적인 단위로 저장하게 된다.
이를 그림으로 표현하자면, 아래 빌딩 그림을 메모리(RAM)으로 비유하고 각기 방을 데이터라고 비유하자면, ArrayList는 연속적인 묶음으로 되어있지만, LinkedList는 각기 다른 방에 저장되어있고 링크로 연결되어 있음을 볼 수 있다.
그래서 LinkedList는 메모리 이곳저곳에 산재해 저장되어 있는 노드들을 접근하는데 있어 ArrayList보다 당연히 긴 지연 시간이 소모되게 된다. 특히 Singly Linked List는 단방향성만 갖고 있기 때문에 인덱스를 이용하여 자료를 검색하는 애플리케이션에는 적합하지 않는다.
LinkedList의 또 다른 단점은 참조자를 위해 추가적인 메모리를 할당해야 하는 점 이다. 배열 같은 경우 그냥 데이터 그대로만 저장하면 되지만, LinkedList의 노드 같은 경우 데이터 이외에 next 나 prev 같은 참조자도 저장해야 되기 때문에 추가적인 공간이 더 필요 할 수 밖에 없다.
| LinkedList 장점 | LinkedList 단점 |
| 자료의 삽입과 삭제가 용이 | 포인터의 사용으로 인해 저장 공간의 낭비 |
| 리스트 내에서 자료의 이동이 불필요 | 알고리즘이 복잡 |
| 사용 후 기억 장소의 재사용이 가능 | 특정 자료의 탐색 시간이 많이 소요 |
| 연속적인 기억 장소의 할당이 불필요 |
LinkedList vs ArrayList 성능 비교
시간 복잡도 비교
LinkedList를 처음 배울 때 착각하는 것이, 요소를 추가하는 것과 요소를 삭제하는 것의 시간복잡도가 오로지 O(1) 이라는 점이다. 맨 앞이나 맨 뒤 요소만 추가하고 삭제한다고 가정하면 시간복잡도는 O(1)이 맞지만, 중간에 요소를 추가 / 삭제 한다면 그 중간 위치까지 탐색을 해야 하므로 최종적으로 O(N)이 된다.
※ 참고
그래도 탐색 시간(search time)에 시간이 그리 소요되지 않으면 ArrayList보다 삽입 속도가 빠르기 때문에 표기만 저렇지 왠만한 상황에선 LinkedList가 ArrayList보다 우위로 보면 된다.
| 연산 | LinkedList (doubly) | ArrayList | 추천 |
| 첫번째 위치에 insert / remove | O(1) | O(N) | LinkedList |
| 마지막 위치에 insert / remove | O(1) | O(1) / O(N) | LinkedList |
| 중간에 insert / remove | O(N) / search time + O(1) | O(N) | LinkedList |
| 값으로 search | O(N) | O(N) | ArrayList |
| 인덱스로 값 get | O(N) | O(1) | ArrayList |
| 값으로 remove | O(N) | O(N) | LinkedList |
위의 표에서 ArrayList에서 첫번째 삽입이 O(N)인 이유는 무조건적으로 요소들을 뒤로 이동해야 되기 때문이다. 그리고 마지막 위치 삽입이 O(1) 또는 O(N)이 되는 이유는 만일 공간 부족으로 인해 배열 복사가 일어나면 시간이 소요되기 때문이다.
실제 성능 측정
두 리스트에 대해 실제 메서드 동작 시간을 측정한 그래프이다.
조회(get)시에는 arraylist가 우위 지만 삽입/삭제(add/remove) 시에는 linkedlist가 뛰어난 성능을 보여준다.
public static void main(String[] args) {
//추가할 데이터의 개수를 고려해서 크기를 지정해야함
ArrayList<Number> al = new ArrayList<>();
LinkedList<Number> ll = new LinkedList<>();
System.out.println("+++ 순차적으로 추가하기 +++");
System.out.println("ArrayList : " + add1(al));
System.out.println("LinkedList : " + add1(ll));
System.out.println();
System.out.println("+++ 중간에 추가하기 +++");
System.out.println("ArrayList : " + add2(al));
System.out.println("LinkedList : " + add2(ll));
System.out.println();
System.out.println("+++ 접근시간 테스트 +++");
System.out.println("ArrayList : " + access(al));
System.out.println("LinkedList : " + access(ll));
System.out.println();
System.out.println("+++ 중간에서 삭제하기 +++");
System.out.println("ArrayList : " + remove2(al));
System.out.println("LinkedList : " + remove2(ll));
System.out.println();
System.out.println("+++ 순차적으로 삭제하기 +++");
System.out.println("ArrayList : " + remove1(al));
System.out.println("LinkedList : " + remove1(ll));
System.out.println();
}public static long add1(List list) {
long start = System.nanoTime();
for (int i = 0; i < 10000; i++)
list.add(i + 1);
long end = System.nanoTime();
return end - start;
}
public static long add2(List list) {
long start = System.nanoTime();
for (int i = 0; i < 10000; i++)
list.add(500, 1);
long end = System.nanoTime();
return end - start;
}
public static long remove1(List list) {
long start = System.nanoTime();
for (int i = list.size() - 1; i >= 0; i--)
list.remove(i);
long end = System.nanoTime();
return end - start;
}
public static long remove2(List list) {
long start = System.nanoTime();
for (int i = 0; i < 10000; i++)
list.remove(500);
long end = System.nanoTime();
return end - start;
}
public static long access(List list) {
long start = System.nanoTime();
for (int i = 0; i < 10000; i++)
list.get(i);
long end = System.nanoTime();
return end - start;
}
값이 작을 수록 빠르다
- [순차 추가] 가 linkedlist가 우위인 이유는 arraylist는 공간 부족으로 인한 배열 복사가 일어나기 때문이다.
- [중간 추가] 가 linkedlist가 우위인 이유는 arraylist는 배열 복사 및 데이터 이동(shift)가 발생하기 때문이다.
- [접근 시간] 이 arraylist가 우위인 이유는 메모리 저장 구조상 배열은 연속된 공간에 저장되고 인덱스로 단번에 엑세스하기 때문이다.
- [중간 삭제] 가 linkedlist가 우위인 이유는 요소 이동 없이 그저 노드의 포인팅만 교체만 하면 되기 때문이다.
- [순차 삭제] 가 arraylist가 우위인 이유는 아무래도 노드의 링크를 끊고 하는 작업 보단 배열에서 요소를 삭제하는게 더 빠르기 때문이다.
But) LinkedList는 의외로 잘 사용되지 않는다
보통 ArrayList 와 LinkedList 중에 어느걸 사용하면 되냐고 묻는다면, 삽입 / 삭제가 빈번하면 LinkedList를, 요소 가져오기가 빈번하면 ArrayList를 사용하면 된다 라고들 가르쳐 주지만, 사실 성능면에서 둘은 큰 차이가 없다.
예를들어 ArrayList는 ReSizing 과정에서 배열 복사하는 추가 시간이 들지만, 배열을 새로 만들고 for문을 돌려 기존 요소를 일일히 대입하는 그러한 처리가 아니라, 내부적으로 잘 튜닝이 되고 최적화 되어있어 우리가 생각하는 것처럼 전혀 느리지않다.
위의 성능 코드 예시 역시 두각을 나타내기 위해 극단적으로 나노초로 비교해서 차이가 확연히 보여서 그렇지 체감상 차이가 그리 큰 편도 아니다.
또한 외국 사례를 검색하여 살펴보면 LinkedList를 사용하는 사례보다 그냥 ArrayList를 사용하는 사례가 많은데, 자바의 컬렉션 프레임워크 등 자바 플랫폼의 설계와 구현을 주도한 조슈아 블로치(Joshua Bloch) 본인도 자신이 설계했지만 사용하지 않는다고 말할 정도이다.
몇몇 사람은 FIFO(선입선출)이 빈번할 경우, ArrayList 경우 첫번째에 요소를 추가할 때마다 자주 데이터 이동(shift)가 일어나기 때문에 큐(queue)를 사용해야 할때 LinkedList를 사용한다 라고 말하지만, 차라리 그런 경우엔 따로 ArrayDeQue라는 더욱 최적화된 컬렉션을 쓰는 것이 훨씬 좋다.
위에서 ArrayList의 경우 CPU Cache의 이점을 활용한다고 하였다. 해당 내용은 다음 포스팅 참고.
[번역] Performance of Array vs. Linked-List on Modern Computers
출처 : https://dzone.com/articles/performance-of-array-vs-linked-list-on-modern-comp%EF%BB%BF Performance of Array vs. Linked-List on Modern Computers 위에서 설명했다시피 Linked-list는 특정 지점에서 Array보다 일반적으로 더 빨랐
s-y-130.tistory.com
Array, ArrayList, LinkedList 임의의 값 탐색 속도 비교
n 개의 원소가 있다고 가정하였을때 Array, ArrayList, LinkedList 연산 비용은 다음과 같이 생각해 볼 수 있다.
| 구분 | Array | ArrayList | LinkedList |
| i 번째 탐색 | O(1) | O(1) | O(n) |
| i 번째 삽입 | O(n) + 새로운 배열 할당 비용 + 전체 배열 복사 비용 | O(n) + 복사비용 + 공간비용(capacity 초과 시) | O(n) + 앞뒤 노드 참조 맵핑 비용 |
| i 번째 삭제 | O(n) + 새로운 배열 할당 비용 + 전체 배열 복사 비용 | O(n) + i 번째 이후 복사 비용 | O(n) + 앞뒤 노드 참조 맵핑 비용 |
그런데, i 번째 원소 탐색이 아니고 랜덤한 임의의 값을 찾는 탐색이면 어떨까?
일단 예상으로는 Array > ArrayList > LinkedList 일 것 같다.
- Array는 연속적인 메모리 할당으로 cache locality가 좋다. CPU 캐시는 한 메모리 주소에 접근할 때 그 주소뿐 아니라 해당 블록을 전부 캐시에 가져오게 되는데, 이때 Array는 해당 블록에 있는 것들은 함께 캐싱되기 때문에 cache miss가 덜 발생한다.
- 이에 반해 LinkedList는 비연속적인 메모리 할당을 하기 때문에 효율적인 캐싱이 어렵고 cache miss가 많이 발생하게 되어 이에 따른 오버헤드가 있다.
- ArrayList는 내부적으로 Array를 구현하고 있어서 Array의 탐색 속도와 거의 유사할 것으로 보이나, 간접참조하고 있기 때문에 약간의 지연이 있을 것으로 예상된다.
이 예상이 맞는지 검증해 보기 위해 코드를 작성해보았다.
Array, ArrayList, LinkedList의 랜덤 값 탐색 비용 비교
1. String 타입의 랜덤한 알파벳 문자열 배열을 생성하는 클래스를 정의한다.
public class RandomArray {
private static Random random = new Random();
public static String[] makeRandomStrings(int len, int arraySize) {
String[] strs = new String[arraySize];
for (int i = 0; i < arraySize; i++) {
strs[i] = makeWord(len);
}
return strs;
}
private static String makeWord(int len) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; i++) {
sb.append((char) (random.nextInt(26) + 'a'));
}
return sb.toString();
}
}
2. 생성한 문자열들을 각 자료구조에 담아서, 동일한 조건으로 탐색할 때의 각 평균 시간을 비교헤본다.
public class RandomArrayManualTest {
private static final Random random = new Random();
private static final int arraySize = 100_000; //배열의 길이
private static final int strLen = 6; // 한 문자열의 길이
private static final int times = 100_000; // 수행 횟수
private String[] strs;
private List<String> listStrs;
private List<String> linkedStrs;
public RandomArrayManualTest(String[] strs, List<String> listStrs, List<String> linkedStrs) {
this.strs = strs;
this.listStrs = listStrs;
this.linkedStrs = linkedStrs;
}
public static RandomArrayManualTest makeRandomArrayTest() {
String[] strs = RandomArray.makeRandomStrings(strLen, arraySize);
return new RandomArrayManualTest(strs, //배열의 길이와 문자열 길이를 입력받아, 랜덤한 문자열 배열 생성
// new ArrayList 로 생성하지 않을 경우 copy하지 않고 참조만 하여 Array가 캐시 해놓은 것을 쓰기 때문에 성능비교가 제대로 안됨.
new ArrayList<>(Arrays.asList(strs)), // ArrayList 객체로 복사
new LinkedList<>(Arrays.asList(strs))); // LinkedList 객체로 복사
}
public void compareSearchTime() {
long arrayTotalTime = 0; // Array 탐색 시간 측정용
long arrayListTotalTime = 0; // ArrayList 탐색 시간 측정용
long linkedListTotalTime = 0; // LinkedList 탐색 시간 측정용
for (int i = 0; i < times; i++) { // times 만큼 시도하고, times로 나눠 평균 시간을 측정
// 임의의 문자열을 하나 pick. 동일한 조건으로 테스트 하기 위해 ArrayList와 LinkedList도 동일한 target을 사용한다.
String target = strs[random.nextInt(arraySize)];
arrayTotalTime += measureSearchInArray(target); // Array 탐색 시간 측정
arrayListTotalTime += measureSearchInArrayList(target); // ArrayList 탐색 시간
linkedListTotalTime += measureSearchInLinkedList(target); // LinkedList 탐색 시간
}
// 각각의 평균값 계산
System.out.println("Array times : " + (double)arrayTotalTime / times);
System.out.println("ArrayList times : " + (double)arrayListTotalTime / times);
System.out.println("LinkedList times : " + (double)linkedListTotalTime / times);
}
private long measureSearchInArray(String target) {
long startTime = System.nanoTime();
int j = 0;
while (!strs[j].equals(target)) {
j++;
}
return System.nanoTime() - startTime;
}
private long measureSearchInArrayList(String target) {
long startTime = System.nanoTime();
int j = 0;
while (!listStrs.get(j).equals(target)) {
j++;
}
return System.nanoTime() - startTime;
}
private long measureSearchInLinkedList(String target) {
long startTime = System.nanoTime();
linkedStrs.indexOf(target);
return System.nanoTime() - startTime;
}
public static void main(String[] args) {
RandomArrayManualTest randomArrayManualTest = RandomArrayManualTest.makeRandomArrayTest();
randomArrayManualTest.compareSearchTime();
}
}Array times : 213125.284
ArrayList times : 230597.337
LinkedList times : 248438.041
결과가 나오기까지 살짝 오래 걸리지만 이렇게 성능 테스트를 했을 때 문제점이 있다.
즉, 이렇게만 하면 제대로 된 비교를 할 수 없다. JVM warm-up을 고려하지 않았기 때문이다.
JVM warm-up에 대해서 궁금하신 분들은 다음 포스팅을 참고.
[JVM] 성능 테스트를 위한 JVM Warm-up 하기
Java 컴파일 1. 컴파일 과정 JVM 실행 전 1) 소스 코드(.java)를 바이트 코드(.class)로 변환 (Java compiler) JVM 실행 후 2) 해당 클래스를 사용하는 시점에 클래스 로더가 lazy loading 3) 로딩 된 클래스를 OS가
s-y-130.tistory.com
3. 사전에 동일 코드를 실행하는 수동 warm-up 작업 수행 후 속도 측정
main 메서드에 warm-up 작업을 추가한다.
public static void main(String[] args) {
RandomArrayManualTest randomArrayManualTest = RandomArrayManualTest.makeRandomArrayTest();
System.out.println("warm-up start --");
for (int i = 0; i < 3; i++) {
randomArrayManualTest.compareSearchTime();
System.out.println();
}
System.out.println("warm-up finish --\n");
System.out.println("measure start --");
randomArrayManualTest.compareSearchTime();
System.out.println("measure finish --");
}
수행결과
warm-up start --
Array times : 209235.002 ArrayList times : 226675.955 LinkedList times : 244810.149
Array times : 215325.015 ArrayList times : 231005.961 LinkedList times : 255013.059
Array times : 206880.443 ArrayList times : 222352.722 LinkedList times : 239497.409
warm-up finish --
measure start --
Array times : 202314.792
ArrayList times : 218000.374
LinkedList times : 234467.248
measure finish --Array > ArrayList > LinkedList 순으로 속도가 빠른 것을 확인 할 수 있다.
warm-up 타임에 중간에 예상을 벗어난 결과가 한번 발생하기도 했다. 그러나 최종 결과는 warm-up 타임 때보단 빨라진 것을 확인할 수 있다.
4. jmh를 활용하여 JVM warm-up 후 속도 측정
@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime) // 평균 시간 측정. 결과 파일에 Score로 표시
@OutputTimeUnit(TimeUnit.NANOSECONDS) // 시간 단위 설정
@Fork(5) // 벤치 마크 수행 횟수. 횟수가 늘어날수록 정밀도는 높아지지만 오래걸림
@Warmup(iterations = 3)
public class RandomArrayBenchmarkTest {
private static final Random random = new Random();
private static final int arraySize = 100_000; //배열의 길이
private static final int strLen = 6; // 한 문자열의 길이
private String[] strs;
private List<String> listStrs;
private List<String> linkedStrs;
private String target;
@Setup
public void setup(){
strs = RandomArray.makeRandomStrings(strLen, arraySize); //배열의 길이와 문자열 길이를 입력받아, 랜덤한 문자열 배열 생성
// ArrayList 객체로 복사 (new ArrayList 로 생성하지 않을 경우 copy하지 않고 참조만 하여 Array가 캐시 해놓은 것을 쓰기 때문에 성능비교가 제대로 안됨.
listStrs = new ArrayList<>(Arrays.asList(strs));
linkedStrs = new LinkedList<>(Arrays.asList(strs)); // LinkedList 객체로 복사
target = strs[random.nextInt(arraySize)];
}
@Benchmark // 벤치마크 대상
public void measureInArray() {
int i = 0;
while (!strs[i].equals(target)) {
i++;
}
}
@Benchmark // 벤치마크 대상
public void measureInArrayList() {
// listStrs.indexOf(target); // indexOf의 인자를 체크하는 비용이 추가로 발생하므로 get으로 체크
int i = 0;
while (!listStrs.get(i).equals(target)) {
i++;
}
}
@Benchmark // 벤치마크 대상
public void measureInLinkedList() {
// Array, ArrayList 처럼 get으로 체크하는 경우 매번 첫 노드부터 탐색하므로 indexOf 사용
linkedStrs.indexOf(target);
}
}Benchmark Mode Cnt Score Error Units
RandomArrayBenchmarkTest.measureInArray avgt 25 105793.230 ± 64196.021 ns/op
RandomArrayBenchmarkTest.measureInArrayList avgt 25 179614.273 ± 134637.374 ns/op
RandomArrayBenchmarkTest.measureInLinkedList avgt 25 295682.266 ± 142809.858 ns/op수동 warm-up을 했을 때와 동일한 Array > ArrayList > LinkedList 순으로 속도가 빠른 것을 확인 할 수 있다.
결론
두가지 측면에서 jmh를 활용하는 것이 좋다고 생각한다.
- 첫번째로, 수동 warm-up을 활용하였을 때는 위에서도 알 수 있듯이 결과가 일정하지 않다. 보다 정교한 성능 측정을 위해선 jmh를 사용하기를 권장한다.
- 보다 코드를 깔끔하게 짤 수 있다.
- 수동 warm-up을 활용한 경우, 성능 측정을 위해 흐름을 제어하는 코드와 실제 측정하고 싶은 연산이 코드에 혼재되어 있다. 또한 성능 측정을 위해 굳이 for문을 이용하는 것도 맘에 들지 않는다.
- 하지만 jmh를 활용하는 경우, 성능 측정을 위한 흐름 제어는 jmh에 맡기고 실제 벤치마크 하고 싶은 대상에 집중 하도록 코드를 분리하여 작성할 수 있다.
전체 코드는 아래 링크에서 확인할 수 있다.
GitHub - seyoung5744/JAVA_Study_Test
Contribute to seyoung5744/JAVA_Study_Test development by creating an account on GitHub.
github.com
참고