Android Improve time complexity, using HashMap
사용 언어: Kotlin 1.9.22
사용 버전: Android Studio Hedgehog 2023.1.1 Patch 2
무엇인가를 찾기 위해 contains는 N의 시간을 가지는 반면, HashMap은 1의 시간을 가집니다.
또, HashMap과 Map 그리고 LinkedHashMap도 다뤄보겠습니다.
AllFlightRepository.kt
fun getAllFlightsStream()
아래처럼 favorite를 구분하기 위해 favoriteIds라는 mutableList를 만들었습니다.
사용 버전: Android Studio Hedgehog 2023.1.1 Patch 2
안드로이드 Improve time complexity, using HashMap을 알아보겠습니다.
HashMap을 사용하면, collections의 contains를 사용하는 것보다 시간 복잡도를 많이 향상시킬 수 있습니다.무엇인가를 찾기 위해 contains는 N의 시간을 가지는 반면, HashMap은 1의 시간을 가집니다.
또, HashMap과 Map 그리고 LinkedHashMap도 다뤄보겠습니다.
AllFlightRepository.kt
fun getAllFlightsStream()
아래처럼 favorite를 구분하기 위해 favoriteIds라는 mutableList를 만들었습니다.
그러고는 contains를 사용하여 해당 문구가 포함되어 있는지 확인합니다.
이것은 추가하는 작업과 확인하는 작업까지 해서 2N이라는 시간이 소비됩니다.
이러한 복잡도를 개선하기 위해 HashMap으로 변환할 것입니다.
Kotlin에는 여러 Map 종류가 있지만, Map과 HashMap, LinkedHashMap이 세 가지를 비교해 보겠습니다.
Map 공식 문서
Map은 interface로 사실 직접적으로 사용되지는 않습니다.
설명으로는 key가 중복되지 않는 값이어야 한다고 합니다.
HashMap은 MutableMap을 상속받으며, keys, values 그리고 entries의 순서를 보장하지 않습니다.
LinkedHashMap 공식 문서
LinkedHashMap은 MutableMap을 상속받으며, entries가 들어오는 순서를 보장합니다.
재미난 것은 mutableMapOf를 타고 들어가면 LinkedHashMap을 할당하는 것을 볼 수 있다는 것입니다.
즉, 그냥 mutableMapOf를 사용하면 LinkedHashMap을 사용하게 되는 것입니다.
mapOf는 읽기만 가능하고 입력이 불가능하므로 입력 순서가 존재하지 않습니다.
그래서 위의 속도를 향상하는 상황에서 순서는 중요하지 않으므로 mutableMap보다는 HashMap을 사용하기로 결정했습니다.
아까의 코드는 이렇게 변경 가능합니다.
이렇게 되면, 추가하는 데 N의 시간이 걸리고, 검색하는 데 1이 걸리므로 N+1로 개선됩니다.
참고 프로젝트:
끝.
카테고리: Android
댓글
댓글 쓰기
궁금한 점은 댓글 달아주세요.
Comment if you have any questions.