This article mainly introduces the function memory of JavaScript learning notes. The editor thinks it is quite good. Now I will share it with you and give it as a reference. Let’s follow the editor and take a look.
This article explains the implementation of function memory and Fibonacci sequence and shares it with everyone. The details are as follows
Definition
Function memory refers to caching the last calculation result. When the next call is made, if the same parameters are encountered, the data in the cache will be returned directly.
For example:
function add(a, b) { return a + b; } // 假设 memorize 可以实现函数记忆 var memoizedAdd = memorize(add); memoizedAdd(1, 2) // 3 memoizedAdd(1, 2) // 相同的参数,第二次调用时,从缓存中取出数据,而非重新计算一次
Principle
It is very simple to implement such a memorize function. In principle, only the parameters and corresponding result data need to be stored in an object. When calling, it is judged whether the data corresponding to the parameter exists, and if it exists, the corresponding result data is returned.
First version
Let’s write a version:
// 第一版 (来自《JavaScript权威指南》) function memoize(f) { var cache = {}; return function(){ var key = arguments.length + Array.prototype.join.call(arguments, ","); if (key in cache) { return cache[key] } else return cache[key] = f.apply(this, arguments) } }
Let’s test it out :
var add = function(a, b, c) { return a + b + c } var memoizedAdd = memorize(add) console.time('use memorize') for(var i = 0; i < 100000; i++) { memoizedAdd(1, 2, 3) } console.timeEnd('use memorize') console.time('not use memorize') for(var i = 0; i < 100000; i++) { add(1, 2, 3) } console.timeEnd('not use memorize')
In Chrome, using memorize takes about 60ms. If we don't use function memory, it takes about 1.3 ms.
Note
What, we used the seemingly advanced function memory, but it turned out to be more time-consuming, almost 60 times in this example!
So, function memory is not omnipotent. If you look at this simple scenario, it is actually not suitable for using function memory.
It should be noted that function memory is just a programming technique. It essentially sacrifices the space complexity of the algorithm in exchange for better time complexity. In client-side JavaScript, the execution time complexity of the code often becomes bottleneck, so in most scenarios, this approach of sacrificing space for time to improve program execution efficiency is very desirable.
Second Edition
Because the first edition uses the join method, we can easily think that when the parameter is an object, the toString method will be automatically called. Convert to [Object object], and then concatenate the string as the key value. Let’s write a demo to verify this problem:
var propValue = function(obj){ return obj.value } var memoizedAdd = memorize(propValue) console.log(memoizedAdd({value: 1})) // 1 console.log(memoizedAdd({value: 2})) // 1
Both return 1, which is obviously a problem, so let’s see how underscore’s memoize function is implemented :
// 第二版 (来自 underscore 的实现) var memorize = function(func, hasher) { var memoize = function(key) { var cache = memoize.cache; var address = '' + (hasher ? hasher.apply(this, arguments) : key); if (!cache[address]) { cache[address] = func.apply(this, arguments); } return cache[address]; }; memoize.cache = {}; return memoize; };
As can be seen from this implementation, underscore uses the first parameter of the function as the key by default, so if you use
# directly ##
var add = function(a, b, c) { return a + b + c } var memoizedAdd = memorize(add) memoizedAdd(1, 2, 3) // 6 memoizedAdd(1, 2, 4) // 6
var memoizedAdd = memorize(add, function(){ var args = Array.prototype.slice.call(arguments) return JSON.stringify(args) }) console.log(memoizedAdd(1, 2, 3)) // 6 console.log(memoizedAdd(1, 2, 4)) // 7
Applicable scenarios
var count = 0; var fibonacci = function(n){ count++; return n < 2? n : fibonacci(n-1) + fibonacci(n-2); }; for (var i = 0; i <= 10; i++){ fibonacci(i) } console.log(count) // 453
So the total number of executions is: 177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 times!
What if we use function memory?
var count = 0; var fibonacci = function(n) { count++; return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2); }; fibonacci = memorize(fibonacci) for (var i = 0; i <= 10; i++) { fibonacci(i) } console.log(count) // 12
So we need to carefully look at our writing method. In our writing method, we actually overwrite the original fibonacci function with the generated fibonacci function. When we execute fibonacci(0), the function is executed once, and the cache is { 0: 0}, but when we execute fibonacci(2), we execute fibonacci(1) + fibonacci(0), because the value of fibonacci(0) is 0, !cache[address]
The result If it is true, the fibonacci function will be executed again. It turns out that the extra time is here!
One more thing
Maybe you will feel that fibonacci is not used in daily development. This example feels that it is not of high practical value. In fact, this The example is used to illustrate a usage scenario, that is, if a large number of repeated calculations are required, or a large number of calculations depend on previous results, you can consider using function memory. And when you encounter this kind of scene, you will know it.
The above is the detailed content of Introduction to JavaScript functions. For more information, please follow other related articles on the PHP Chinese website!