Kotlin에서 Set에 Array 넣는 방법

안녕하세요.

지난번에 kotlin의 Equality에 대해 포스팅했었는데요. 아래 포스팅입니다.

Kotlin의 Equality, == vs ===

Structural equality와 Referential equality, 동일성과 동등성에 대해 정리하면서 == 연산자와

===

연산자의 차이에 대해 알아보았습니다.

그리고 equals를 호출했을 때 동일성과 동등성을 비교해 주는 것의 차이를 알아보았죠.

여기에서 HashSet<List<Int>>는 동등성을 비교해 주면서, 원소로 주어진 리스트가 동일한 크기면서 동일한 원소를 동일한 순서로 저장하고 있다면 return true로 동작한다고 말씀드렸습니다.

그러나 HashSet<IntArray>는 동일성을 비교해 주면서, 완벽히 동등한 원소가 들어오더라도 주소값을 통해 set 내부 원소 중복을 체크하기 때문에 기대했던 대로 동작하지 않는다...고 말씀드렸었죠.

마지막으로 List와 Array는 연산에 상당한 시간복잡도 차이가 존재하기 때문에 List에서만 동등성을 비교해 주는 것이 조금 아쉽다고 정리했었습니다.

그랬더니 어느 분이 아래와 같은 댓글로 의견을 주셨는데요.

오...

설득력이 있습니다.

그래서 직접 해봤습니다.

놀라운 결과가 나왔어요.

 

 

실험

IntArrayWrapper를 Set에 넣는 것과 List<Int>를 Set에 넣는 것 사이에 시간 차이가 있을까?

이게 궁금했습니다.

결론만 말해보자면 IntArrayWrapper가 더 빠른 것으로 측정되었습니다. N이 작으면 차이가 근소하기는 하지만 N이 커질수록 유의미한 시간 차이가 존재하기는 하더라고요.

 

IntArrayWrapper

class IntArrayWrapper(private val array: IntArray) {

	override fun equals(other: Any?): Boolean {
		if (this === other) return true
		if (other !is IntArrayWrapper) return false

		return array.contentEquals(other.array)
	}

	override fun hashCode(): Int {
		return array.contentHashCode()
	}
}

IntArrayWrapper의 코드는 이렇습니다.

equals를 오버라이드해서

1. 주소값으로 동일성 비교

2. 타입 비교

3. contentEquals로 동등성 비교

를 해 주었어요.

동등성으로 원소를 구별하는 것이 목표이기 때문에 hashCode 또한 contentHashCode로 오버라이드해 주었습니다.

 

테스트 방법

1. 동일한 원소: IntWrapperArray와 List<Int>를 set에 N번 추가하기

2. 다른 원소: IntWrapperArray와 List<Int>를 set에 N번 추가하기

 

1번 코드

동일한 원소를 set에 N번 추가하기

import kotlin.system.measureTimeMillis

class IntArrayWrapper(private val array: IntArray) {

	override fun equals(other: Any?): Boolean {
		if (this === other) return true
		if (other !is IntArrayWrapper) return false

		return array.contentEquals(other.array)
	}

	override fun hashCode(): Int {
		return array.contentHashCode()
	}
}

fun main() {
	val N = 10000000
	val setWrapperArray = HashSet<IntArrayWrapper>()
	val setOriginList = HashSet<List<Int>>()

	// IntArray WrapperClass, set에 N개의 원소 추가하기
	val timeWrapperArray = measureTimeMillis {
		for (i in 0 until N) {
			setWrapperArray.add(IntArrayWrapper(intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)))
		}
	}
	println(setWrapperArray.size)
	println("IntArrayWrapper = $timeWrapperArray")

	val timeOriginList = measureTimeMillis {
		for (i in 0 until N) {
			setOriginList.add(listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
		}
	}
	println(setOriginList.size)
	println("List<Int> = $timeOriginList")

	var list = mutableListOf<List<Int>>()
	val timeOriginListAdd = measureTimeMillis {
		for (i in 0 until N) {
			list.add(listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
		}
	}
	println(list.size)
	println("List<Int> mutableList Add = $timeOriginListAdd")
}

N은 10000000으로 주었습니다.

더 크게 주려면 heap 옵션을 변경하셔야 할 듯 합니다. 저는 0 하나 더 붙이니까 메모리가 터지더라고요.

충분히 유의미한 시간 차이가 보이기 때문에 굳이 옵션 변경까지는 하지 않았습니다.

위의 코드를 실행시켜 보면 아래와 같은 결과가 나옵니다.

1
IntArrayWrapper = 385
1
List<Int> = 758
10000000
List<Int> mutableList Add = 1174

의도했던 대로 동작하는지 확인하기 위해 size도 함께 출력해주었습니다.

List<Int>가 더 느린 것으로 나왔습니다.

아마 IntArray는 물리적으로 연속적인 메모리에 원소가 저장되고, List<Int>는 논리적으로 연속적인 메모리에 원소가 저장되기 때문에 다음 원소로 넘어가는 동작이 이런 차이를 만들어내지 않았을까 싶네요.

 

2번 코드

다른 원소를 set에 N번 추가하기

import kotlin.system.measureTimeMillis

class IntArrayWrapper(private val array: IntArray) {

	override fun equals(other: Any?): Boolean {
		if (this === other) return true
		if (other !is IntArrayWrapper) return false

		return array.contentEquals(other.array)
	}

	override fun hashCode(): Int {
		return array.contentHashCode()
	}
}

fun main() {
	val N = 10000000
	val setWrapperArray = HashSet<IntArrayWrapper>()
	val setOriginList = HashSet<List<Int>>()

	// IntArray WrapperClass, set에 N개의 원소 추가하기
	val timeWrapperArray = measureTimeMillis {
		for (i in 0 until N) {
			setWrapperArray.add(IntArrayWrapper(intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, i)))
		}
	}
	println(setWrapperArray.size)
	println("IntArrayWrapper = $timeWrapperArray")

	val timeOriginList = measureTimeMillis {
		for (i in 0 until N) {
			setOriginList.add(listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, i))
		}
	}
	println(setOriginList.size)
	println("List<Int> = $timeOriginList")

	var list = mutableListOf<List<Int>>()
	val timeOriginListAdd = measureTimeMillis {
		for (i in 0 until N) {
			list.add(listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, i))
		}
	}
	println(list.size)
	println("List<Int> mutableList Add = $timeOriginListAdd")
}

이번에는 각 set의 원소의 마지막마다 10 대신 i를 넣어주었습니다.

모두 다른 원소를 넣어준 것이죠.

위의 코드를 실행시켜 보면 아래와 같은 결과가 나옵니다.

10000000
IntArrayWrapper = 1083
10000000
List<Int> = 1577
10000000
List<Int> mutableList Add = 794

size를 보니 의도했던 대로 다 잘 들어갔고, 여기에서도 약간의 시간 차이가 보이네요.

본격적으로 파보자면 N도 다양하게 넣어보고 원소도 다양하게 넣고 해야 할 것 같지만 실제로 시간 차이가 존재한다는 것은 명확한 것 같습니다.

신기하네요...

코드를 기억해서 써먹는다면 리스트에서 원소의 동등성을 체크하고 싶을 때 유용하게 사용할 수 있을 것 같습니다.

물론 IntArrayWrapper는 원소 추가가 어렵고, List는 mutableList를 사용할 경우 원소 추가 및 삭제가 가능하기 때문에 각 상황마다 어떤 자료구조를 선택할지는 개발자의 몫입니다.