[Kotlin] lazy(지연) 컬렉션 연산, sequence(시퀀스)

Kotlin in Action 을 공부하고 Effective kotlin 의 내용을 조금 참조하여 정리한 글입니다.

 

이미지 출처               https://commons.wikimedia.org/wiki/File:Kotlin_Icon.svg

 

이전 글에서 몇가지 컬렉션 함수를 살펴보았다.

그 함수들은 결과 컬렉션을 eagerly(즉시) 생성한다.

즉, '컬렉션 함수를 연쇄하면, 매 단계마다 연산의 중간 결과를 새로운 컬렉션에 임시로 담는다'는 의미이다.

 

컬렉션 함수 연쇄 (시퀀스 사용 X)

data class Person(val name: String, val age: Int)

people.map(Person::name).filter { it.startsWith('A') }

(`people` 은 `List<Person>` 이다.)

`filter` 와 `map` 은 리스트를 리턴한다.

즉, 위 코드에서는 두 함수를 연쇄 호출하여 리스트를 두 개 만든다.

한 리스트는 `filter` 의, 다른 한 리스트는 `map` 의 결과를 담는다.

만약 `people` 이 원소가 굉장히 많다면 연산이 필요없는 중간 결과 리스트를 생성하는 것은 효율이 떨어진다.

Sequence(시퀀스)

반면에, `Sequence`(시퀀스)를 사용하면 중간 임시 컬렉션을 사용하지 않고도 컬렉션 연산을 연쇄할 수 있다.

 

컬렉션 함수 연쇄 (시퀀스 사용)

people.asSequence() // 원본 컬렉션을 시퀀스로 변환
    .map(Person::name) 
    .filter { it.startsWith('A') } // 시퀀스도 컬렉션과 똑같은 API 제공
    .toList() // 결과 시퀀스를 다시 리스트로 변환

위에서의 두 코드의 연산을 수행 결과는 같다.

시퀀스를 사용한 코드에서는 중간 결과를 저장하지 않기 때문에 원소가 많은 경우 성능이 굉장히 좋아진다.

`people` 을 100개의 `Person` 을 원소로 가지는 List 로 만들어서 두 함수를 테스트해보면,

시퀀스를 사용한 경우 그렇지 않은 경우보다 약 2배의 성능 차이가 난다.

 

코틀린 lazy(지연) 연산 시퀀스는 `Sequence` 인터페이스에서 시작한다.

Sequence 인터페이스

public interface Sequence<out T> {
    public operator fun iterator(): Iterator<T>
}

 코틀린의 `Sequence`(시퀀스)는 lazy evaluation(지연 연산)을 기반으로 하는 데이터 스트림이다.

지연 연산은 필요할 때까지 연산을 미루고 값이 요구될 때만 연산이 수행된다는 의미이다.

그래서 시퀀스는 무한할 수 있게 되며(아래 무한 시퀀스 설명 참조), 메모리 효율성이 높아진다.

 

시퀀스에 대해 `map`, `filter` 등의 연산을 수행해도 이러한 지연 연산을 보존된다.(대부분)

즉, 결과 시퀀스의 원소들이 즉시 연산되어 리턴되는 게 아니라, 실제로 원소들이 필요할 때 연산이 수행된다.

(특정 시퀀스 연산들에 대해서는 이러한 지연 연산을 하지 않는 것들도 있다. 이는 코틀린 문서에 명시되어 있다.)

 

`Sequence` 안에 있는 `iterator` 라는 메서드를 통해 시퀀스로부터 원소 값을 얻을 수 있다.

 

시퀀스 처리 함수를 사용하면, 데코레이터 패턴으로 꾸며진 새로운 시퀀스가 리턴된다. 

만약 `Sequence` 에 대한 filter 확장함수를 사용하면, 

그 즉시 연산이 이뤄지지 않고, `FilteringSequence@...` 와 같은 형태의 데코레이터가 설치된다.

다른 `Sequence` 에 대한 확장함수들도 마찬가지이다.

(아래 generateSequence 함수 의 자연수의 시퀀스를 생성하고 사용하기에서 이를 보여준다.)

asSequence 확장 함수

public fun <T> Iterable<T>.asSequence(): Sequence<T> {
    return Sequence { this.iterator() }
}

`asSequence` 확장 함수를 호출하여 어떤 컬렉션이든 시퀀스로 바꿀 수 있다. 

큰 컬렉션에 대해 연산을 연쇄할 때는 시퀀스를 사용하는 것을 컨벤션으로 삼자.
여러 처리 단계를 사용해야 하는 컬렉션 처리에서는 시퀀스를 사용하는 것을 컨벤션으로 삼자.
시퀀스를 사용하지 않는 것이 효율적인 경우도 드물게 있는데 이는 아래에서 설명한다.

시퀀스에 대한 연산은 지연 연산되기 때문에 실제 연산이 실행되게 하려면,

최종 시퀀스의 원소를 하나씩 `iteration` 하거나 최종 시퀀스를 리스트로 변환해야 한다.

시퀀스 연산 실행

시퀀스에 대한 연산은 intermediate(중간) 연산과 terminal(최종) 연산으로 나뉜다.

중간 연산은 항상 지연 연산된다.

 

최종 연산이 없는 `justSequence` 함수

fun justSequence(): Sequence<Int> = listOf(1, 2, 3, 4).asSequence()
    .map {
        println("map($it)")
        it * it
    }.filter {
        println("filter($it)")
        it % 2 == 0
    }

@Test
fun testJustSequence() = assert(justSequence() is Sequence)

테스트는 통과되지만, 어떠한 내용도 출력되지 않는다.

`map` 과 `filter` 변환이 지연되어서 결과를 얻을 필요가 있을 때(최종 연산이 호출될 때) 적용된다는 뜻이다.

 

최종 연산을 포함한 테스트

@Test
fun testSequenceToList() = assert(justSequence().toList() is List)
// print
/*
map(1)
filter(1)
map(2)
filter(4)
map(3)
filter(9)
map(4)
filter(16)
*/

이렇게 `List` 로 변환하니, 지연되었던 모든 연산이 수행된다.

eagerly(즉시) 연산을 수행한다면, 리스트의 모든 원소에 대해 먼저 `map` 을 수행한 후에,

그 결과에 대해 `filter` 를 수행할 것이다.

 

하지만 시퀀스를 사용하면 다르게 작동한다. 

모든 연산은 각 원소에 대해 순차적으로 적용된다.

아래 코드와 그림을 보면 이해하기 편하다.

 

`map` 으로 각 숫자를 제곱하고, 제곱한 숫자 중 `find` 로 3보다 큰 첫 원소 찾기

assert(
    listOf(1, 2, 3, 4).asSequence()
        .map { it * it }.find { it > 3 } == 4
)

• 지연 연산에서는
  1. 최초 시퀀스에서 1 을 가져와서 제곱을 한 후, `find` 연산을 한다.
  2. 제곱한 수는 1, 이는 3보다 작아서 predicate 를 만족하지 않는다.
  3. 최초 시퀀스에서 두 번째 원소 2에 대해서 제곱을 한 후, find 연산을 한다.
  4. 제곱한 수는 4, 이는 3보다 커서 predicate 를 만족한다.
  5. `find` 의 결과를 찾았으므로 최초 시퀀스에서 3, 4 에 대한 연산을 수행하지 않는다.
• 즉시 연산에서는
  1. 최초 리스트에서 1,2,3,4 에 대해 모두 제곱을 한다.
  2. 그 결과 중간 컬렉션(리스트) {1, 4, 9, 16} 이 생긴다.
  3. 중간 컬렉션에 대해서 `find` 연산을 한다.
  4. 4 가 predicate 를 만족하는 원소이므로 4를 리턴한다.

이렇게 시퀀스를 사용하면, 원소에 연산을 차례대로 적용하다가 결과가 얻어지면 그 이후 원소에 대해서는 변환이 이루어지지 않을 수도 있다. 

이렇게 시퀀스를 사용하여 연산에 대해 이득을 볼 수 있다.

 

지연 연산, 시퀀스 처리는 요소 하나하나에 지정한 연산을 한꺼번에 적용한다. 

이를 lazy order, element-by-element order 라고 부른다.

 

반면, 즉시 연산, 컬렉션 처리 함수는 요소 전체를 대상으로 연산을 한 단계씩 적용한다.

이를 eager order, step-by-step order 라고 부른다.

 

컬렉션 처리 함수를 사용하지 않고 고전적인 반복문과 조건문을 활용해서 아래처럼 코드를 구현한다면,

이는 시퀀스 처리인 element-by-element order 와 같다.

fun classicStatement() {
    for (e in listOf(1, 2, 3)) {
        print("F$e, ")
        if (e % 2 == 1) {
            print("M$e, ")
            val mapped = e * 2
            print("E$mapped, ")
        }
    }
}

@Test fun testClassicStatement() = classicStatement()
// print
/* F1, M1, E2, F2, F3, M3, E6, */

 

컬렉션 연산 순서의 중요성

컬렉션에 대해 수행하는 연산의 순서도 성능에 영향을 끼친다.

그에 대한 예를 하나 보자.

 

`Collection<Person>` 에서 어떤 길이보다 이름이 짧은 사람의 명단

private val people = listOf(Person("Alice", 29), Person("Bob", 31), Person("Carles", 32), Person("Dan", 2131))

people.asSequence().map(Person::name)
    	.filter { it.length < 4 }.toList() == listOf("Bob", "Dan")

people.asSequence().filter { it.name.length < 4 }
	    .map(Person::name).toList() == listOf("Bob", "Dan")

이번에는 마지막 연산이 `find` 가 아닌, `filter` 혹은 `map` 이다. 그래서 모든 원소를 검사해야 한다.

`map` 을 먼저 수행하면, 모든 원소를 변환한다.

하지만 `filter` 를 먼저 수행하면, 부적절한 원소를 먼저 제외하기 때문에 그런 원소는 변환되지 않는다.

코틀린 시퀀스는 자바 8 스트림과 매우 비슷하다.
그런데 코틀린 시퀀스에 비해 자바 8 스트림이 가지는 이점이 있다.
자바 8 스트림에서는 스트림 연산을 여러 CPU 에서 병렬적으로 실행하는 기능(`parallelStream`)이 있다.
코틀린 언어에서도 자바 8 스트림을 사용할 수 있기 때문에 목적에 맞게 사용하면 된다.

시퀀스 만들기

컬렉션에 대해 `asSequence` 를 호출하여 시퀀스를 만드는 것 말고도 다른 방법이 있다.

무한 시퀀스

시퀀스는 최종 연산이 일어나기 전까지 컬렉션 연산을 하지 않는다고 했다. 

따라서 무한 시퀀스(infinite sequence)를 만들고 필요한 부분까지만 값을 추출하는 것도 가능하다.

 

무한 시퀀스를 만드는 일반적인 방법은 `generateSequence`  또는 `sequence` 를 사용하는 것이다.

generateSequence 함수

public fun <T : Any> generateSequence(seed: T?, nextFunction: (T) -> T?): Sequence<T> =
    if (seed == null)
        EmptySequence
    else
        GeneratorSequence({ seed }, nextFunction)

이 함수는 초기값 `seed` 와 한 iteration 마다 이전 원소를 기반으로 다음 원소를 계산하는 데 사용되는 `nextFunction`  로 정의된 시퀀스를 리턴한다.

첫 null 값을 만날 때까지 값을 만들어낸다.

`generateSequence` 함수를 사용하는 예제 코드를 보자.

 

자연수 중 2로 나누어 떨어지는 수를 구하는데 10개만 연산하여 출력하기

generateSequence(1) { it + 1 }
        .map { it * 2 }
        .take(10) // 10개를 계산한다
        .forEach { print("$it, ") }

// print
/* 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 */

`take(10)` 를 사용하여 무한 시퀀스의 결과 중 10개만 계산하도록 하고 있다.

 

자연수의 시퀀스를 생성하고 사용하기

val naturalNumbers = generateSequence(0) { it + 1 } // 시퀀스
val numbersTo100 = naturalNumbers.takeWhile { it <= 100 } // 시퀀스
assert(numbersTo100.sum() == 5050) // sum 이 최종 연산

 0부터 100까지의 자연수의 합을 구하는 프로그램이다.

위 이미지를 보면 `GeneratorSequence@...`, `TakeWhileSequence@...` 가 생기는 것을 볼 수 있다.

데코레이터 패턴으로 감싸진(꾸며진) 새로운 시퀀스가 생기는 것이다.

 

상위 디렉토리의 시퀀스를 생성하고 사용하기

fun File.isInsideHiddenDirectory() = generateSequence(this) { it.parentFile }.any { it.isHidden }

@Test fun findHiddenFileInParentDir() {
    val file = File("/Users/sh1mj1/.HiddenDir/a.txt")
    assertTrue(file.isInsideHiddenDirectory())
}

어떤 파일의 상위 디렉토리를 뒤지면서 Hidden(숨김) 속성을 가진 디렉토리 안에 파일이 있는지 검사하는 프로그램이다.

여기서도 첫번째 원소를 지정하고, 시퀀스의 한 원소로부터 다음 원소를 계산하는 방법을 제공하여 시퀀스를 만든다.

이렇게 시퀀스를 사용하면, 조건을 만족하는 디렉토리를 찾은 뒤에는 더 이상 상위 디렉토리를 뒤지지 않는다.

sequence 함수

`sequence` 는 중단 함수(suspending function, 코루틴)로 원소들을 지정한다.

시퀀스 빌더는 중단 함수 내부에서 `yield` 로 값을 하나씩 만들어 낸다.

`yield` 함수는 빌드된 iterator 에 값을 만들어 주고, 다음 값이 요청될 때까지 suspend(일시 중지)하는 suspend 함수이다.

 

피보나치 수열을 만드는 무한 시퀀스

val fibonacciInfiniteSequence = sequence {
    yield(1)
    var current = 1
    var prev = 1
    while (true) {
        yield(current)
        val temp = prev
        prev = current
        current += temp
    }
}

println(fibonacciInfiniteSequence.take(10).toList())
// print 
/* [1, 1, 2, 3, 5, 8, 13, 21, 34, 55] */

이렇게 무한 시퀀스를 실제로 사용할 때는 값을 몇 개 활용할지 지정해야 한다.

그렇지 않으면 무한히 반복한다.

fibonacciInfiniteSequence.toList()  // 종료되지 않고 무한히 반복됨

그러므로 위 코드처럼 `take` 를 사용해서 활용할 값의 수를 지정하거나,

`first`,`find`,`any`,`all`,`none`,`indexOf` 와 같은 일부 요소만 선택하는 종결 연산을 활용해야 한다.

무한 시퀀스는 종결 연산으로 `take` 와 `first` 정도만 사용하는 것이 좋다.

(`any` 가 true 를, `all` 과 `none` 이 false 를 리턴하지 못하면, 무한 반복에 빠진다.)

시퀀스가 빠르지 않는 경우

• 컬렉션 전체를 기반으로 처리해야 하는 연산은 시퀀스를 사용해도 빨라지지 않는다.

코틀린 stdlib 의 `sorted` 가 그러한 예이다.

`Sequence` 에 대한 확장함수 `sorted` 는 `Sequence` 를 `List` 로 변환한 뒤에 자바 stdlib 의 `sort` 를 사용하여 처리한다.

이러한 변환 때문에 시퀀스가 일반 컬렉션 처리보다 느려진다.

• 무한 시퀀스에 `sorted` 를 적용하지 말자.

무한 시퀀스처럼 시퀀스의 다음 요소를 lazy 하게 구하는 시퀀스에 `sorted` 를 적용하면, 무한 반복에 빠지는 문제가 있다.

generateSequence(0) { it + 1 }.sorted().take(10).toList() // 종료되지 않고 무한 반복

generateSequence(0) { it + 1 }.take(10).sorted().toList() // 정상 동작

 

또한 다른 경우도 있다.

• 작은 컬렉션의 컬렉션 처리를 한 단계만 할 때는 시퀀스가 더 느리다.

컬렉션 처리를 한 단계만 한다는 것은 컬렉션 처리 함수를 한 번만 사용한다는 의미이다.

 

리스트를 컬렉션 처리 vs 시퀀스로 변환하여 처리

fun singleStepListPrecessing(): List<Person> = people.filter { it.age > 30 }
fun singleStepSequenceProcessing(): List<Person> = people.asSequence().filter { it.age >= 30 }.toList()

시퀀스는 람다를 저장해야 하므로 람다를 `inline`(인라인)하지 않는다. 

반면에 `Iterable` 의 `filter` 는 람다를 인라인한다.

public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {
    return FilteringSequence(this, true, predicate)
}
public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
    return filterTo(ArrayList<T>(), predicate)
}

즉, 크기가 작은 컬렉션의 처리 단계가 한 단계인 경우에는 오히려 시퀀스를 사용하는 것이 더 느리다.

 

인라인에 대해서는 다른 글에서 자세히 설명할 것이니 일단은 이렇게만 알아두자.