英文: Understanding Memoization in JavaScript to Improve Performance

中文: 了解JavaScript中的Memoization以提高性能--react的應用

我們渴望提高應用程序的性能，Memoization是JavaScript中的一種技術，通過緩存結果并在下一個操作中重新使用緩存來加速查找費時的操作。

在這里，我們將看到memoization的用法以及它如何幫助優(yōu)化應用的性能。

Memoization: 基本想法

如果我們有CPU密集型操作，我們可以通過將初始操作的結果存儲在緩存中來優(yōu)化使用。如果操作必然會再次執(zhí)行，我們將不再麻煩再次使用我們的CPU，因為相同結果的結果存儲在某個地方，我們只是簡單地返回結果。

可以看下面的例子:

function longOp(arg) {
    if( cache has operation result for arg) {
        return the cache
    }
    else {
        假設執(zhí)行一個耗時30分鐘的操作
        把結果存在`cache`緩存里
    }
    return the result
}
longOp('lp') // 因為第一次執(zhí)行這個參數(shù)的操作，所以需要耗時30分鐘
// 接下來會把結果緩存起來
longOp('bp') // 同樣的第一次執(zhí)行bp參數(shù)的操作，也需要耗時30分鐘
// 同樣會把結果緩存起來
longOp('bp') // 第二次出現(xiàn)了
// 會很快的把結果從緩存里取出來
longOp('lp') //也同樣出現(xiàn)過了
// 快速的取出結果

就CPU使用而言，上面的偽函數(shù)longOp是一種耗時的功能。上面的代碼會把第一次的結果給緩存起來，后面具有相同輸入的調(diào)用都會從緩存中提取結果，這樣就會繞過時間和資源消耗。

下面看一個平方根的例子:

function sqrt(arg) {
    return Math.sqrt(arg);
}
log(sqrt(4)) // 2
log(sqrt(9)) // 3

現(xiàn)在我們可以使用memoize來處理這個函數(shù):

function sqrt(arg) {
    if (!sqrt.cache) {
        sqrt.cache = {}
    }
    if (!sqrt.cache[arg]) {
        return sqrt.cache[arg] = Math.sqrt(arg)
    }
    return sqrt.cache[arg]
}

可以看到，結果會緩存在cache的屬性里。

Memoization：履行

在上面部分，我們?yōu)楹瘮?shù)添加了memoization。

現(xiàn)在，我們可以創(chuàng)建一個獨立的函數(shù)來記憶任何函數(shù)。我們將此函數(shù)稱為memoize。

function memoize(fn) {
    return function () {
        var args = Array.prototype.slice.call(arguments)
        fn.cache = fn.cache || {};
        return fn.cache[args] ? fn.cache[args] : (fn.cache[args] = fn.apply(this,args))
    }
}

我們可以看到這段代碼接收另外一個函數(shù)作為參數(shù)并返回。

要使用此函數(shù)，我們調(diào)用memoize將要緩存的函數(shù)作為參數(shù)傳遞。

memoizedFunction = memoize(funtionToMemoize)
memoizedFunction(args)

我們現(xiàn)在把上面的例子加入到這個里面:

function sqrt(arg) {
    return Math.sqrt(arg);
}
const memoizedSqrt = memoize(sqrt)

返回的函數(shù)memoizedSqrt現(xiàn)在是sqrt的memoized版本。

我們來調(diào)用下:

//...
memoizedSqrt(4) // 2 calculated(計算)
memoizedSqrt(4) // 2 cached
memoizedSqrt(9) // 3 calculated
memoizedSqrt(9) // 3 cached
memoizedSqrt(25) // 5 calculated
memoizedSqrt(25) // 5 cached

我們可以將memoize函數(shù)添加到Function原型中，以便我們的應用程序中定義的每個函數(shù)都繼承memoize函數(shù)并可以調(diào)用它。

Function.prototype.memoize = function() {
    var self = this
    return function () {
        var args = Array.prototype.slice.call(arguments)
        self.cache = self.cache || {};
        return self.cache[args] ? self.cache[args] : (self.cache[args] = self(args))
    }
}

我們知道JS中定義的所有函數(shù)都是從Function.prototype繼承的。因此，添加到Function.prototype的任何內(nèi)容都可用于我們定義的所有函數(shù)。

我們現(xiàn)在再來試試:

function sqrt(arg) {
    return Math.sqrt(arg);
}
// ...
const memoizedSqrt = sqrt.memoize()
log(memoizedSqrt(4)) // 2, calculated
log(memoizedSqrt(4)) // 2, returns result from cache
log(memoizedSqrt(9)) // 3, calculated
log(memoizedSqrt(9)) // 3, returns result from cache
log(memoizedSqrt(25)) // 5, calculated
log(memoizedSqrt(25)) // 5, returns result from cache

Memoization: Speed and Benchmarking

memoization的目標是速度，他通過內(nèi)存來提升速度。

看下面的對比:
文件名: memo.js:

function memoize(fn) {
    return function () {
        var args = Array.prototype.slice.call(arguments)
        fn.cache = fn.cache || {};
        return fn.cache[args] ? fn.cache[args] : (fn.cache[args] = fn.apply(this,args))
    }
}

function sqrt(arg) {
    return Math.sqrt(arg);
}
const memoizedSqrt = memoize(sqrt)
console.time("non-memoized call")
console.log(sqrt(4))
console.timeEnd("non-memoized call")
console.time("memoized call")
console.log(sqrt(4))
console.timeEnd("memoized call")

然后node memo.js可以發(fā)現(xiàn)輸出，我這里是:

2
non-memoized call: 2.210ms
2
memoized call: 0.054ms

可以發(fā)現(xiàn)，速度還是提升了不少。

Memoization: 該什么時候使用

在這里，memoization通常會縮短執(zhí)行時間并影響我們應用程序的性能。當我們知道一組輸入將產(chǎn)生某個輸出時，memoization最有效。

遵循最佳實踐，應該在純函數(shù)上實現(xiàn)memoization。純函數(shù)輸入什么就返回什么，不存在副作用。

記住這個是以空間換速度，所以最好確定你是否值得那么做，有些場景很有必要使用。

在處理遞歸函數(shù)時，Memoization最有效，遞歸函數(shù)用于執(zhí)行諸如GUI渲染，Sprite和動畫物理等繁重操作。

Memoization: 什么時候不要使用

不是純函數(shù)的時候(輸出不完全依賴于輸入)。

使用案例：斐波那契系列(Fibonacci)

Fibonacci是許多復雜算法中的一種，使用memoization優(yōu)化的作用很明顯。

1,1,2,3,5,8,13,21,34,55,89
每個數(shù)字是前面兩個數(shù)字的和。
現(xiàn)在我們用js實現(xiàn):

function fibonacci(num) {
    if (num == 1 || num == 2) {
        return 1
    }
    return fibonacci(num-1) + fibonacci(num-2)
}

如果num超過2，則此函數(shù)是遞歸的。它以遞減方式遞歸調(diào)用自身。

log(fibonacci(4)) // 3

讓我們根據(jù)memoized版本對運行斐波那契的有效性進行測試。
memo.js文件:

function memoize(fn) {
    return function () {
        var args = Array.prototype.slice.call(arguments)
        fn.cache = fn.cache || {};
        return fn.cache[args] ? fn.cache[args] : (fn.cache[args] = fn.apply(this,args))
    }
}



function fibonacci(num) {
    if (num == 1 || num == 2) {
        return 1
    }
    return fibonacci(num-1) + fibonacci(num-2)
}

const memFib = memoize(fibonacci)
console.log('profiling tests for fibonacci')
console.time("non-memoized call")
console.log(memFib(6))
console.timeEnd("non-memoized call")
console.time("memoized call")
console.log(memFib(6))
console.timeEnd("memoized call")

接下來調(diào)用:

$ node memo.js
profiling tests for fibonacci
8
non-memoized call: 1.027ms
8
memoized call: 0.046ms

可以發(fā)現(xiàn)，很小的一個數(shù)字，時間差距就那么大了。

上面是參考原文，下面是個人感想。

咋說呢, 第一時間想到了react的memo組件(注意 這里，現(xiàn)版本(16.6.3)有兩個memo,一個是React.memo,還有一個是React.useMemo, 我們這里說的是useMemo)，相信關注react動態(tài)的都知道useMemo是新出來的hooks api，并且這個api是作用于function組件，官方文檔寫的是這個可以優(yōu)化用以優(yōu)化每次渲染的耗時工作。

看文檔這里介紹的也挺明白。今天看到medium的這篇文章，感覺和react memo有關系，就去看了下源碼，發(fā)現(xiàn)的確是和本文所述一樣。

export function useMemo<T>(
  nextCreate: () => T,
  inputs: Array<mixed> | void | null,
): T {
  currentlyRenderingFiber = resolveCurrentlyRenderingFiber(); //返回一個變量
  workInProgressHook = createWorkInProgressHook(); // 返回包含memoizedState的hook對象

  const nextInputs =
    inputs !== undefined && inputs !== null ? inputs : [nextCreate]; // 需要保存下來的inputs，用作下次取用的key

  const prevState = workInProgressHook.memoizedState; // 獲取之前緩存的值
  if (prevState !== null) {
    const prevInputs = prevState[1];
    // prevState不為空，并且取出上次存的`key`, 然后下面判斷(前后的`key`是不是同一個)，如果是就直接返回，否則繼續(xù)向下
    if (areHookInputsEqual(nextInputs, prevInputs)) {
      return prevState[0];
    }
  }

  const nextValue = nextCreate(); //執(zhí)行useMemo傳入的第一個參數(shù)(函數(shù))
  workInProgressHook.memoizedState = [nextValue, nextInputs]; // 存入memoizedState以便下次對比使用
  return nextValue; 
}

進行了緩存(workInProgressHook.memoizedState就是hook返回的對象并且包含memoizedState，進行對比前后的inputs是否相同,然后再次進行操作)，并且支持傳遞第二個數(shù)組參數(shù)作為key。

果然, useMemo就是用的本文提到的memoization來提高性能的。

其實從官方文檔就知道這個兩個有關系了 :cry: :

Pass a “create” function and an array of inputs. useMemo will only recompute the memoized value when one of the inputs has changed. This optimization helps to avoid expensive calculations on every render.