Kotlin Weekly # -387 "Kotlin 꼬리 재귀의 최적화"

1월 1주차에는 꼬리 재귀와 최적화방법에 관한 글입니다.

 

https://proandroiddev.com/kotlin-under-the-hood-how-to-get-rid-of-recursion-5a34162e890b

Kotlin under the hood: how to get rid of recursion

 

 

 

소개

이 글은 코틀린에서 재귀를 최적화하는 방법과 'tailrec' 키워드의 구현 방법에 대한 글입니다.

 

 

 

내용

1. Tailrec과 꼬리 재귀

• 꼬리 재귀는 재귀 호출이 함수의 마지막 작업일 때 발생합니다.
• 이런 종류의 재귀는 반복을 통해 효율적으로 최적화됩니다.
  
• tailrec 키워드는 간단한 꼬리 재귀에만 작동합니다.
• 복 잡한 재귀 함수에 tailrec을 사용하면 최적화되지 않습니다.

tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
    return if (n == 0) b else fibonacci(n - 1, a + b, a)
}

 

2. 트리에서의 재귀

• 트리 구조에서 재귀를 사용한 문제를 해결하는 방법입니다.
• 이 방법은 재귀마다 리스트를 생성하고 복사하는 문제가 있습니다.

fun ViewGroup.findViewRecursion(predicate: (View) -> Boolean): List<View> {
    val accumulator = mutableListOf<View>()
    if (predicate(this)) {
        accumulator.add(this)
    }
    children.forEach { child ->
        when {
            child is ViewGroup -> accumulator.addAll(
                child.findViewRecursion(predicate)
            )
            predicate(child) -> accumulator.add(child)
        }
    }
    return accumulator
}

 

3. 트리에서 재귀 최적화

• 큐를 사용하여 재귀를 제거하는 방법입니다.
• 이 방법은 재귀를 사용하지 않고 트리를 순회합니다.

fun ViewGroup.findViewQueue(predicate: (View) -> Boolean): List<View> {
    val accumulator = mutableListOf<View>()
    val queue: Queue<View> = LinkedList()
    queue.add(this) 
    while (queue.isNotEmpty()) {
        val view = queue.poll() 
        if (predicate(view)) {
            accumulator.add(view)
        }
        if (view is ViewGroup) { 
            view.children.forEach { queue.add(it) }
        }
    }
    return accumulator
}

 

4. 반복자와 시퀀스 양보를 사용한 최적화

• 지연된 반복자를 사용하여 트리를 순회하는 방법입니다.

fun ViewGroup.findViewTreeIterator(predicate: (View) -> Boolean): Sequence<View> {
    val treeIterator = TreeIterator(children.iterator()) { view ->
        (view as? ViewGroup)?.children?.iterator() 
    }
    return sequenceOf(this)
        .plus(treeIterator.asSequence())
        .filter { predicate(it) }
}

 

 

5. 성능 비교

 

1. 일반 재귀와 리스트 복사:
   • 이 방법은 3000 레벨의 중첩에서 stackOverflow 를 일으켰습니다.
   • 이는 중첩 레벨이 높을 때 메모리 문제로 인해 비효율적임을 시사합니다.
2. 누산기를 사용한 최적화된 재귀:
   • 이 방법은 5000 레벨의 중첩까지 오류 없이 처리했습니다.
   • 성능 면에서, 최적화된 재귀는 큐 방법보다 두 배 빨랐습니다.
   • 재귀 호출 시 스택을 통한 매개변수 전달이 큐에서 항목을 추가하고 제거하는 것보다 훨씬 빠릅니다.
   • 중첩 레벨이 많지 않은 트리 구조에서는 재귀가 속도 면에서 최선의 선택입니다.
3. 큐를 사용한 최적화:
   • 깊은 중첩 레벨을 가진 계층 구조를 처리할 때 큐를 사용하는 최적화가 속도 면에서 가장 좋은 방법입니다.
   • 그러나 지연된 반복자를 사용한 최적화는 큐와 비슷한 성능을 보이면서 더 유연한 해결책을 제공합니다.
4. 시퀀스의 yield 문:
   • 글쓴이는 시퀀스의 속도와 yield 호출을 통한 지연된 시퀀스 확장의 속도가 낮을 것으로 예상했지만, 실제로는 그 예상보다 훨씬 낮았습니다.
   • yield 문을 사용한 방법은 반복자 솔루션보다 수백 배 느렸습니다.
   • 이는 운영 원리가 비슷함에도 불구하고, 성능 면에서 큰 차이를 보인다는 것을 의미합니다.
5. 정리 :

• 누산기를 사용한 최적화된 재귀: 중첩 레벨이 많지 않고 성능이 중요한 경우에 적합합니다. 메모리 사용량이 제한적이지만, 일반 재귀보다 효율적입니다.
• 큐를 사용한 최적화: 매우 깊은 중첩 레벨을 처리해야 할 때 유용합니다. 이 방법은 스택 오버플로우를 방지하고, 누산기를 사용한 재귀보다 더 깊은 구조를 처리할 수 있습니다.
• 지연된 반복자와 시퀀스 yield: 유연성과 통합성이 중요한 경우, 특히 기존의 데이터 처리 체인에 통합해야 할 때 유리합니다. 그러나 성능 면에서는 다른 방법들에 비해 뒤떨어질 수 있습니다.

 

정리

글쓴이가 말하는 정리 : 결론적으로, 재귀 함수의 최적화는 사용하는 특정 상황과 요구 사항에 따라 다르게 접근해야 합니다. 재귀는 절대적인 악이 아니며, 적절하게 최적화하고 사용할 때 매우 효과적일 수 있습니다. 하지만, 모든 최적화는 실제 성능 테스트를 통해 검증해야 하며, 무엇보다도 코드의 복잡성과 유지보수 가능성을 고려해야 합니다.

 

 

 

 

 

 

 

http://kotlinweekly.net/

** Kotlin Weekly **