Collections vs. Sequences
Collections에 대해 정의된 람다를 인자로 받는 확장 함수(filter(), map(), find(), groupBy())는 inline 함수로 정의되기 때문에 익명 클래스 객체 생성 측면에 대해서는 퍼포먼스 오버헤드에 대해 걱정할 필요가 없이 자유롭게 사용할 수 있다.
다만, Collections 확장 함수의 경우 퍼포먼스 측면에서 문제가 있다. 확장 함수를 호출할 때마다 새로운 Collection이 생성된다는 것이다. 아래 코드를 보자.
val list = listOf(1, 2, -3) // [1, 2, -3]
val maxOddSquare = list
.map { it * it } // [1, 4, 9]
.filter { it % 2 == 1 } // [1, 9]
.maxOrNull() // 9
fun main() {
println(maxOddSquare)
}위 코드에서 확인할 수 있듯이 각 확장 함수를 사용할 때마다 새로운 Collection이 생성된다. 결과적으로는 최종 생성된 결과물만 필요하지만, intermediate collection이 생성된다는 것을 알 수 있다. 만약 위 코드가 늘어나서 call chain 연산이 발생하는 경우 퍼포먼스 오버헤드가 발생할 수 있다.
이러한 문제를 피하기 위해 탄생한 것이 Sequence 이다. Sequence는 Java의 stream에 대응되는 개념이다. Sequence의 경우 lazy evaluation으로 처리된다. 반면 collections는 eager evaluation으로 처리되게 된다. 그렇다면 위 코드를 아래로 변환해 보자.
val list = listOf(1, 2, -3) // [1, 2, -3]
val maxOddSquare = list
.asSequence()
.map { it * it }
.filter { it % 2 == 1 }
.maxOrNull()
fun main() {
println(maxOddSquare)
}asSequence() 확장 함수를 사용하면 Collection을 Sequence로 변환하게 되고, 이로써 중간 과정에서 intermediate collection이 생성되지 않아 퍼포먼스 측면에서 우위를 점할 수 있다. lazy evaluation을 통해 결과가 필요한 시점에만 연산을 수행하여 최종 결과만을 반환하게 되는 것이다. 이제 Sequence에 대해 더 알아보도록 하자.
Sequences
n 개의 원소를 갖고 있는 collection과 sequence가 있다고 가정하자. 이 때, map()과 find() 순서로 call chain 연산을 진행한다면 어떻게 되는가?
collection의 경우 n 개의 원소를 모두 map() 한 뒤, find() 연산을 진행한다. 반면 sequence의 경우 원소를 하나씩 map() 하고, 해당 원소에 대해 find() 연산을 진행한다. 그러다 조건에 맞는 원소가 발견되는 경우 연산을 종료한다. 아래 예제를 통해 결과를 확인하도록 하자.
val list2 = listOf(1, 2, 3, 4)
fun c(num: Int) : Int {
println("c$num")
return num
}
fun s(num: Int) : Boolean {
println("s$num")
return num % 2 == 0
}
fun main() {
// c1 c2 c3 c4 s1 s2 s3 s4
println("collections : ${list2.map(::c).filter(::s)}")
// c1 s1 c2 s2 c3 s3 c4 s4
println("sequence : ${list2.asSequence().map(::c).filter(::s).toList()}")
// no terminal operation -> no actual operation
println("sequence no terminal operation : ${list2.asSequence().map(::c).filter(::s)}")
}실행 결과는 위 주석 내용과 같다. collection의 경우 map 연산이 모두 종료된 이후 filter를 진행하며, sequence의 경우 map 연산 1회 직후 filter 연산을 즉시 진행하는 모습을 볼 수 있다.
그러나 위 코드의 마지막 줄은 실제 연산이 발생하지 않는다. 왜냐하면 sequence의 경우, sequence가 아닌 다른 타입을 반환하는 terminal operation이 실행되어야 하는데, 그것이 실행되지 않았으므로 연산이 아예 수행되지 않는다.
Sequence 생성
sequence를 생성하는 방법을 알아 본다.
asSequence()
이 방법은 위에서 알아본 바와 같다. collections의 call chain에서 사용하면 된다.
generateSequence(nextFunction: () -> T?)
람다로 정의된 nextFunction에 따라 무한히 원소를 생성하다가, nextFunction이 null을 반환할 때까지 반복하고 종료된다. 가령, input text file을 record 단위로 읽어 가다가 sequence를 생성하는 예시를 들 수 있다.
generateSequence(seed: T?, nextFunction: () -> T?)
seed에 인자로 받은 값을 첫 원소로 생성한다. 그 다음, nextFunction을 통해 seed를 변환해 가며 무한히 반복하고, 원소를 생성한다. 규칙에 따른 원소 생성이 주 목적일 때 사용한다. take() 함수를 통해 원하는 지점까지의 값을 가져갈 수 있다.
yield
yield를 사용하는 방법같은 경우 가장 자유도가 높게 sequence를 생성할 수 있다. yield(value), yieldAll(list), yieldAll(sequence)를 사용해 원하는 원소를 자유롭게 추가할 수 있다. 아래는 yield의 예제이다.
val sequence = sequence {
val start = 0
yield(start)
yieldAll(1..5 step 2)
yieldAll(generateSequence(8) { it * 3 })
}
val numbers = sequence {
var x = 0
while (true) {
yield(x++)
}
}
val mySequence = sequence {
yield(1)
yield(3..5)
yield(listOf(7, 9))
}
fun main() {
println(sequence.take(7).toList())
println(numbers.take(10).toList())
println(mySequence.toList())
}call chain 최적화
제목과 같이, call chain을 최적화할 수 있는 방법은 무엇일까. Sequence를 사용하지 않는다면 아래 2가지 방법이 선택지가 된다.
- call chain에 대응되는 1개의 확장 함수만을 사용
collection을 사용할 때 만약 여러 확장 함수를 하나의 확장 함수로 변경할 수 있다면, 그렇게 하는 것이 좋다. 앞서 말했듯 collection 확장 함수는 intermediate collection을 생성하기 때문이다. 아래 코드와 같이 사용한다.
data class PersonInfo(
val age: Int,
val isPublicProfile: Boolean,
val name: String
)
class Person {
// 각 함수들의 코드는 같은 연산을 수행하는 코드이다.
// 윗줄은 call chain에 대응되는 함수 2개 이상, 아랫줄은 1개의 함수만을 사용한 경우이다.
lateinit var people: ArrayList<PersonInfo>
fun showCountUnderAge() {
println("showCountUnderAge")
println("before:${people.filter { it.age < 21 }.size}")
println("after:${people.count { it.age < 21 }}")
println()
}
fun showSortedAge() {
println("showSortedAge")
println("before:${people.sortedBy { it.age }.reversed()}")
println("after:${people.sortedByDescending { it.age }}")
println()
}
fun isPublicProfile() {
println("isPublicProfile")
println("before:${people.map { person ->
person.takeIf { it.isPublicProfile }?.name
}.filterNotNull()}")
println("after:${people.mapNotNull { person ->
person.takeIf { it.isPublicProfile }?.name
}}")
println()
}
var map = mutableMapOf<Int, MutableList<PersonInfo>>()
fun showAge() {
println("showAge")
for (person in people) {
if (person.age !in map)
map[person.age] = mutableListOf()
map.getValue(person.age) += person
}
println("before:$map")
map = mutableMapOf()
for (person in people) {
map.getOrPut(person.age) { mutableListOf() } += person
}
println("after1:$map")
val map2 = people.groupBy { it.age }
println("after2:$map2")
}
}
var personInfo = arrayListOf<PersonInfo>()
fun setDummyData() {
personInfo = arrayListOf(
PersonInfo(26, true, "박수용"),
PersonInfo(18, false, "김수용"),
PersonInfo(29, true, "이수용"),
PersonInfo(31, false, "최수용"),
PersonInfo(12, true, "명수용")
)
}
fun main() {
setDummyData()
val person = Person()
person.people = personInfo
with(person) {
showCountUnderAge()
showSortedAge()
isPublicProfile()
showAge()
}
}- 연산 순서 변경
만약 연산의 순서를 변경함으로써 다음 연산에서 처리할 원소가 줄어들 수 있는 경우 연산을 변경함으로써 최적화가 가능하다. 이것은 sequence, collection 모두에게 해당될 수 있는 효과이다. 다만, collection의 경우에 2개 이상의 확장 함수를 사용하는 경우 intermediate collection 생성은 피할 수 없다.
References
