[함수형사고] 4. 열심히 보다는 현명하게

패러다임을 바꾸면 더 적은 노력으로 더 많은 일을 할 수 있는 득을 보게 된다. 함수형 프로그래밍에서 나타나는 많은 구조들이 그렇다. 흔히 볼 수 있는 문제들을 구현할 때 짜증나던 것들을 제거해준다.

이 장에서는 메모이제이션과 게으름 설명을 보자.

4.1 메모이제이션

메모이제이션은 다음과같은 상황에서 유용하다. 시간이 많이 걸리는 연산을 반복적으로 사용해야 한다는 가정 주어진 매개변수를 사용하여 연산을 할 때마다 그값을 매개변수를 키 값으로 하는 캐시에 저장한다. 후에 이 함수가 같은 매개변수로 호출되면 다시 연산하는 대신에 캐시의 값을 리턴한다. 함수 캐싱은 전형적인 컴퓨터과학의 트레이드오프이다. 이 방법은 좋은 성능을 위해서 메모리를 더 많이 사용한다.

캐싱 방법이 제대로 작동하려면 함수가 순수해야 한다. 순수함수란 부수효과가 없는 함수를 말한다. 가변 클래스 필드를 참조하지 않고, 리턴 값외에는 아무 값도 쓰지 않아야 하며, 주어진 매개변수에만 의존해야 한다. java.lang.Math의 모든 메소드가 순수함수의 좋은 예이다. 물론, 주어진 매개변수에 대해 항상 같은 값을 리턴하는 함수에 한해서만 캐시된 값을 재사용할 수 있다.

캐싱

캐싱은 흔한 요구사항이자 찾기 어려운 오류의 근원이다. 이 절에서는 캐싱용레를 살펴보자.

메서드 레벨에서의 캐싱

이번 장에서 자연수 분류 문제를 해법을 그려나가는 캔버스처럼 사용하였다. Classifier클래스는 자연수를 분류한다. 분류를 위해 같은 수를 이 클래스의 여러 메서드에 주는 일이 다반사이다. 예를 들어 다음의 코드를 보자,

if(Classifier.isPerfect(n)) print “i” else if(Classifier.isAbundant(n)) print “+” else if(Classifier.isDeficient(n)) print “-“

이렇게 구현한 경우, 모든 분류 메서드를 호출할 때마다 매개변수의 합을 계산해야 한다. 이것이 클래스 내부 캐싱의 예이다. 이 경우 sumOfFactors()가 각각의 수에 대해 여러번 호출된다. 이렇게 자주 사용된다면 이는 상당히 비효울적인 접근 방법이다.

합산 결과를 캐싱하기.

이미 수행된 결과를 재사용하는 것이 코드를 효율적으로 만드는 한 방법이다. 매개변수의 합을 구하는 것이 어렵기 때문에 각 수마다 한 번만 계산하고자 한다. 그러기 위해서 다음과 같은 코드로 계산 결과를 저장할 캐시를 만들어야 한다.

class ClassifierCacheSum {
  private sumCache = [:]

  def sumOfFactors(number) {
    if(! sumCache.containsKey(number)){
      sumCache[number] = factorsOf(number).sum()
    }
    return sumCache[number]
  }
}

게으름

표현의 평가를 가능한 최대로 늦추는 기법인 게으른 평가는 함수형 프로그래밍에서 많이 사용된다. 게으른 컬렉션은 그 요소들을 한꺼번에 미리 연산하는 것이 나니라, 필요에 따라 하나씩 전달해준다. 이렇게 몃 가지 이점이 있다. 우선 시간이 많이 걸리는 연산을 반드시 필요할 때까지 미룰 수 있다. 둘째로, 요청이 계속되는 한 요소를 계속 전달하는 무한 컬렉션을 만들 수 있다. 셋쨰로, 맵이나 필터 같은 함수형 개념을 게으르게 사용하면 효율이 높은 코드를 만들 수 있다. 자바는 버전 8 이전까지는 게으름을 지원하지 않았지만 몃몃 프레임워크나 파생 언어는 지원한다.

자바의 게으른 반복자

게으름을 만들려면 자료구조부터 그 개념을 지원하야 한다. 예를 위해 소수(자기 자신과 1로만 나뉘는 수)를 구현해보자

package com.nealford.ft.primes;

import java.util.HashSet;
import java.util.Set;

import static java.lang.Math.sqrt;

public class Prime {

    public static boolean isFactor(final int potential, final int number) {
        return number % potential == 0;
    }

    public static Set<Integer> getFactors(final int number) {
        Set<Integer> factors = new HashSet<>();
        factors.add(1);
        factors.add(number);
        for (int i = 2; i < sqrt(number) + 1; i++)
            if (isFactor(i, number)) {
                factors.add(i);
                factors.add(number / i);
            }
        return factors;
    }

    public static int sumFactors(final int number) {
        int sum = 0;
        for (int i : getFactors(number))
            sum += i;
        return sum;
    }

    public static boolean isPrime(final int number) {
        return sumFactors(number) == number + 1;
    }

    public static Integer nextPrimeFrom(final int lastPrime) {
        int candidate = lastPrime + 1;
        while (!isPrime(candidate)) candidate++;
        return candidate;
    }

}

이걸 자바의 반복자(iterator)를 활용해보면~

package com.nealford.ft.primes;

import java.util.Iterator;

public class PrimeIterator implements Iterator<Integer> {
    private int lastPrime = 1;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public Integer next() {
        return lastPrime = Prime.nextPrimeFrom(lastPrime);
    }

    @Override
    public void remove() {
        throw new RuntimeException("Fundamental nature of the universe exception!");
    }
}