One item I’ve asked a lot of candidates: ✧(≖ ◡ ≖✿)
First of all, this is a very good interview question, you can investigate many aspects of the interviewer, such as basic skills, code ability, logical ability, and into attack, retreat can defend, for different levels of people can investigate different difficulties, such as beautiful sister out of 1☆, (*^__^*) hee hee……
Generally, after the interviewer answers the question, I can always casually throw out some more questions, looking at the interviewer surprised eyes, silently turn around and hide the merit and reputation
In this article, I will give you a deep copy puzzle, from the shallow to the deep, a total of four deep copy methods, each has its own characteristics and personality
Deep copy VS shallow copy
Before we start, I want to remind you what deep copy is, another term related to deep copy is shallow copy and what does that mean? Those of you who are familiar with this part can skip it
In fact, both deep copy and shallow copy are reference types. Variable types in JS are divided into value types (basic types) and reference types. Copying a value type makes a copy of the value, and assigning a value to a reference type makes a copy of the address, so that both variables point to the same data
// Basic type
var a = 1;
var b = a;
a = 2;
console.log(a, b); // 2, 1, a, b point to different data
// The reference type refers to the same data
var a = {c: 1};
var b = a;
a.c = 2;
console.log(a.c, b.c); // 2, 2 are all 2, a and b refer to the same data
Copy the codeFor reference types, this can result in a and B pointing to the same piece of data, and if you change one of them, it will affect the other. Sometimes this may not be the desired result, and it can cause unnecessary bugs if you are not clear about this phenomenon
How to sever the relationship between A and B? A copy of A’s data can be divided into shallow copy and deep copy according to the copy level. Shallow copy means only one copy, and deep copy means unlimited copy
var a1 = {b: {c: {}};
var a2 = shallowClone(a1); / / shallow copy
a2.b.c === a1.b.c // true
var a3 = clone(a1); / / copy
a3.b.c === a1.b.c // false
Copy the codeThe implementation of shallow copy is very simple, and there are many methods, in fact, the problem of iterating object properties, here is only one method, if you do not understand the following method, or interested in other methods, you can read my article
function shallowClone(source) {
var target = {};
for(var i in source) {
if(source.hasOwnProperty(i)) { target[i] = source[i]; }}return target;
}
Copy the codeThe simplest deep copy
The deep copy problem can actually be broken down into two problems, shallow copy + recursion, what does that mean? Suppose we have the following data
var a1 = {b: {c: {d: 1}};
Copy the codeJust make a few changes to the above shallow copy of the code, notice the difference
function clone(source) {
var target = {};
for(var i in source) {
if (source.hasOwnProperty(i)) {
if (typeof source[i] === 'object') {
target[i] = clone(source[i]); // Notice here
} else{ target[i] = source[i]; }}}return target;
}
Copy the codeMost people can write the code above, but when I ask what’s wrong with the code above? Very few people can answer it. Can you find the question?
There are too many problems with the code above, so let’s start with a few examples
- Parameters are not checked
- Determine if the object’s logic is not rigorous enough
- Array compatibility is not considered
(it’s even), let’s look at each problem solution, first we need to abstract an object, the method of judgment actually judging objects that are widely used in the method is as follows, in fact the following method also has a problem, but if you can answer that is very good, if interested in perfect solution, just look at here
function isObject(x) {
return Object.prototype.toString.call(x) === '[object Object]';
}
Copy the codeThe function validates the argument and returns it if it is not an object
function clone(source) {
if(! isObject(source))return source;
// xxx
}
Copy the codeOn the third question, well, I’ll leave it to you to lighten the burden by leaving arrays alone and considering set, Map, WeakSet, WeakMap, /(Remaining)
In fact, these three problems are small, but the biggest problem with recursive methods is stack bursting, when the data level is very deep, the stack will overflow
The following code, which we’ll use again later, generates code that specifies the depth and breadth of each layer
function createData(deep, breadth) {
var data = {};
var temp = data;
for (var i = 0; i < deep; i++) {
temp = temp['data'] = {};
for (var j = 0; j < breadth; j++) { temp[j] = j; }}return data;
}
createData(1.3); {data: {0: 0, 1: 1, 2: 2}}
createData(3.0); Data: {data: {data: {data: {}}}}
Copy the codeStack overflow occurs when the clone level is deep, but data breadth does not cause overflow
clone(createData(1000)); // ok
clone(createData(10000)); // Maximum call stack size exceeded
clone(createData(10.100000)); // ok breadth does not overflow
Copy the codeIn most cases this level of data is not available, but there is a fatal problem with this approach, which is circular referencing, for example
var a = {};
a.a = a;
clone(a) // Maximum call Stack size exceeded If the remaining number is exceeded, /(" remaining ")/~~
Copy the codeThere are two ways to solve the problem of circular reference, which has always been cyclic detection. One is brute force cracking. We can think about the circular detection by ourselves. We’ll explain more about brute force cracking in the following section
A deep copy of a line of code
Some students may have seen using the system’s own JSON to do deep copy examples, let’s look at the code implementation
function cloneJSON(source) {
return JSON.parse(JSON.stringify(source));
}
Copy the codeIn fact, when I first simple this method, sincerely expressed admiration, in fact, using tools to achieve the goal, is a very smart approach
Let’s test cloneJSON for overflow issues. It looks like cloneJSON uses recursion internally
cloneJSON(createData(10000)); // Maximum call stack size exceeded
Copy the codeNow that we’re recursing, what about circular references? Json.stringify does not cause a stack overflow because of an infinite loop. Instead, it does an internal loop reference check, which is the first method we mentioned above: loop check
var a = {};
a.a = a;
cloneJSON(a) // Uncaught TypeError: Converting circular structure to JSON
Copy the codeCrack a recursive stack burst
The first is to eliminate tail recursion, which doesn’t seem to work in this case. The second is to skip recursion altogether and use loops. When I suggested loops, almost 90% of the front end was unwritable code, which actually surprised me
As an example, suppose you have the following data structure
var a = {
a1: 1.a2: {
b1: 1.b2: {
c1: 1}}}Copy the codeIt’s a tree, and it’s pretty obvious when you look across the data
a
/ \
a1 a2
| / \
1 b1 b2
| |
1 c1
|
1
Copy the codeTo loop through a tree, you need to use a stack. When the stack is empty, the loop is finished, and the stack stores the next node to be copied
First we put seed data on the stack, and the key is used to store the child copy object of which parent element is placed
It then iterates through the children of the current node, putting them on the stack if they are objects, and copying them otherwise
function cloneLoop(x) {
const root = {};
/ / stack
const loopList = [
{
parent: root,
key: undefined.data: x,
}
];
while(loopList.length) {
// Depth first
const node = loopList.pop();
const parent = node.parent;
const key = node.key;
const data = node.data;
// Initialize the assignment target. If key is undefined, copy it to the parent element, otherwise copy it to the child element
let res = parent;
if (typeofkey ! = ='undefined') {
res = parent[key] = {};
}
for(let k in data) {
if (data.hasOwnProperty(k)) {
if (typeof data[k] === 'object') {
// Next loop
loopList.push({
parent: res,
key: k,
data: data[k],
});
} else{ res[k] = data[k]; }}}}return root;
}
Copy the codeAfter switching to loops, stack bursts are no longer a problem, but circular references are still a problem
Breaking circular references
Is there a way to break the loop? One of the problems with all three methods is reference loss, which may not be acceptable in some cases
For example, if an object A has two keys that refer to the same object B, after a deep copy, the two keys of A will lose their reference relationship and become two different objects, O (╯□╰) O
var b = {};
var a = {a1: b, a2: b};
a.a1 === a.a2 // true
var c = clone(a);
c.a1 === c.a2 // false
Copy the codeIf we find a new object we save it along with its copy. Each time we check to see if it has already been copied. If so, we skip copying and just use the original one so that we can preserve the reference relationship ✧(≖ ≖✿)
But how to write code, O (╯□╰) O, don’t hurry to look down, in fact, and loop code roughly the same, different places I use // ========== marked out
UniqueList a uniqueList array is used to store a uniqueList array that has been copied. For each loop, check whether the object is in uniqueList. If it is, copy logic will not be executed
Find is an abstract function that iterates through uniqueList
// Keep the reference relationship
function cloneForce(x) {
/ / = = = = = = = = = = = = =
const uniqueList = []; // use to remove weight
/ / = = = = = = = = = = = = =
let root = {};
// loop array
const loopList = [
{
parent: root,
key: undefined.data: x,
}
];
while(loopList.length) {
// Depth first
const node = loopList.pop();
const parent = node.parent;
const key = node.key;
const data = node.data;
// Initialize the assignment target. If key is undefined, copy it to the parent element, otherwise copy it to the child element
let res = parent;
if (typeofkey ! = ='undefined') {
res = parent[key] = {};
}
/ / = = = = = = = = = = = = =
// The data already exists
let uniqueData = find(uniqueList, data);
if (uniqueData) {
parent[key] = uniqueData.target;
continue; // Break the loop
}
// Data does not exist
// Save the source data and reference it in the copy data
uniqueList.push({
source: data,
target: res,
});
/ / = = = = = = = = = = = = =
for(let k in data) {
if (data.hasOwnProperty(k)) {
if (typeof data[k] === 'object') {
// Next loop
loopList.push({
parent: res,
key: k,
data: data[k],
});
} else{ res[k] = data[k]; }}}}return root;
}
function find(arr, item) {
for(let i = 0; i < arr.length; i++) {
if (arr[i].source === item) {
returnarr[i]; }}return null;
}
Copy the codeSo let’s check that out. Amazing
var b = {};
var a = {a1: b, a2: b};
a.a1 === a.a2 // true
var c = cloneForce(a);
c.a1 === c.a2 // true
Copy the codeHere’s how to break a circular reference. Wait, the code above looks like it can break a circular reference
(*^__^*) hee hee……
var a = {};
a.a = a;
cloneForce(a)
Copy the codeIs the seemingly perfect cloneForce ok? CloneForce has two problems
If holding a reference is not what you want, then you can’t use cloneForce.
The second problem is that cloneForce can be very problematic when there are a large number of objects. It is not suitable to use cloneForce if there is a large amount of data
The performance comparison
The above content is a bit difficult, but let’s do something more difficult and compare the performance of different methods
Let’s do the experiment first and look at the data. There are two reasons that affect the performance, one is depth, the other is breadth of each layer. We test the performance by fixing one variable and letting only one variable change
The test method is the number of times the deep copy is executed within a specified period of time. The more times, the better the performance
Clone (createData(500, 1)) in 2 seconds
function runTime(fn, time) {
var stime = Date.now();
var count = 0;
while(Date.now() - stime < time) {
fn();
count++;
}
return count;
}
runTime(function () { clone(createData(500.1))},2000);
Copy the codeLet’s do the first test. Set the width at 100, the depth at 100, and record the number of times you execute it in 1 second
| The depth of the | clone | cloneJSON | cloneLoop | cloneForce |
|---|---|---|---|---|
| 500 | 351 | 212 | 338 | 372 |
| 1000 | 174 | 104 | 175 | 143 |
| 1500 | 116 | 67 | 112 | 82 |
| 2000 | 92 | 50 | 88 | 69 |
If you tabulate the data above, you can see some patterns
- As the depth gets smaller, the difference gets smaller
- Clone and cloneLoop are not that different
- cloneLoop > cloneForce > cloneJSON
Let’s start by looking at the time complexity of each method, because each method has to do the same thing, but I’m not going to calculate it, like loop through an object, and see if it’s an object
- Clone time = create recursive function + processing time per object
- CloneJSON time = loop detection + processing time per object * 2 (recursive transform string + recursive parsing)
- CloneLoop time = processing time per object
- CloneForce Time = Determine whether an object is in the cache + processing time per object
CloneJSON is 50 percent as fast as Clone, which is easy to understand because it takes one more recursion
If the number of objects is n, the time complexity of the judgment logic is O(n2). The more objects there are, the slower cloneForce will be
1 + 2 + 3... + n = n^2/2 - 1Copy the codeThere is a problem with Clone and cloneLoop. There seems to be a discrepancy between the experimental results and the inference results
Next, do a second test, fix the depth at 10000, the breadth at 0, and record the number of executions in 2 seconds
| The width of the | clone | cloneJSON | cloneLoop | cloneForce |
|---|---|---|---|---|
| 0 | 13400 | 3272 | 14292 | 989 |
Take a look at the effect of depth on each method, regardless of width
- As the number of objects increases, cloneForce’s poor performance becomes apparent
- CloneJSON’s performance is also compromised because loop checking takes a lot of time
- CloneLoop performs better than Clone, and you can see that recursive new functions take negligible time compared to looping objects
Let’s test the performance limits of cloneForce, this time by testing how long it takes to run the specified number of times
var data1 = createData(2000.0);
var data2 = createData(4000.0);
var data3 = createData(6000.0);
var data4 = createData(8000.0);
var data5 = createData(10000.0);
cloneForce(data1)
cloneForce(data2)
cloneForce(data3)
cloneForce(data4)
cloneForce(data5)
Copy the codeThrough the test, it is found that the time increases exponentially. When the number of objects is more than 10,000 levels, there will be a delay of more than 300ms
conclusion
In fact, each method has its own advantages and disadvantages, and applicable scenarios. It is the truth that people make the best use of their talents and things
The following is a comparison of various methods, hoping to provide you with some help
| clone | cloneJSON | cloneLoop | cloneForce | |
|---|---|---|---|---|
| The difficulty | Do do | Do things | Do do do | Being fostered fostered fostered |
| compatibility | ie6 | ie8 | ie6 | ie6 |
| A circular reference | A layer of | Does not support | A layer of | support |
| Stack overflow | will | will | Don’t | Don’t |
| Keep references | no | no | no | is |
| Suitable for the scene | General data copy | General data copy | A lot of hierarchy | Keep references |
This article is all inspired by @jsmini/ Clone. If you want to use the four deep-copy methods in this article, you can directly use @jsmini/ Clone library
// npm install --save @jsmini/clone
import { clone, cloneJSON, cloneLoop, cloneForce } from '@jsmini/clone';
Copy the codeFor simplicity and readability, some boundary cases have been omitted from the sample code in this article. If you want to learn the code in production, read the @jsmini/ Clone source code
@jsMini/Clone incubated in JSMini, JSMini is committed to providing you with a group of small and beautiful, dependency free high quality library
Jsmini was born without Jslib-Base, thanks to JSLib-Base for providing the underlying technology for JSmini
Thank you for reading this article, and now you can handle any deep-copy problem. If you have any questions, please feel free to discuss them with me
Finally, I’d like to recommend my new book React State Management and Isomorphism For an in-depth look at cutting-edge isomorphism technology. Thank you for your support
Jingdong: item.jd.com/12403508.ht…
Down-down: product.dangdang.com/25308679.ht…
Finally recruitment front end, back end, client end! Location: Beijing + Shanghai + Chengdu, interested students, you can send your resume to my email: [email protected]
The original url: yanhaijing.com/javascript/…