스택 사용하기

코틀린 컬렉션에는 스택이 따로 구현되어 있지 않다.

스택을 사용하기 위해서는 java.util.Stack 클래스를 사용하거나 MutableList, ArrayList의 add()와 removeLast()를 사용해 스택처럼 사용한다.

궁금중

자바로 구현된 Stack과 코틀린 네이티브인(결국 Java로 컴파일되서 JVM에 올라가긴 하지만) Mutable, ArrayList를 사용하는 경우의 성능차이가 궁금해서 push, pop의 시간을 측정해보았다.

fun main() {
    val repetitions = 10000000
    val stack1 = Stack<Int>()
    val stack2 = mutableListOf<Int>()
    val stack3 = arrayListOf<Int>()

    val pushTime1 = measureNanoTime { repeat(repetitions) { stack1.push(it) } }
    val pushTime2 = measureNanoTime { repeat(repetitions) { stack2.add(it) } }
    val pushTime3 = measureNanoTime { repeat(repetitions) { stack3.add(it) } }
    val mid1 = listOf(pushTime1, pushTime2, pushTime3).sorted()[1]

    println("${pushTime1 - mid1} ${pushTime2 - mid1} ${pushTime3 - mid1}")

    val popTime1 = measureNanoTime { repeat(repetitions) { stack1.pop() } }
    val popTime2 = measureNanoTime { repeat(repetitions) { stack2.removeLast() } }
    val popTime3 = measureNanoTime { repeat(repetitions) { stack3.removeLast() } }
    val mid2 = listOf(popTime1, popTime2, popTime3).sorted()[1]

    println("${popTime1 - mid2} ${popTime2 - mid2} ${popTime3 - mid2}")
}

결과적으로 push는 Stack, MutableList, ArrayList 순으로 빨랐고 pop은 ArrayList, MutableList, Stack 순으로 빨랐다.

Stack의 경우 Vector로 구현되어 있어 pop시 동기화가 필요해 pop에서 성능이 상대적으로 낮은 것으로 나타났다.

신기한 점은 ArrayList는 MutableList를 구현한 컬렉션이고 mutableListOf()는 ArrayList를 반환하는데도 성능차이가 나타났다는 것이다. nano 단위 측정이기에 오차라고 볼 수도 있으나 같은 ArrayList지만 성능차이가 나타난 점이 신기했다.

결론

ArrayList나 MutableList를 스택 대용으로 사용하는 것은 문제가 없다