As we all know, the JS language itself does not provide deep copy of the Object function, whether it is direct assignment, object.assign, expansion operators… All are shallow copies. Some concepts about deep and shallow copies of JS can be referred to an article I wrote a long time ago
There are many excellent articles and implementations on the web about how to implement deep copy. This article focuses on an unconventional way to implement deep copy using non-recursive methods
In this article, only three data types are considered: array, object, and simple value
To realize the determination of data types, first to implement the three tool methods to determine the type. The most common is to use the Object. The prototype. The characteristics of the toString
const getType = v= > {
switch (Object.prototype.toString.call(v)) {
case "[object Object]":
return "Object";
case "[object Array]":
return "Array";
default:
// Consider only arrays and objects, the rest are simple values
return false; }};Copy the codeThe recursive implementation
Before I talk about the non-recursive implementation, let’s take a look at the deep copy implementation of the recursive version, which is very simple, directly into the code
const copy = source= > {
const _cp = source= > {
let dest;
const type = getType(source);
if (type === "Array") {
dest = [];
source.forEach((item, index) = > {
dest[index] = _cp(item);
});
return dest;
} else if (type === "Object") {
dest = {};
for (let [k, v] of Object.entries(source)) {
dest[k] = _cp(v);
}
return dest;
} else {
returnsource; }};return _cp(source);
};
Copy the codeOf course, this does not handle circular references. Processing cyclic reference is also very simple, use a WeakMap to record the value traversed, each copy before finding out the existence of the value in WeakMap, directly return. So the code after processing the loop reference looks like this
const copy = (source) = > {
const map = new WeakMap(a);const _cp = (source) = > {
let dest;
if (map.get(source)) {
return map.get(source);
}
const type = getType(source);
if (type === "Array") {
/ / array
dest = [];
map.set(source, dest);
source.forEach((item, index) = > {
dest[index] = _cp(item);
});
return dest;
} else if (type === "Object") {
// obj
dest = {};
map.set(source, dest);
for (let [k, v] of Object.entries(source)) {
dest[k] = _cp(v);
}
return dest;
} else {
returnsource; }};return _cp(source);
};
Copy the codeNon-recursive implementation
In fact, almost any recursive function can be implemented using non-recursive methods. If you have the experience of using javascript to brush Leetcode, a lot of times if our code uses recursion to solve the problem, there is no tail call optimization (many times some problems do not write tail call optimization method, or I may be too poor), it is easy to appear js call stack too deep error situation, At this point we can just go back to non-recursive writing, and it’s very simple
So let’s just take a look at the nature of j s recursion. J s global is that we have a function call stack, and when we call a function a, that function A is pushed, and when we call a again from within a, a new function A is pushed again. After execution, eject the stack one by one. The process is similar for multiple functions. The essence of non-recursive solution is to use the data structure of queue or stack to simulate the execution process of JS call stack
The pseudo-code is as follows, 99 percent of recursion can be implemented non-recursively with the following idea
-
Declare a stack variable to simulate the call stack
const stack = []; Copy the code
-
The initial parameter is pushed
stack.push({ param1, param2 }); Copy the code
-
If the stack is not empty, keep fetching the stack element
while (stack.length) { const item = stack.pop(); / /... } Copy the code -
If the next recursion needs to continue, the arguments of the next recursive call are pushed back on the stack
while(stack.length) { const item = stack.pop() // Continue with the next recursion // Each recursive execution flow. if (condition) { stack.push({{param1:nextParam1,param2:nextParam2}}) } else{... }}Copy the code -
The current recursive termination condition is not pushed
while(stack.length) { const item = stack.pop() // Continue with the next recursion // Each recursive execution flow. if (condition) {/ /... } else { // Recursive termination condition. Do not stack}}Copy the code
After reading this, you might wonder what happens if the result of each recursive call needs to be the return value of the next recursive call. Take the deep copy of our recursive implementation above
dest[index] = _cp(item);
Copy the codeActually is easy to understand, recursive, when we are at the next lower level recursive back, we also can explain the assignment in recursive scenarios, the next level returns after the execution of our current level variables are also in our implementation can directly, but the recursive case execution of the current iteration, there is no higher level variables. In this case, we need to pass in the next iteration one more variable that points to the lower result of the current iteration. (In recursive scenarios, the return value of the next level of recursion is set in the upper level; In a non-recursive scenario, the return value of the next level is called from the next level, much like we normally pass a callback function.
while(stack.length) {
const item = stack.pop()
// Continue with the next recursion
// Each recursive execution flow.// dest passed by the previous level
//
dest[xx] = xxx
if (condition) {
/ / attention to dest
stack.push({{param1:nextParam1,param2:nextParam2,dest: {}}}}else{... }}Copy the codeWith that in mind, I’m sure you all know the general idea of converting something like a recursive deep copy into a non-recursive implementation, which is to take an object, level by level, and break it down into keys and values. The following is a detailed analysis
-
First, a deep copy receives a value and then returns a copy value, so a reference to the copy value needs to be created initially. At each level of the iteration, we process the subparts of this reference
const copy = source= > { // Simple values are returned directly if(! getType(source)) {return source; } // Create the ontology of the final deep-copy value returned let dest = Array.isArray(source) ? [] : {}; / /... }; Copy the code -
Perform the mock call stack procedure mentioned above. In the recursive version, we know that the entry to the recursive function is actually the value of the child node that was visited, and the return value is the copy value of the current child node. As discussed earlier, iteration calls need to be set by passing in a reference value created at the previous level. So we iterate over the call, each time with two values: the original value of the node currently accessed (as in the recursive call) and the reference value used to store the copy (created in the previous iteration).
// Call stack initial state const queue = [{ source, dest }]; while (queue.length) { // source Specifies the node currently accessed // dest is used to store the copy reference value const { dest, source } = queue.shift(); // Determine the node type to be accessed const type = getType(source); // } Copy the code -
Each iteration process is discussed here in different cases
-
The access nodes are arrays
if (type === "Array") { / /... source.forEach((x, index) = > { const xType = getType(x); }); } Copy the code -
The entry is the object (1)
if (xType === "Object") { // Generate an object reference for the next iteration dest[index] = {}; // The next iteration is required queue.push({ source: x, dest: dest[index] }); return; } Copy the code -
The entry is an array (2)
if (xType === "Array") { // Generate an array reference for the next iteration dest[index] = []; // The next iteration is required queue.push({ source: x, dest: dest[index] }); return; } Copy the code -
Array entries are simple values. Set this value directly to dest
if(! getType(x)) { dest[index] = x;return; } Copy the code
-
-
Access nodes are objects. Similar to array handling
- Object keys are objects
- The object key is an array
- Object keys are simple values
Plus the circular reference processing is very simple, adding the current source to WeakMap at the end of each iteration. It is ok to judge whether the source of push is in WeakMap when dealing with stack.push of object type each time. If it is described as circular reference in WeakMap, set the value directly without pushing
while (stack.lenght) {
//....
if (xType === "Object") {
if (map.get(x)) {
dest[index] = map.get(x);
return;
}
dest[index] = {};
queue.push({
source: x,
dest: dest[index],
});
map.set(x, dest[index]);
return;
}
//....
}
Copy the codeFinally, a deep copy of our non-recursive version is complete. Although it took some effort to implement this copy, the code is much more complex than the recursive version, and the performance may be worse, but if you can look at it from the beginning to the end, and implement it yourself, I believe it will greatly improve my understanding of deep copy and the idea of functional recursion. The next time an interviewer asks you to write a deep copy, write a non-recursive version that will wow the interviewer.
The complete code is as follows
const copy2 = (source) = > {
if(! getType(source)) {/ / simple values
return source;
}
let dest = Array.isArray(source) ? [] : {};
const queue = [{ source, dest }];
const map = new WeakMap(a);while (queue.length) {
const { dest, source } = queue.shift();
const type = getType(source);
if (type === "Array") {
/ / array
source.forEach((x, index) = > {
const xType = getType(x);
if(! getType(x)) { dest[index] = x;return;
}
if (xType === "Array") {
dest[index] = [];
queue.push({
source: x,
dest: dest[index],
});
return;
}
if (xType === "Object") {
if (map.get(x)) {
dest[index] = map.get(x);
return;
}
dest[index] = {};
queue.push({
source: x,
dest: dest[index],
});
map.set(x, dest[index]);
return; }}); }else {
/ / object
for (let [k, v] of Object.entries(source)) {
const vType = getType(v);
if(! vType) { dest[k] = v;continue;
}
if (vType === "Array") {
dest[k] = [];
queue.push({
source: v,
dest: dest[k],
});
}
if (vType === "Object") {
if (map.get(v)) {
dest[k] = map.get(v);
continue;
}
dest[k] = {};
queue.push({
source: v,
dest: dest[k], }); } map.set(v, dest[k]); }}}return dest;
};
Copy the codeCode word is not easy, if you feel good, ask for a star or like it!