logo
Nostrss
Published on

나는 가끔 기다리고 싶을 때가 있다. (feat. 지연평가)

Authors
Lazy Evaluation

이번에는 2개의 함수를 구현해 보려고 한다. 숫자의 리스트를 만드는 range 함수와, 이터레이터에서 앞에서부터 n개의 요소만 가져오는 take 함수이다. 그리고 이것을 통해 지연 평가(Lazy Evaluation) 라는 개념에 대해서 알아보자.

숫자를 만드는 두 가지 방법

1. 성실한 Range

우리가 흔히 숫자 리스트를 만들 때 사용하는 방식이다.

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

var list = range(4)
log(list) // [0, 1, 2, 3]

range(4)를 호출하는 순간 [0, 1, 2, 3]이라는 배열이 즉시 만들어진다. 만약 range(100)이라면 100개짜리 배열이 메모리에 생긴다. 여기까지는 아주 익숙하다.

2. 게으른 L.range (Lazy Evaluation, 지연평가)

이번에는 자바스크립트의 제너레이터(Generator) 를 사용해서 조금 다르게 만들어보자.

const L = {}
L.range = function* (l) {
  let i = -1
  while (++i < l) {
    yield i
  }
}

var list = L.range(4)
log(list) // L.range {<suspended>}

L.range(4)를 호출했더니 배열이 나오지 않고 L.range {<suspended>}가 나온다. 이것은 이터레이터(Iterator) 다. 아직 내부의 코드는 실행되지 않았다.

우리가 list.next()를 호출하거나, for...of 문 등으로 순회할 때 비로소 코드가 실행되면서 값을 하나씩 던져준다(yield). 필요할 때 값을 평가한다고 해서 지연 평가(Lazy Evaluation) 라고 부른다.

왜 게으른 게 좋을까?

"어차피 다 쓸 거면 미리 만들어두나 그때그때 만드나 똑같은 거 아냐?" 라고 생각할 수 있다. 맞다. 리스트의 모든 요소를 순회하며 연산해야 한다면, range와 L.range의 성능 차이는 크지 않다.

하지만 필요한 만큼만 가져다 쓴다면 이야기가 달라진다.

take 함수 등장

여기 리스트에서 앞에서부터 l개만 잘라주는 take 함수가 있다.

const take = curry((l, iter) => {
  let res = []
  for (const a of iter) {
    res.push(a)
    if (res.length == l) return res
  }
  return res
})

이제 range와 L.range를 take와 함께 사용해서 비교해보자.

성능 비교 실험

10,000개의 숫자 중에서 앞의 5개만 필요하다고 가정해보자.

// 1. 일반 range 사용
go(
  range(10000), // 10,000개짜리 배열 생성! (이미 메모리 사용)
  take(5), // 앞의 5개만 자름
  reduce(add),
  log
)

// 2. L.range 사용
go(
  L.range(10000), // 아무것도 안 만듦 (준비만 함)
  take(5), // 최대 5개만 달라고 함
  reduce(add),
  log
)

실행 흐름 차이:

  1. 일반 range:

    • 0부터 9999까지 담긴 배열을 전부 만든다.
    • 그 배열을 take에게 넘긴다.
    • take는 거기서 5개만 꺼낸다.
    • 나머지 9,995개는? 그냥 만들어지고 버려졌다. 낭비다.

  2. L.range:

    • L.range는 아직 아무것도 안 만들었다.
    • take가 "첫 번째 값 줘"라고 요청하면, 그때 L.range가 0을 만들어서 준다.
    • take가 "두 번째 값 줘"라고 하면, 1을 만들어서 준다.
    • ...
    • take가 5개를 다 채우고 나면, 더 이상 값을 요청하지 않는다.
    • L.range도 멈춘다. 5부터 9999까지는 아예 생성조차 되지 않는다.

시간 측정 결과

실제로 console.time으로 측정해보면 극적인 차이를 볼 수 있다.

function test(name, time, f) {
  console.time(name)
  while (time--) f()
  console.timeEnd(name)
}

test('range', 10, () => reduce(add, take(5, range(1000000)))) // 0.151123046875 ms
test('L.range', 10, () => reduce(add, take(5, L.range(1000000)))) // 0.01904296875 ms

range는 백만 개를 만드느라 끙끙대지만, L.range는 순식간에 끝난다. 숫자 크기가 커질수록 이 차이는 훨씬 더 벌어진다.

마치 무한수열(Infinity) 도 다를 수 있게 되는 것이다.

L.range(Infinity) // 가능함!
take(5, L.range(Infinity)) // [0, 1, 2, 3, 4]

일반 range(Infinity)를 했다면 브라우저는 바로 뻗어버렸을 것이다.

정리

  • range: 끝까지 다 만든다. 성실하지만 때론 미련하다.
  • L.range: 부르면 만든다. 게으르지만 효율적이다.
  • take: 필요한 만큼만 평가하게 도와준다.

출처

인프런 함수형 프로그래밍과 JavaScript ES6+ 강의를 학습하고 정리한 내용입니다.

함수형 프로그래밍과 JavaScript ES6+