LazyList 및 메모이제이션

“Progress isn't made by early risers. It's made by lazy men trying to find easier ways to do something.” ― Robert Heinlein

Scala(및 기타 함수형 프로그래밍 언어)가 명령형 언어에 비해 갖는 이점 중 하나는 지연 평가의 개념입니다. 게으른 평가는 전체 계산을 평가하지 않고 필요할 때만 절대적으로 필요한 것을 계산합니다.

Scala 2.13에 도입된 LazyList (2.12 이하의 경우 Stream 참조)는 느리게 평가되는 변경 불가능한 연결 목록 구현입니다. 요소는 필요한 만큼만 계산됩니다.

0에서 무한대까지의 목록을 고려하십시오. 일반 목록을 사용하면 완전히 평가되어야 하고 절대 종료되지 않기 때문에 이것을 선언할 수 없습니다. 그러나 LazyList를 사용하면 다음과 같이 말할 수 있습니다.

val list = LazyList.from(0)
val list: scala.collection.immutable.LazyList[Int] = LazyList(<not computed>)

이 목록은 평가되지 않았습니다. 직관적으로 우리는 이 목록이 비어 있지 않다는 것을 알고 있지만, 알아내려고 하면

val empty = list.isEmpty
val empty: Boolean = false

list
val res1: scala.collection.immutable.LazyList[Int] = LazyList(0, <not computed>)

따라서 목록이 비어 있는지 확인하려면 헤드를 계산해야 했습니다. 그리고 일단 계산되면 이제 구체적인(불변의) 값을 갖게 됩니다. 머리를 가져오려는 추가 시도는 지금 계산된 값을 반환합니다.

메모이제이션으로 알려진 LazyList의 이 속성은 매우 유용하며 왜 고전적인 재귀 예제인 피보나치 수 계산을 살펴보겠습니다.

피보나치

Scala에서 재귀적으로 사용되는 고전적인 피보나치 함수를 고려하십시오.

def fib(n: Int): BigInt = {
  if (n == 1) 0
  else if (n == 2) 1
  else fib(n - 1) + fib(n - 2)
}

이 다양한 간단한 구현에는 2개의 기본 사례가 있으며, 기본 사례에 도달할 때까지 내림차순으로 피보나치를 계산하는 재귀 호출이 있습니다. 그러나 이 순진한 구현에는 큰 문제가 있습니다. fib(n)을 계산하면 fib(n-1) 및 fib(n-2)가 호출됩니다. 차례로 이들은 fib(n-2) , fib(n-3) , fib(n-3) , fib(n-4) 등에 대한 호출을 생성합니다. 우리가 몇 가지 수준에 도달할 때까지 동일한 값을 반복해서 계산하게 됩니다. 내 Macbook Air에서 위의 함수를 실행하여 fib(40)를 계산하는 데 약 4초가 걸리며 fib(50)는 거의 1분이 걸립니다. 종료를 기다릴 인내심이 있는 경우 테일이 아닌 재귀 호출이 많고 스택 오버플로의 가능성이 있다는 점을 추가하십시오.
분명히 그 모든 것은 상대적으로 간단한 문제에 대한 문제입니다.
메모 입력 및 LazyList
LazyList에 대한 Scala 문서는 fib의 멋진 한 줄 구현을 다음과 같이 제공합니다.

val fibs: LazyList[BigInt] =  BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map{ n => n._1 + n._2 }

위치 0과 1의 기본 값이 LazyList cons 연산자#::로 채워진 것을 볼 수 있습니다. 그런 다음 모든 fib를 fibs.tail로 압축하여 후속 값을 계산하고 다음 fib 번호는 이 둘의 합계입니다. 느리게 평가되기 때문에 끝없이 긴 시퀀스를 꼬리로 압축할 수 있습니다. 메모이제이션은 주어진 위치의 구체적인 값이 한 번만 계산되도록 합니다.
이것을 사용하여 fib 번호 100,000이 20,000자리라는 것을 몇 초 안에 계산할 수 있었습니다. 멋진.

fibs.take(100000).lastOption.foreach(n => println(n.toString.length))
> 20899

그러나 이 중 어느 것도 무료로 제공되지 않으며 평소와 같이 트레이드 오프는 메모리 공간에 있습니다. 위의 예에서 크기가 100,000인 연결 목록은 메모리에 있어야 하며 범위( val fibs )에 헤드에 대한 참조가 있는 동안 계속 그렇게 합니다.

경쟁 프로그래밍을 시도하거나 TopCoder 또는 Hackerrank와 같은 평가 사이트를 사용하는 경우 동적 프로그래밍(DP)을 접하게 될 것입니다. 메모이제이션은 많은 자동 평가 평가를 통해 얻을 수 있는 DP 기술이며, 그 이유만으로도 배울 가치가 있습니다. 또한 오래된 문제를 보는 새로운 방법을 제공하며 이는 항상 가치가 있습니다.