點燈坊

失くすものさえない今が強くなるチャンスよ

使用 Generator 實現 Infinite Array

Sam Xiao's Avatar 2020-03-09

有些語言有 Infinite Array 概念，透過 ECMAScript 2015 的 Generator，我們也能實作出此概念。

Version

macOS Catalina 10.15.3
VS Code 1.42.1
Quokka 1.0.282
ECMAScript 2015

Array.from()

let range = (start, end, step) => 
  Array.from({ length: (end - start) / step }, (_, i) => start + (i * step))

range(1, 10, 3) // ?

ECMAScript 沒有內建 range()，標準做法是使用 Array.from() 實作 range()。

range000

Generator

function* range(start, end, step = 1) {
  for (let i = start; i < end; i+= step)
    yield i
}

[...range(1, 10, 3)] // ?

另一種方式改用 generator 實作 range()，使用 yield 回傳 iterator。

由於每呼叫一次 range() 只會執行一次 yield，因此要使用 ES6 的 ... spread operator 強迫展開 range() 才回執行所有 yield。

Q：Generator 也是使用 for loop，且只是從 return 改成 yield，function 變成 function*，看似只是 syntatic suguar 而已是嗎 ?

表面上 generator 看起來只是 syntatic suguar，但底層實作方式並不一樣。

傳統 function 會真的在記憶體放一份 array，而 generator 卻是 lazy evaluation，只有呼叫時才會 yield 該筆資料，因此記憶體內永遠只有該筆資料而已。

Generator 內的 for loop 真的只是 syntatic sugar，不會真的執行，而是 lazy evaluation，因此不必考慮其 big O

range001

inRange()

let range = (start, end, step) => 
  Array.from({ length: (end - start) / step }, (_, i) => start + (i * step))

let inRange = (v, start, end, step) => {
  for (let x of range(start, end, step)) {
    if (x === v)
      return true

    if (x > v)
      return false
  }
}

inRange(3, 1, 100, 2) // ?
inRange(96, 1, 100, 2) // ?

若要實作 inRange() 判斷指定 number 是否存在於 array，若使用 Array.from() 實作，必須真的在記憶體內展開全部 array 才能判斷，既浪費 CPU 也浪費記憶體。

range002

function* range(start, end, step = 1) {
  for(let i = start; i < end; i+= step) {
    yield i
  }
}

let inRange = (v, start, end, step) => {
  for (let x of range(start, end, step)) {
    if (x === v)
      return true

    if (x > v)
      return false
  }
}

inRange(3, 1, 100, 2) // ?
inRange(96, 1, 100, 2) // ?

若改用 generator 實作 range()，由於是 lazy evaluation，只有 for of loop 使用時才 yield 產生值，因此較省 CPU 與記憶體。

range003

Infinite Array

let range = (start, end, step) => 
  Array.from({ length: (end - start) / step }, (_, i) => start + (i * step))

let inRange = (v, start, end, step) => {
  for (let x of range(start, end, step)) {
    if (x === v)
      return true

    if (x > v)
      return false
  }
}

inRange(3, 1, Infinity, 2) // ?
inRange(96, 1, Infinity, 2) // ?

別忘了 ECMAScript 也有 Infinity，若要產生 infinite array，則 Array.from() 無福消受，因為根本無法建立 infinite array。

range004

function* range(start, end, step = 1) {
  for(let i = start; i < end; i+= step) {
    yield i
  }
}

let inRange = (v, start, end, step) => {
  for (let x of range(start, end, step)) {
    if (x === v) {
      return true
    }
    if (x > v) {
      return false
    }
  }
}

inRange(3, 1, Infinity, 2) // ?
inRange(96, 1, Infinity, 2) // ?

但由於 generator 是 lazy evaluation，因此可接受 Infinity。

range005

Conclusion

  • Generator 在實務上有兩個適用場景，如檔案很大，全部讀進記憶體要很久，甚至記憶體根本放不下，可改用 generator 讀取檔案，每次只要讀進一筆資料，且記憶體也只需一筆資料而已
  • 另一個適用場景是產生 infinite array，這也是 ES5 做不到的

Reference

MDN, Array.from
MDN, Generator

# ECMAScript