들어가기 전에
백준에 있는 자료구조 문제를 풀다가 쉬워보여서 신명나게 빨리 풀고 제출해보았지만, 이게 웬걸.. 시간초과다.
문제는 정말 쉬운 문제이다.
원소가 하나 남을 때까지 맨 앞의 원소를 삭제하거나, 맨앞의 원소를 삭제하고 바로 뒤에 추가하는 행동을 반복하면 된다.
문제 풀이
물론 문제에서 요구하는건 큐를 유도하지만 문득 MutableList를 사용해서도 풀 수 있지 않을까?
하는 마음에 Queue의 remove()을 MutableList의 removeFirst()로 먼저 구현해보았다.
시간초과
어 이거 왜이러지? 하면서 다시 정해법인 Queue를 사용해서 풀자.
정답입니다!
왜 그럴까?
다음은 내가 풀이한 코드의 두방법을 시간을 재보는 코드이다.
import java.util.LinkedList
import java.util.Queue
import kotlin.system.measureTimeMillis
fun main() {
val n = readln().toInt()
val list = MutableList(n) { it + 1 }
var toggle1 = true
val listTime = measureTimeMillis {
while (list.size != 1) {
if (toggle1) list.removeFirst() else list.add(list.removeFirst())
toggle1 = !toggle1
}
}
val queue: Queue<Int> = LinkedList()
repeat(n) {
queue.add(it + 1)
}
var toggle2 = true
val queueTime = measureTimeMillis {
while (queue.size != 1) {
if (toggle2) queue.remove() else queue.add(queue.remove())
toggle2 = !toggle2
}
}
println("$listTime mills")
println("$queueTime mills")
}
문제에서 요구하는 최대 n은 500,000 이기때문에 최대값으로 시간을 측정해보면? 다음과 같은 결과가 나온다.
약 500배가 차이나는 엄청난 시간 속도 차이를 볼 수 있다. 왜그럴까?
가설
Kotlin에서MutableList의 구현체로Java의ArrayList()가 나온다.
또한 나는 실험에 있어서Queue의 구현체로Java의LinkedList()를 사용했다.
결국에ArrayList()와LinkedList()의 작동 방식 차이에서 나오는 시간차이지 않을까? 싶었다.
탐구 과정
먼저 나는
removeFirst()가 어떻게 구현이 되어있는지 확인해보았다.
다음과 같이 구현 되어있었다.
리스트가 비었으면 예외를, 그렇지 않다면removeAt(0)을 호출한다.
@SinceKotlin("1.4")
@WasExperimental(ExperimentalStdlibApi::class)
public fun <T> MutableList<T>.removeFirst(): T
= if (isEmpty()) throw NoSuchElementException("List is empty.") else removeAt(0)다시
removeAt()으로 가보자.
MutableList인터페이스가 나오는데 내가 궁금한건 정작 코드가 실행되는 구현체다.
나는
ArrayList가 궁금한 것이니 3개 다 찾아봤지만,
단 하나도 구현이 된 코드를 볼 수 없었다.
코틀린의expect class만 있어서 구현이 되어있진 않고 추상클래스 처럼 명시되어있었다. (이거 어떻게 JVM꺼 actual class를 볼 수 있는지 아시는 분 댓글 주시면 너무 감사하겠습니다 ㅠㅠ)
자 다시 돌아와서 결국 찾아낸건 Kotlin 공식 문서에서 검색하여 깃허브 링크를 타고 Native로 구현된 걸 볼 수 있었다. 하지만 이게 JVM 상에서 실행했을 때와 같은 로직을 수행하는지는 알지 못하여 나중에 JVM actual class을 볼 수 있는 방법을 다시 알게되면 수정하겠다.
override actual fun removeAt(index: Int): E {
checkIsMutable()
checkForComodification()
AbstractList.checkElementIndex(index, length)
return removeAtInternal(offset + index)
}
checkIsMutable()
checkForComodification()
AbstractList.checkElementIndex(index, length)
직접 더 들어가서 위의 이 친구들을 확인해보니 딱히 시간 복잡도를 잡아 먹을 거 같진 않았다.
문제는
removeAtInternal인거 같으니 다시 한번 들어가서 확인해보자.private fun removeAtInternal(i: Int): E { registerModification() if (backingList != null) { val old = backingList.removeAtInternal(i) length-- return old } else { val old = backingArray[i] backingArray.copyInto(backingArray, startIndex = i + 1, endIndex = offset + length, destinationOffset = i) backingArray.resetAt(offset + length - 1) length-- return old } }
마찬가지로
registerModification()는O(1)의 작업이니 무시하도록 하자.
backingList가 존재하냐 하지않냐에 대한 분기문이 있고, 결국에 많은 시간을 잡아먹는 애는backingArray.copyInto()이 부분이다.
배열을 복사하는 로직이다 보니 당연스럽게 시간을 많이 사용하게 한다.
다시 돌아와서 정리해보자면
removeFirst()를 호출하면 결국에removeAt(0)을 호출하는 것이고 곧removeAtInternal()을 호출한다.
또한 이것은 배열을 복사하는 행위를 하게 된다.
이것은 매우 큰 리소스를 잡아먹는 행위이다.
문제에서 보면 최대값이 500,000이므로 결국에 배열 복사를 50만번 하는 것과 같다. 32초가 걸린 이유가 여기에 있다.
그럼 다시 이번엔 Queue를 확인해보자
Queue는 구현체로LinkedList()를 사용했다.
그리고 내가 사용했던대로remove()를 호출하면removeFirst()가 호출되고 결국에 다음과 같이unlinkFirst()를 호출하게 된다.
로직을 보면 알겠지만, 상대적으로 ArrayList()의removeFirst()보다 훨씬 빠르다.
그러다 보니 극단적인 시간 차이가 난 것 같다.
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}결론
결론은 내가 세운 가설대로
ArrayList와LinkedList의 작동 방식 차이에서 있었다.
ArrayList는 결국에Object[]을 가지고 있고 원소를 추가, 제거 함에 따라 배열을 복사하는 오버헤드가 있다.
반면LinkedList는 구현 그대로 앞의 노드만 참조를 해제하고 다음 노드를 제일 처음 노드라고 지정만 해놓으면 되는 차이였다.
마치며..
개발자로서 항상 자료구조가 중요하단 생각이 든다.
자료구조의 내부 사정을 알아야 추후에 성능을 더 중요시 할 때와 성능보다 코드의 가독성 및 편의성을 생각할지 고를수 있는 선택권이 비로소 생긴다고 생각한다. (ex.IntArray와List<Int>의 차이)
내가 자료구조를 잘 모르면 그런 생각이나 할 수 있을까?
늘 겸손해지는 프로그래밍 세계이다.
긴글 읽어주셔서 감사합니다!
개선할 점, 혹은 잘못된 점이 있다면 댓글 주시면 정말 감사하겠습니다! 😙
