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
Is recursion always evil? Let’s look at various recursion optimization methods and measure them.
proandroiddev.com
소개
이 글은 코틀린에서 재귀를 최적화하는 방법과 '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. 성능 비교
- 일반 재귀와 리스트 복사:
- 이 방법은 3000 레벨의 중첩에서 stackOverflow 를 일으켰습니다.
- 이는 중첩 레벨이 높을 때 메모리 문제로 인해 비효율적임을 시사합니다.
- 누산기를 사용한 최적화된 재귀:
- 이 방법은 5000 레벨의 중첩까지 오류 없이 처리했습니다.
- 성능 면에서, 최적화된 재귀는 큐 방법보다 두 배 빨랐습니다.
- 재귀 호출 시 스택을 통한 매개변수 전달이 큐에서 항목을 추가하고 제거하는 것보다 훨씬 빠릅니다.
- 중첩 레벨이 많지 않은 트리 구조에서는 재귀가 속도 면에서 최선의 선택입니다.
- 큐를 사용한 최적화:
- 깊은 중첩 레벨을 가진 계층 구조를 처리할 때 큐를 사용하는 최적화가 속도 면에서 가장 좋은 방법입니다.
- 그러나 지연된 반복자를 사용한 최적화는 큐와 비슷한 성능을 보이면서 더 유연한 해결책을 제공합니다.
- 시퀀스의 yield 문:
- 글쓴이는 시퀀스의 속도와 yield 호출을 통한 지연된 시퀀스 확장의 속도가 낮을 것으로 예상했지만, 실제로는 그 예상보다 훨씬 낮았습니다.
- yield 문을 사용한 방법은 반복자 솔루션보다 수백 배 느렸습니다.
- 이는 운영 원리가 비슷함에도 불구하고, 성능 면에서 큰 차이를 보인다는 것을 의미합니다.
- 정리 :
- 누산기를 사용한 최적화된 재귀: 중첩 레벨이 많지 않고 성능이 중요한 경우에 적합합니다. 메모리 사용량이 제한적이지만, 일반 재귀보다 효율적입니다.
- 큐를 사용한 최적화: 매우 깊은 중첩 레벨을 처리해야 할 때 유용합니다. 이 방법은 스택 오버플로우를 방지하고, 누산기를 사용한 재귀보다 더 깊은 구조를 처리할 수 있습니다.
- 지연된 반복자와 시퀀스 yield: 유연성과 통합성이 중요한 경우, 특히 기존의 데이터 처리 체인에 통합해야 할 때 유리합니다. 그러나 성능 면에서는 다른 방법들에 비해 뒤떨어질 수 있습니다.
정리
글쓴이가 말하는 정리 : 결론적으로, 재귀 함수의 최적화는 사용하는 특정 상황과 요구 사항에 따라 다르게 접근해야 합니다. 재귀는 절대적인 악이 아니며, 적절하게 최적화하고 사용할 때 매우 효과적일 수 있습니다. 하지만, 모든 최적화는 실제 성능 테스트를 통해 검증해야 하며, 무엇보다도 코드의 복잡성과 유지보수 가능성을 고려해야 합니다.
** Kotlin Weekly **
kotlinweekly.net
'Kotlin Weekly' 카테고리의 다른 글
Kotlin Weekly # -388 "Gemini를 이용한 Chating" (0) | 2024.01.08 |
---|---|
Kotlin Weekly # -386 "Koin 2023: 성장과 미래 계획 " (0) | 2023.12.25 |
Kotlin Weekly # -385 "Kotlin Compiler Plugins" (0) | 2023.12.18 |
Kotlin Weekly # -384 "Jetpack Compose의 Modifiers" (0) | 2023.12.13 |
Kotlin Weekly # -383 "Kotlin 사용 주의점" (0) | 2023.12.13 |