[Level 1] 숫자 짝꿍 - IntArray vs MutableList, 시간 측정 및 단축

[내배캠 - 오늘의 문제]

https://school.programmers.co.kr/learn/courses/30/lessons/131128

프로그래머스

 

테스트 케이스 11~15에서 시간 초과 Error가 발생하여 로직을 계속 수정(시간초과 -> 600ms -> 300ms -> 230ms)하면서 결국 해결했는데 MutableList로 선언한 변수를 IntArray로 변경하니 230ms -> 60ms로 많은 시간 단축 효과가 있었다.

 

그래서 MutableList와 IntArray의 속도 차이를 간단히 리뷰해보려 한다.

val numberCountX = MutableList(10) { 0 } // 0 ~ 9
val numberCountY = IntArray(10) { 0 } // 0 ~ 9

// 1. 공통으로 포함된 수를 뽑는다.
val time0 = System.nanoTime()
for (chx in X) {
    numberCountX[chx - '0']++
}

val time1 = System.nanoTime()
for (chy in Y) {
    numberCountY[chy - '0']++
}

val time2 = System.nanoTime()

println(time1 - time0) // MutableList 사용 시, 22356300
println(time2 - time1) //    IntArray 사용 시,  4387300

 

[GPT의 코멘트]

1. 내부 구현과 메모리 사용: IntArray는 기본 데이터 타입의 배열을 나타내며, JVM(Java Virtual Machine)에서 연속적인 메모리 할당을 사용합니다. 이는 메모리 접근 시간을 최소화하고 캐시 활용을 최적화하는 데 도움이 됩니다. 반면, MutableList는 객체 참조를 위한 배열을 사용합니다. 이는 각 요소가 객체로 간주되어 추가적인 메모리 오버헤드가 발생할 수 있으며, 메모리 접근 패턴이 IntArray보다 덜 효율적일 수 있습니다.
   
   
2. 박싱과 언박싱(autoboxing and unboxing): MutableList<Int>는 정수를 Integer 객체로 박싱해야 합니다. Kotlin은 Java 플랫폼 위에서 실행되기 때문에, JVM의 자동 박싱과 언박싱 메커니즘을 사용합니다. 이는 기본 타입 값을 객체로 변환하는 과정에서 추가적인 시간이 소요될 수 있습니다. IntArray는 기본 타입의 배열이므로 이러한 박싱/언박싱 오버헤드가 없습니다.
   
   
3. 컬렉션 API 사용: MutableList는 컬렉션 인터페이스를 구현하며, 이는 추가적인 메서드 호출과 체크를 수반할 수 있습니다. 반면, IntArray는 배열로서 더 단순하고 직접적인 메모리 접근 패턴을 가지고 있습니다.

정리 : 성능이 중요한 상황에서는 가능한 IntArray와 같은 기본 타입 배열을 사용하는 것이 좋다.

 

git code : https://github.com/rlaxodud214/CodingTest_Kotlin/commit/17664221f38a822b6ab9b18242cf11773fbeac78

 

 

안드로이드 질문방에서 알게된 정보
- 지금까지 해당 코드 전 후로 system.nanotime 값을 사용해 시간을 측정하고 개선했었는데 아래와 같은 메서드가 있었다!
-> 앞으로 코테 문제풀 때, 잘 써먹을 듯!!

import kotlin.system.measureNanoTime

val mapTime = measureNanoTime {
	val tempList = testString.map{it}
}