emrdbs123   3년 전

이 문제의 핵심은 MST 를 구성하는 엣지의 후보군의 공간복잡도를 낮게 가져가는 방식을 찾는것입니다.

단순하게 가능한 모든 Edge 를 때려박으면 n * (n-1) /2 개의 Edge 를 모두 Queue 나 List에 담아야 해서 메모리가 초과 됩니다. (1 % -> 바로 터짐)

(x,y,z) 별로 정렬을 수행하여 인접한 좌표 끼리만 실제 MST 의 Edge 가 될 수 있습니다. (다른 분들 풀이 보고 알았음...)

그래서 3 * (n - 1) 개의 Edge 후보군을 저장하여 정렬을 수행해야합니다.

그런데 이 문제에서 아래와 같은 kotlin 의 정렬 API 를 사용하면 메모리 초과가 발생합니다. (7% 에서 터짐)

/* 터지는 방식들 */

private data class Point(val idx: Int, val value: Int) // 각 (x,y,z) 별 인덱스와 값을 담을 data class

val x = mutableListOf() // x 값의 목록을 담을 리스트

/* x 값을 입력 받는다 */

/* case 1 */   x.sortBy { it.value }                     // 정렬을 한다. -> 터짐
/* case 2 */   x.sortWith(comparaeBy {it.value})         // 위 코드와 같음 -> 터짐
/* case 3 */   val valueComp =  comparaeBy {it.value}    // comp 를 별도 저장하고 정렬 한다 -> 터짐
               x.sortWith(valueComp)

이 문제를 해결 하기 위해서는 Point 클래스를 Comparable 을 구현한 형태로 바꾸어 주던가 Comparator 를 생성할때 

kotlin 의 compareBy 가 아니라 람다를 이용해 직접 만들어 주어야 합니다.


/* 안 터지는 방식 들 */ 

/* case 4 */ private data class Point(val idx: Int, val value: Int) : Comparable<Point> {
                    override fun compareTo(other: Point) = value - other.Value  
            }
            x.sort() // -> comparable 을 이용한 sort 수행 comparator 지정 x 

/* case 5 */  val valueComp = Comparator<Point> { p1, p2 -> p1.value - p2.value }// comp 를 직접 만든다 (compareBy 사용 x)
              x.sortWith(valueComp)

이게 왜 그런지 하루정도 머리 박으면서 여러 실험을 해보았는데 정확한 이유나 발생 조건을 알아내지는 못했습니다. 

(여러 방식으로 머리 박아본 실험 - 깃헙 링크)

실험 해보니 문제가 Kotlin 의 Comparator 생성 API 에서 활용하는 compareValues API 에서 === 비교를 하고 또한 뭔가 타입 이레이져같은게 동작해서 컴파일러가 얘를 객체타입으로 인식해서 각 Primitive Int 를 객체 Integer 로 변환해 힙 메모리에 저장하는거 같긴한데 정확한지는 잘 모르겠습니다.


Queue 로도 실험해보고 다른 여러 방식으로도 실험해 보았는데 확실히 compareValues 얘가 포함된 API 를 사용할때 문제가 발생하기는 합니다.

혹시 이유를 아시는 분은 알려주시면 감사하겠습니다.

asdfghjkl46   3년 전

글이 많이 도움이 되었습니다. 실제로 몇몇 문제에서 sortWith을 버리고 객체에 CompareTo를 구현하는 방식으로 정렬할 경우 메모리 초과를 피하는 것 같아요.

코틀린 API의 sort를 구현한 소스를 보면 단순히 자바의 sort를 호출하더군요. (참조 - https://ongveloper.tistory.com...)

그리고 자바의 Collections에 정의된 sort는 merge sort와 insert sort를 혼합한 tim sort를 사용하는 데, 저도 잘 모르지만 merge sort 방식이 메모리에 새로운 버퍼를 의미 있는 수준까지 생성하는 것 같습니다.

emrdbs123   3년 전

요약 입니다 :)

- compareValues 를 사용하면 null 비교에 따른 불필요한 Wrapper 클래스 생성 발생

- comparingInt 와 같은 Primitive Type 전용 메서드를 사용하면 메모리 사용량에 영향 없음

----

하지만 Kotlin 기본 Comparator 생성 API 에서는 모든 Type 에 대해 compareValues 를 기본적으로 사용하기 때문에 Primitive Type 을 비교할때 메모리 낭비가 발생함

따라서 메모리 제한이 심한 문제, 상황에서는 sortBy 를 비롯한 compareValues 를 호출하는 정렬 API 를 이용하지 말자.

댓글을 작성하려면 로그인해야 합니다.