[모던 자바] 스트림(Stream)과 게으른 평가

스트림과 게으른 평가

스트림은 데이터 컬렉션을 처리하는 편리한 도구다.

효율적인 구현 및 여러 이유로 Java8 설계자들은 스트림을 조금 특별한 방법으로 java8에 추가했다.

그중 하나로 스트림은 단 한 번만 소비할 수 있다는 제약이 있어서 스트림은 재귀적으로 정의할 수 없다.

자기 정의 스트림

다음 코드처럼 소수 스트림을 계산할 수 있다.

public boolean isPrime(int candidate) {
    int candidateRoot = (int) Math.sqrt((double) candidate);
    return IntStream.rangeClosed(2, candidateRoot)
        .noneMatch(i -> candidate % i == 0);
}

public Stream<Integer> primes(int n) {
    return Stream.iterate(2, i -> i + 1)
        .filter(this::isPrime)
        .limit(n);
}

위 코드를 보면 우선 후보 수(candidate number)로 정확히 나누어 떨어지는지 매번 모든 수를 반복 확인했다.

이론적으로 소수로 나눌 수 있는 모든 수는 제외할 수 있다.

1 단계 : 스트림 숫자 얻기

IntStream.iterate 메서드를 이용하면 2에서 시작하는 무한 숫자 스트림을 생성할 수 있다.

public IntStream numbers() {
    return IntStream.iterate(2, n -> n + 1);
}

2 단계 : 머리 획득

IntStream은 첫 번째 요소를 반환하는 findFirst라는 메서드를 제공한다.

public int head(IntStream numbers) {
    return numbers.findFirst().getAsInt();
}

3 단계 : 꼬리 필터링

스트림의 꼬리를 얻는 메서드를 정의한다.

public IntStream tail(IntStream numbers) {
    return numbers.skip(1);
}

다음처럼 획득한 머리로 숫자를 필터링할 수 있다.

IntStream numbers = numbers();
int head = head(numbers);
IntStream filtered = tail(numbers).filter(n -> (n & head) != 0);

4 단계 : 재귀적으로 소수 스트림 생성

반복적으로 머리를 얻어서 스트림을 필터링한다.

public IntStream primes(IntStream numbers) {
    int head = head(numbers);
    return IntStream.concat(
        IntStream.of(head),
        primes(tail(numbers).filter(n -> n % head != 0))
    );
}

게으른 평가

만약 4단계 코드르 실행하면 IllegalStateException이 발생할 것이다.

위 코드에서는 호출하면 스트림이 완전 소비되는 두 개의 최종 연산 findFirst와 skip을 사용했기 때문이다.

그리고 IntStream.concat은 두 개의 스트림 인스턴스를 인수로 받는데, 두 번째 인수가 primes를 직접 재귀적으로 호출하면서 무한 재귀에 빠진다.

 

"재귀적 정의 허용하지 않음"같은 Java8의 스트림 규칙은 우리에게 아무 해도 끼치지 않으며 오히려 이 규칙 덕분에 데이터베이스 같은 질의를 표현하고 병렬화 할 수 있는 능력을 얻을 수 있다.

그래서 Java8 설계자는 이 같은 제한을 두기로 결정했다. 

 

결론적으로 concat의 두 번째 인수에서 primes를 게으르게 평가하는 방식으로 문제를 해결할 수 있다.

좀 더 기술적인 프로그래밍 언어의 용어로는 게으른 평가(lazy evaluation)를 비 엄격한 평가(nonstrict evaluation) 또는 이름에 의한 호출(call by name)이라 한다.

 

즉, 스트림에 최종 연산을 적용해서 실제 계산을 해야 하는 상황에서만 실제 연산이 이루어진다.

특히 스트림에 여러 연산을 적용할 때 이와 같은 특정을 활용할 수 있다. 

게으른 특성 때문에 각 연산별로 스트림을 탐색할 필요 없이 한 번에 여러 연산을 처리할 수 있다.

 

Supplier<T>를 이용해서 게으른 리스트를 만들면 꼬리가 모두 메모리에 존재하지 않게 할 수 있다.

Supplier<T>로 리스트의 다음 노드를 생성할 것이다. 

interface MyList<T> {
    T head();
    MyList<T> tail();
    default boolean isEmpty() {
        return true;
    }
}

class LazyList<T> implements MyList<T> {
    final T head;
    final Supplier<MyList<T>> tail;

    public LazyList(T head, Supplier<MyList<T>> tail) {
        this.head = head;
        this.tail = tail;
    }

    @Override
    public T head() {
        return head;
    }

    @Override
    public MyList<T> tail() {
        return tail.get();
    }
    
    public boolean isEmpty() {
        return false;
    }
}

이제 연속적인 숫자의 다음 요소를 만드는 LazyList의 생성자에 tail 인수로 Supplier를 전달하는 방식으로 n으로 시작하는 무한히 게으른 리스트를 만들 수 있다.

public LazyList<Integer> from(int n) {
    return new LazyList<>(n, () -> from(n + 1));
}

LazyList<Integer> numbers = from(2);
        
int two = numbers.head();
System.out.println("two : " + two);

int three = numbers.tail().head();
System.out.println("three : " + three);

int four = numbers.tail().tail().head();
System.out.println("four : " + four);

실행 결과

만약 요청했을 때 코드가 실행되는 것이 아니라 2부터 시작해서 모든 수를 미리 계산하려 한다면 프로그램은 영원히 종료되지 않을 것이다.

 

그럼 위에 구현한 LazyList를 활용해서 게으른 소수 리스트를 생성해보자.

우선 LazyList에 요소들을 필터링할 filter 메서드를 구현(게으른 필터 구현)하고 적용해보자.

class LazyList<T> implements MyList<T> {
	
    ...
    
    public MyList<T> filter(Predicate<T> p) {
        return isEmpty() ? this : p.test(head()) ?
            new LazyList<>(head(), () -> tail().filter(p)) :
            tail().filter(p);
    }
    
    ...
}

public MyList<Integer> primes(MyList<Integer> numbers) {
    return new LazyList<>(numbers.head(),
        () -> primes(numbers.tail().filter(n -> n % numbers.head() != 0)));
}

tail과 head 호출을 연결해서 처음 세 개의 소수를 계산할 수 있다.

LazyList<Integer> numbers = from(2);

int two = primes(numbers).head();
System.out.println("two : " + two);

int three = primes(numbers).tail().head();
System.out.println("three : " + three);

int five = primes(numbers).tail().tail().head();
System.out.println("five : " + five);

실행 결과

이로써 함수를 자료구조 내부로 추가할 수 있고, 이런 함수는 자료구조를 만드는 시점이 아니라 요청 시점에 실행된다는 사실도 확인했다. 또한 게으른 리스트는 Java8의 스트림과의 연결고리를 제공한다.

 

하지만 자료구조의 10퍼센트 미만의 데이터만 활용하는 상황에서는 게으른 실행으로 인한 오버헤드가 더 커질 수 있다.

게으른 리스트가 게으르진 않을 수 있다는 말이다.

 

위 예제로 예를 들면 LazyList값을 탐색할 때 10번째 항목까지는 모든 노드를 두 번 생성하므로 10개가 아니라 20개의 노드가 생성되는데 이 작업은 게으르게 처리할 수 없고, LazyList 탐색을 요청할 때마다 tail의 Supplier가 반복적으로 호출된다는 점이 문제다.

처음 탐색 요청을 호출할 때만 tail의 Supplier가 호출되도록 하여(그리고 결과값을 캐시 해서) 이 문제를 해결할 수 있다.

LazyList에 private Optional<LazyList<T>> alreadyComputed 필드를 추가하고 tail 메서드가 적절하게 리스트를 업데이트하도록 정리할 수 있다.

 

게으른 자료구조는 강력한 프로그래밍 도구이다.

애플리케이션을 구현하는 데 도움을 준다면 게으른 자료구조를 사용하되, 게으른 자료구조 때문에 효율성이 떨어진다면 전통적인 방식으로 코드를 구현해야 할 것이다.