Lazy Evaluation(지연 평가)와 지연성 map, filter

아래는 즉시 평가되는 함수들이다. 매 연산마다 새로운 배열을 만들어야 하는데,

이 방법은 배열의 크기가 작으면 편리하지만, 배열의 크기가 큰 경우에는 계속해서 불필요한 연산을 해야 합니다.

// eager evaluation
go(
  range(10),
  map(a => a + 10),
  filter(a => a % 2),
  take(2),
  console.log
);
// [0, 1, 2, 3, ...]
// [10, 11, 12, ...]
// [false, true, false, ...]
// [11, 13]


// lazy evaluation
go(
  L.range(10),
  L.map(a => a + 10),
  L.filter(a => a % 2),
  take(2),
  console.log
);
// 0 (L.range) => 10 (L.map) => false
// 1 (L.range) => 11 (L.map) => true => console.log
// ...

 

위 코드에서, 지연 평가를 적용한 함수를 쓰면, 애초에 연산 횟수가 줄어서 일반 eager evaluation이 되는 경우보다 더 나은 성능을 보인다.

제너레이터를 통해서 lazy evaluation을 했기 때문에  take(2)가 통과되는 즉시 결과를 반환한다.

 

Lazy한 range로 살펴보는 lazy evaluation

 

아래는 일반적인 range 함수와 generator를 활용하여 iterator를 반환하는 방식을 활용한 L.range 함수를 만들어뒀습니다.

즉시 평가가 되지 않아서 좋은 점은, 미리 그 만큼의 배열을 생성해놓을 필요가 없다는 것이겠죠.

// 즉시 평가되는 range
const range = l => {
  let i = -1;
  let res = [];
  while (++i < l) {
    res.push(i);
  }
  return res;
};

// 지연 평가되는 range generator
L.range = function* (l) {
  let i = -1;
  while (++i < l) {
    yield i;
  }
};

// 같은 결과가 나옴
console.log(reduce((acc, cur) => acc + cur, range(10)));
console.log(reduce((acc, cur) => acc + cur, L.range(10)));

range 즉시 평가와, L.range의 지연 평가

연산 결과는 같아도 위 두 함수 간에는 차이가 존재합니다.

L.range = function* (l) {
  console.log('generater start'); // next 메서드가 적용되기 전까지 출력 안 됨
  let i = -1;
  while (++i < l) {
    console.log('i is', i); // next 메서드가 적용되기 전까지 출력 안 됨
    yield i;
  }
};
console.log(L.range(10)); // next 메서드가 적용되기 전까지 평가되지 않음.

const list = L.range(10);

console.log(list.next());
console.log(list.next());
console.log(list.next()); // i = 2 까지만 yield함

 

 

지연 평가가 즉시 평가보다 좋은가?

여기서 근본적인 의문점은, 지연 평가가 즉시 평가보다 좋은가?일 것입니다.

안 좋으면 굳이 generator 까지 써가면서 할 필욘 없으니까요.

 

1) 일반적으로 지연 평가 함수가 성능이 더 나음(반복을 적게 하는 경우 즉시 평가가 더 빠른 케이스도 있음.)

2) 무한 수열을 다룰 수 있음. 

 

 

1) 속도에 대하여

 

당연히 즉시 평가를 할 필요 없으니 지연평가가 빠를 것이고, 지연 평가를 할 필요도 없이 적은 숫자만 반복한다면 즉시 평가가 빠를 것입니다. 제 환경에서는 15번 정도 iteration을 돌아야 한다면 지연 평가가 빠르더라구요.

사실, api에서 넘어오는 배열의 크기는 15length 정도는 가뿐히 넘을테니, 일반적인 환경에서는 지연 평가가 더 낫다고 평가할 수 있을겁니다.

console.time('range');
console.log(range(100000));
console.timeEnd('range');
// range: 12.56884765625 ms

console.time('L.range');
console.log(L.range(100000));
console.timeEnd('L.range');
// L.range: 0.56494140625 ms

 

여기서 주의할 점은, 지연 평가 range를 잘 만들어 놓고서 다시 큰 사이즈의 배열을 재생성해야하는 동작을 하면 의미 없이 하면 안된다는 것입니다. 아래 같이 다시 큰 배열의 Array를 iterator를 풀어내서 다시 만들어내고, Array.prototype.reduce를 이용한다면..

이러면 즉시 평가되는 range와 크게 다를게 없어집니다. 헛짓이죠.

console.time('range');
console.log([...range(1000000)].reduce((acc, cur) => acc + cur, 0));
console.timeEnd('range');

console.time('L.range');
console.log([...L.range(1000000)].reduce((acc, cur) => acc + cur, 0));
console.timeEnd('L.range');

 

 

2) 무한에 대하여

 

극단적으로, 아래 같은 경우에도 Infinity의 크기 만큼의 배열을 만들 필요가 없으니까 메모리 부족으로 뻗지 않을겁니다.

const list = take(5, L.range(Infinity));
console.log(list); // [ 0, 1, 2, 3, 4 ]

 

실제로 Infinity의 크기를 가진 배열을 생성해보면 힙 메모리 부족 에러가 발생합니다.

FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory

 

 

Lazy한 map, filter

곧바로 결과를 반환하지 말고, iterator로 반환하면 된다. generator를 이용해 yield로 하나씩 뿌려주면 된다.

 

L.map = currify(function* (f, iter) {
  if (!isIterable(iter)) throw Error('not iterable');
  for (const value of iter) {
    yield f(value);
  }
});

L.filter = currify(function* (f, iter) {
  if (!isIterable(iter)) throw Error('not iterable');
  for (const value of iter) {
    if (f(value)) yield value;
  }
});

 

 

 

Array.prototype.flatMap이 나온 이유와 Lazy한 flatmap

 

우선, flatMap은, flat, map 메서드를 합쳐놓은 것으로, 각각의 메서드를 따로 썼을 때보다 효율적이라고 합니다.

이는 flat, map 각 메서드를 쓸때마다 배열을 반환하기 때문입니다. 

그래도 eager한 것은 동일하기 때문에 성능 차이가 그렇게 크다고 하지는 않다고 합니다.

console.log(list.flatMap(a => a.map(a => a * a)));

// flat 한 번 배열을 eager하게 만들고, map에서 다시 배열을 eager하게 만든다.
console.log(list.flat().map(a => a * a));

 

L.flatMap은 L.map과 L.flatten을 pipe로 묶어주어 가능합니다.

L.map = currify(function* (f, iter) {
  if (!isIterable(iter)) throw Error('not iterable');
  for (const value of iter) {
    yield f(value);
  }
});

// iterable 안의 값도 iterable이면 펼쳐내는 작업. 단, depth가 1인 경우만 됨
L.flatten = function* (iter) {
  for (const a of iter) {
    if (isIterable(iter)) yield* a;
    else yield a;
  }
};


L.flatMap = currify(pipe(L.map, L.flatten));


// use case
const list = [
  [1, 2],
  [3, 4],
  [5, 6, 7],
];

go(list, L.flatMap(map(a => a * a)), take(Infinity), console.log);

 

 

lodash를 사용해서 간편하게 지연 평가를 사용하기

이미 존재하는 큰 배열 => _chain 활용

새롭게 range 배열을 만들되 지연 평가된 range => _().range(n)

const _ = require('lodash');

// eager range
const range = (l) => {
  let i = -1;
  let res = [];
  while (++i < l) {
    res.push(i);
  }
  return res;
}

console.time("eager")
range(1000000).map(el => el + 10) 
console.timeEnd("eager")

console.time("lazy-1")
_.range(1000000).map(el => el + 10)
console.timeEnd("lazy-1")

console.time("lazy-2")
_().range(1000000).map(el => el + 10)
console.timeEnd("lazy-2")

console.time("lazy-3")
_.chain(range(1000000)).map(el => el + 10) 
console.timeEnd("lazy-3")

// eager: 104.301ms
// lazy-1: 73.382ms
// lazy-2: 0.851ms
// lazy-3: 51.678ms

 

 

ref)

https://edykim.com/ko/post/introduction-to-lodashs-delay-evaluation-by-filip-zawada/

https://armadillo-dev.github.io/javascript/whit-is-lazy-evaluation/