Preface;
Dynamic planning has appeared for more than ten years. According to Wikipedia, it is both a mathematical optimization method and a computer programming method. To truly apply dynamic programming, one problem must have two key properties: the optimal structure and the overlapping substructure. This article will not go into detail about dynamic programming, but will focus on how overlapping substructures become one of the key attributes of dynamic programming. Since this is related to the next storage solution problem, the discussion of it is very important.
This article will cover what a memo is, what value does a memo have for Javascript developers, and how to use it to improve itJavascriptfunction, thus gaining a deeper understanding of the memo itself and what the memo means for optimizing the application.
In this article, we will discuss the following topics:
- What is a memo
- The main concepts of memorandum
- Comparison between function usage memo and no memo
- The significance of the memorandum
What is a memorandum?
Memos are a form of cache, a value storage method that is convenient for entry and subsequent use. A memo is to record the results of the resolved problem, so that the next time you need to perform the same operation again, you don't have to recalculate it. However, a function needs to use a memo to meet certain conditions: it must be reference-transparent, that is, it can only be used if the effect of calling a function is exactly the same as replacing a function call with the return value of the function.
There are memos in most programming languages such as Ruby, C++, Python, etc., and there are even many libraries to simplify. In this article, we will focus on Javascript. Programming languages may be different, but the concepts and ideas are consistent.
The concept of memorandum
A memorandum requires understanding of the following two concepts:
1. Quote Transparent
If an expression can be replaced by its corresponding value without changing the behavior of the program (and vice versa), then it is called reference transparency. This requires that the expression must be pure, i.e. for the same input, the value of the expression must be the same, and its evaluation must have no side effects. Non-reference transparent expressions are called reference opacity.
With the above explanation, we can quickly associate it with the behavior of the memo, and this concept allows us to write a function with the memo.
2. Look up table
A lookup table (LUT) is an array that replaces runtime calculations with simpler array indexing operations. This process is called "direct addressing", and the difference between LUT and hash tables is that it retrieves a value.
Comparing functions using memos and not using memos
Take the classic Fibonacci sequence definition as an example:
function Fibo(n) {
if (n < 2) {
return n;
}
return Fibo(n - 1) + Fibo(n - 2);
} You might have expected that once you start using numbers greater than 20, the process will become very slow. And when you process a number of around 35, the computer probably can't hold on.
The solution is to record the return result of the calling function
var IterMemoFib = function() {
var cache = [1, 1];
var fib = function(n) {
if (n >= ) {
for (var i = ; i <= n; i++) {
cache[i] = cache[i - 2] + cache[i - 1];
}
}
return cache[n];
}
return fib;
}(); This part is a bit troublesome and is not completely readable, or you can also let the computer assist with it:
Fib = ();
Due to technical (browser security policy) limitations, the parameters of the memo function can only be array or scalar values, and cannot be objects.
The following code extendsFunctionObject to add memo function. If the function is a method, you can pass the object to memoize().
= function () {
var pad = {};
var self = this;
var obj = > 0 ? arguments[i] : null;
var memoizedFn = function () {
// Copy the arguments object into an array: allows it to be used as
// a cache key.
var args = [];
for (var i = 0; i < ; i++) {
args[i] = arguments[i];
}
// Evaluate the memoized function if it hasn't been evaluated with
// these arguments before.
if (!(args in pad)) {
pad[args] = (obj, arguments);
}
return pad[args];
};
= function () {
return self;
};
return memoizedFn;
};
= function () {
alert("Attempt to unmemoize an unmemoized function.");
return null;
}; The significance of the memorandum
- "Remember" the result corresponding to a specific set of inputs
- Memo reduces the time cost of the function in exchange for space cost
- Memos do not rely on machines
Conclusion: What is a memorandum?
In this article, we discuss the memorandum and its two main concepts: citation transparency and lookup tables. In addition, we explored its importance to Javascript code, compared the differences between code that does not use memos and code that uses memos, and gained a certain understanding of the techniques used to cache values.
This is the article about using memorandum to improve Javascript functions in dynamic planning. For more related memorandums to improve Javascript functions, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!