英文: Understanding Memoization in JavaScript to Improve Performance

我們渴望提高應(yīng)用程序的性能，Memoization是JavaScript中的一種技術(shù)，通過(guò)緩存結(jié)果并在下一個(gè)操作中重新使用緩存來(lái)加速查找費(fèi)時(shí)的操作。

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

Memoization: 基本想法

如果我們有CPU密集型操作，我們可以通過(guò)將初始操作的結(jié)果存儲(chǔ)在緩存中來(lái)優(yōu)化使用。如果操作必然會(huì)再次執(zhí)行，我們將不再麻煩再次使用我們的CPU，因?yàn)橄嗤Y(jié)果的結(jié)果存儲(chǔ)在某個(gè)地方，我們只是簡(jiǎn)單地返回結(jié)果。

可以看下面的例子:

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

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

下面看一個(gè)平方根的例子:

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

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

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

可以看到，結(jié)果會(huì)緩存在cache的屬性里。

Memoization：履行

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

現(xiàn)在，我們可以創(chuàng)建一個(gè)獨(dú)立的函數(shù)來(lái)記憶任何函數(shù)。我們將此函數(shù)稱(chēng)為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))
    }
}

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

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

memoizedFunction = memoize(funtionToMemoize)
memoizedFunction(args)

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

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

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

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

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

我們可以將memoize函數(shù)添加到Function原型中，以便我們的應(yīng)用程序中定義的每個(gè)函數(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)在再來(lái)試試:

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的目標(biāo)是速度，他通過(guò)內(nèi)存來(lái)提升速度。

看下面的對(duì)比:
文件名: 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: 該什么時(shí)候使用

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

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

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

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

Memoization: 什么時(shí)候不要使用

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

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

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

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

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

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

log(fibonacci(4)) // 3

讓我們根據(jù)memoized版本對(duì)運(yùn)行斐波那契的有效性進(jìn)行測(cè)試。
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")

接下來(lái)調(diào)用:

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

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

上面是參考原文，下面是個(gè)人感想。

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

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

//react/packages/react-reconciler/src/ReactFiberHooks.js
export function useMemo<T>(
  nextCreate: () => T,
  inputs: Array<mixed> | void | null,
): T {
  currentlyRenderingFiber = resolveCurrentlyRenderingFiber(); //返回一個(gè)變量
  workInProgressHook = createWorkInProgressHook(); // 返回包含memoizedState的hook對(duì)象

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

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

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

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

果然, useMemo就是用的本文提到的memoization來(lái)提高性能的。

其實(shí)從官方文檔就知道這個(gè)兩個(gè)有關(guān)系了 :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.