Java Collections 시간 복잡도

Java Collections 시간 복잡도

알고리즘을 풀며 문득 느낀게 있다. 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쪽에서 왜 이런 결과가 나왔는지는 좀 더 분석이 필요할 것 같다. (추후정리예정) 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를 사용하는 것이 조금 더 좋은 퍼포먼스를 내는 방법이 아닐까 싶다.

출처

Information Technology Gems: Java Collections – Performance (Time Complexity) (infotechgems.blogspot.com)

from http://foot-develop.tistory.com/15 by ccl(A) rewrite - 2021-12-03 18:27:41