[Javascript] Lazy evaluation(지연 평가)

컴퓨터 프로그래밍에서 Lazy evaluation은 계산의 결과 값이 필요할 때까지 계산을 늦추는 기법. Javascript에서는 배열 데이터 구조를 많이 쓰는데, 연산의 성능을 끌어올리기 위해 필요한 기법 중 하나이다.

예시

1. 엄격한 평가

Array(100000).fill().map((v, i) => i)
  .map((v) => v + 1)
  .filter((v) => v % 3 === 0)
  .slice(0, 10);
  
  //[ 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 ]

• 0부터 10만까지의 숫자가 담긴 배열 각각의 요소에 1씩을 더해서 3의 배수가 되는 숫자 10개만 추리는 코드.
• map에서 10만 filter에서 10만 slice에서 10해서 총 200010번의 연산을 해야한다.
• 최종숫자 10개를 선발하기 위해선 앞에서부터 차례대로 30개만 검사하고 끝낼 수 있지만, 컴퓨터는 작업을 순차적으로 수행하기 때문.

2. 지연 평가

Array(100000).fill().map((v, i) => i)
  .slice(0, 30)
  .map((v) => v + 1)
  .filter((v) => v % 3 === 0)
  .slice(0, 10);
  
  [ 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 ]

• 위 코드의 경우에는 결과는 같지만 작업 횟수가 slice 30, map 30, filter 30, slice 10해서 총 100번의 연산이 실행된다.
• 처음 연산을 시작하기 전에 slice(0, 30)를 넣어주어 작업 범위를 줄여 연산 횟수를 크게 줄일 수 있다.

제너레이터와 이터러블 프로토콜을 따르는 함수들과 함께 사용하면 지연평가를 구현할 수 있다.

Generator 함수를 통한 구현

Generator 함수를 호출하면 Generator 객체를 반환한다. 이 Generator 객체는 바로 내부 동작을 수행하지 않고 next 메서드를 호출할 때 비로소 연산을 수행한다. 이러한 특징이 지연 평가를 가능케 한다.

// 지연 평가 함수 모음
const L = {}

L.map = function* (f, iter) {
  for (let item of iter) {
    yield f(item)
  }
}

L.filter = function* (f, iter) {
  for (let item of iter) {
    if(f(item)) yield item
  }
}

L.take = function* (limit, iter) {
  for (let item of iter) {
    yield item
    if (!--limit) break
  }
}

// 엄격한 평가 함수 모음
const _ = {}

_.take = function(limit, iter) {
  const result = []
  for (let item of iter) {
    result.push(item)
    if (result.length === limit) return result
  }
}

Lodash를 이용한 구현

Loadash에서는 _.chain , _.value 함수를 이용해 지연 평가를 지원한다. chain 함수의 인자로 사용할 데이터를 넘기면 해당 데이터를 lodash 객체로 감싼다. 이후 제공되는 지연 평가 함수들을 이용해 원하는 결과로 가공한다. 최종적으로 value 함수를 통해 wrapping되어 있는 결과를 실제 값으로 치환한다.

let _ = require('lodash');

const arr = Array(1000000)
  .fill()
  .map((v, i) => i);
  
const result = _.chain(arr)
  .map((num) => num + 1)
  .filter((num) => num % 3 === 0)
  .take(10)
  .value();
console.log(result);
//[ 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 ]