반응형
알고리즘을 풀며 문득 느낀게 있다. Java Collection들을 사용하며, 정확한 속도의 메커니즘을 모르니 이것 저것 써보며 속도가 줄어드나 확인해보곤 한다.
그래서 Java Collections의 속도를 비교하여 어떤 메소드를 사용할 때 어떤 Collection을 써야할지 판단하기위해 자료 정리를 하려한다.
1. List
|
|
Add
|
Remove
|
Get
|
Contains
|
Data Structure
|
|
ArrayList
|
O(1)
|
O(n)
|
O(1)
|
O(n)
|
Array
|
|
LinkedList
|
O(1)
|
O(1)
|
O(n)
|
O(n)
|
Linked List
|
|
CopyonWriteArrayList
|
O(n)
|
O(n)
|
O(1)
|
O(n)
|
Array
|
검증결과
- 조회와 삭제의 빈도수를 고려하여 LinkedList를 사용할지 ArrayList를 사용할지 판단해야한다.
2. Set
|
|
Add
|
Contains
|
Next
|
Data Structure
|
|
HashSet
|
O(1)
|
O(1)
|
O(h/n)
|
Hash Table
|
|
LinkedHashSet
|
O(1)
|
O(1)
|
O(1)
|
Hash Table + Linked List
|
|
EnumSet
|
O(1)
|
O(1)
|
O(1)
|
Bit Vector
|
|
TreeSet
|
O(log n)
|
O(log n)
|
O(log n)
|
Red-black tree
|
|
CopyonWriteArraySet
|
O(n)
|
O(n)
|
O(1)
|
Array
|
|
ConcurrentSkipList
|
O(log n)
|
O(log n)
|
O(1)
|
Skip List
|
검증결과
- ADD 하는 속도에서는 대동소이하며, next로 메소드를 호출할 경우 LinkedHashSet이 더 빠르다.
- 단순 시간복잡도만 비교하였을땐 LinkedHashSet을 사용하는게 가장 속도적인 측면에서는 우수한 것 같다.
3. Queue
|
|
Offer
|
Peak
|
Poll
|
Size
|
Data Structure
|
|
PriorityQueue
|
O(log n )
|
O(1)
|
O(log n)
|
O(1)
|
Priority Heap
|
|
LinkedList
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
Array
|
|
ArrayDequeue
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
Linked List
|
|
ConcurrentLinkedQueue
|
O(1)
|
O(1)
|
O(1)
|
O(n)
|
Linked List
|
|
ArrayBlockingQueue
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
Array
|
|
PriorirityBlockingQueue
|
O(log n)
|
O(1)
|
O(log n)
|
O(1)
|
Priority Heap
|
|
SynchronousQueue
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
None!
|
|
DelayQueue
|
O(log n)
|
O(1)
|
O(log n)
|
O(1)
|
Priority Heap
|
|
LinkedBlockingQueue
|
O(1)
|
O(1)
|
O(1)
|
O(1)
|
Linked List
|
검증결과
- 시간복잡도만 비교하였을 때 LinkedList가 가장 우수하여 보였지만, Offer메소드 쪽에서 우선순위큐가 더 빨랐다. 하지만 Poll을 호출하는 속도는 LinkedList가 압도적으로 우수하여, Offer와 Poll 둘 다 사용할 경우 LinkedList가 속도측면에서는 가장 우수해 보인다.
- Offer쪽에서 LinkedList가 더 빨라야 하는데 왜 이런 결과가 나왔는지는 좀 더 분석이 필요할 것 같다. (추후정리예정)
4. Map
|
|
Get
|
ContainsKey
|
Next
|
Data Structure
|
|
HashMap
|
O(1)
|
O(1)
|
O(h / n)
|
Hash Table
|
|
LinkedHashMap
|
O(1)
|
O(1)
|
O(1)
|
Hash Table + Linked List
|
|
IdentityHashMap
|
O(1)
|
O(1)
|
O(h / n)
|
Array
|
|
WeakHashMap
|
O(1)
|
O(1)
|
O(h / n)
|
Hash Table
|
|
EnumMap
|
O(1)
|
O(1)
|
O(1)
|
Array
|
|
TreeMap
|
O(log n)
|
O(log n)
|
O(log n)
|
Red-black tree
|
|
ConcurrentHashMap
|
O(1)
|
O(1)
|
O(h / n)
|
Hash Tables
|
|
ConcurrentSkipListMap
|
O(log n)
|
O(log n)
|
O(1)
|
Skip List
|
검증결과
- Get에서 약간의 속도차이만 날뿐 나머지는 대동소이하다. Map쪽은 취향껏 사용해도 상관이 없을 것 같다.
결론
개인 PC에 따라, 환경에 따라 어느정도 속도 차이는 있을 것 이지만, 자바 Collections는 데이터 구조에 따라 메소드의 성능이 제각기 다르다. 본인이 이 구조를 어느정도 파악한 후, 상황에 따라 적절한 Collections를 사용하는 것이 조금 더 좋은 퍼포먼스를 내는 방법이 아닐까 싶다.
출처
반응형
'Language > ☕️Java' 카테고리의 다른 글
| JAVA로 카카오 메시지 API연동 (4) | 2022.02.25 |
|---|---|
| JVM 아키텍처 1탄 - Class Loader SubSystem (0) | 2021.12.08 |
| Java 직렬화란(Serialization)? (0) | 2021.08.19 |
| class파일로 컴파일 후, FTP를 통한 배포에서 발생한 문제. (UnsupportedClassVersionError ) (0) | 2021.08.14 |
| String을 쓰지 말라는 이유 (1) | 2020.06.16 |
댓글