takeaway
Recently, I often see a lot of article summaries of handwritten JavaScript code, which provides many handwritten implementations of the JavaScript Api.
Most of the title implementations are similar, and to be honest, a lot of the code is very crude in my opinion, if I as an interviewer, see such code, in my mind is not qualified, this article I will take the simplest deep copy to tell.
Ask yourself three questions before reading this article:
-
Do you really understand what a deep copy is?
-
What does a deep copy look like to an interviewer?
-
What deep copy will amaze an interviewer?
Here’s a step-by-step guide to creating a deep copy of an amazing interviewer.
This article tests the code: github.com/ConardLi/Co…
For example, after the code is cloned to the local PC, run node clone1.test.js to view the test result.
It is recommended that you read it together with the test code for better results.
Definition of deep copy and shallow copy
Deep copy has been a commonplace topic, and it is also a frequent topic in front interviews. However, to my surprise, many students have not understood the difference and definition between deep copy and shallow copy. For example, the student who mentioned the issue to me the other day:
If you have any questions about assignment, how objects are stored in memory, variables and types, etc., you can read this article: juejin. Im /post/684490… .
You just need to be less aware of the difference between copying and assigning.
Let’s define deep copy and shallow copy:
Shallow copy:
Creates a new object that has an exact copy of the property values of the original object. If the property is of a primitive type, the value of the primitive type is copied, and if the property is of a reference type, the memory address is copied, so if one object changes the address, the other object is affected.
Deep copy:
A complete copy of an object from memory, from the heap memory to open a new area to store the new object, and the new object changes will not affect the original object
Without further ado, the shallow copy will not say any more, so let’s get to the point:
The beggar version
When we want to deep copy an object without using a third-party library, the most common method is the following.
JSON.parse(JSON.stringify());
Copy the codeThis is very simple and works well for most application scenarios, but it has some major drawbacks, such as copying other reference types, copying functions, circular references, and so on.
Obviously, you’re not going to be qualified if you just say that during the interview.
Next, let’s manually implement a deep copy method.
Basic version
With a shallow copy, we can easily write the following code:
function clone(target) {
let cloneTarget = {};
for (const key in target) {
cloneTarget[key] = target[key];
}
return cloneTarget;
};
Copy the codeCreate a new object, iterate over the objects to be cloned, add the attributes of the objects to be cloned to the new object in turn, and return.
In the case of a deep copy, we can solve the problem recursively by rewriting the above code slightly, given that we don’t know how deep the object we are copying is:
- If it is a primitive type, return it without further copying
- If it is a reference type, create a new object, iterate over the objects to be cloned, and add the properties of the objects to be cloned to the new object one by one after performing a deep copy.
It’s easy to understand that if there are deeper objects that can continue recursion until the property is of the original type, then we have a simple deep copy:
function clone(target) {
if (typeof target === 'object') {
let cloneTarget = {};
for (const key in target) {
cloneTarget[key] = clone(target[key]);
}
return cloneTarget;
} else {
returntarget; }};Copy the codeWe can open clone1.test.js in the test code to test the following test cases:
const target = {
field1: 1.field2: undefined.field3: 'ConardLi'.field4: {
child: 'child'.child2: {
child2: 'child2'}}};Copy the codeExecution Result:
This is a deep copy of the most basic version. This code will allow you to show the interviewer that you can solve a problem with recursion, but obviously it has a lot of drawbacks, such as not considering arrays.
Consider the array
In the previous version, we only initialized normal objects. Now we only need to change the initialization code to be compatible with arrays:
module.exports = function clone(target) {
if (typeof target === 'object') {
let cloneTarget = Array.isArray(target) ? [] : {};
for (const key in target) {
cloneTarget[key] = clone(target[key]);
}
return cloneTarget;
} else {
returntarget; }};Copy the codeExecute the following test case in clone2.test.js:
const target = {
field1: 1.field2: undefined.field3: {
child: 'child'
},
field4: [2.4.8]};Copy the codeExecution Result:
OK, no problem, your code is one small step closer to qualifying.
A circular reference
Let’s execute the following test case:
const target = {
field1: 1.field2: undefined.field3: {
child: 'child'
},
field4: [2.4.8]}; target.target = target;Copy the codeYou can see the following results:
Obviously, the stack is out of memory because of recursion into an infinite loop.
The reason for this is that the above objects have circular references, that is, objects whose properties indirectly or directly refer to themselves:
Solve the problem of circular reference, we can create a extra storage space, to store the current objects and copy the object correspondence, when need to copy the current object, go to the storage space, find ever copy this object, if any direct return, if not to copy, so clever resolve problem of circular references.
This storage space needs to be able to store data in the form of key-value, and the key can be a reference type. We can choose the data structure Map:
- check
mapIs there any cloned object in the - Yes. – Straight back
- None – treats the current object as
key, clone objects asvalueFor storage - Continue to clone
function clone(target, map = new Map()) {
if (typeof target === 'object') {
let cloneTarget = Array.isArray(target) ? [] : {};
if (map.get(target)) {
return map.get(target);
}
map.set(target, cloneTarget);
for (const key in target) {
cloneTarget[key] = clone(target[key], map);
}
return cloneTarget;
} else {
returntarget; }};Copy the codeLet’s execute the above test case:
As you can see, no errors were reported, and the target attribute is now Circular, which means Circular.
Next, we can use WeakMap to make the code achieve the finishing point.
function clone(target, map = new WeakMap()) {
// ...
};
Copy the code
Why do we do that? Let’s look at the function of WeakMap first:
A WeakMap object is a set of key/value pairs where the keys are weakly referenced. The key must be an object, and the value can be arbitrary.
What is a weak reference?
In computer programming, a weak reference, as opposed to a strong reference, is a reference that does not guarantee that the object it references will not be reclaimed by the garbage collector. An object that is referenced only by weak references is considered inaccessible (or weakly accessible) and may therefore be reclaimed at any time.
We create a strong reference object by default: const obj = {}. We create a strong reference object by default. If we manually set obj = null, it will be collected by garbage collection.
Here’s an example:
If we use a Map, there is a strong reference between objects:
let obj = { name : 'ConardLi'}
const target = new Map(a); target.set(obj,'Code Secret Garden');
obj = null;
Copy the codeAlthough we manually release OBj, the target still has a strong reference to OBj, so this part of memory still cannot be freed.
Let’s look at WeakMap:
let obj = { name : 'ConardLi'}
const target = new WeakMap(a); target.set(obj,'Code Secret Garden');
obj = null;
Copy the codeIf it is a WeakMap, the target and OBj have a weak reference relationship. When the next garbage collection mechanism is executed, the memory will be freed.
Imagine that if the object we want to copy is very large, the use of Map will cause very large extra consumption on memory, and we need to manually clear the attributes of the Map to release the memory, and WeakMap will help us cleverly resolve this problem.
I also often see people using WeakMap to solve circular reference problems in some code, but the explanations are always ambiguous when you don’t know much about what WeakMap really does. I suggest you don’t write code like this in an interview either. You’ll end up digging yourself into a hole. Even in preparation for an interview, every line of code you write needs to be thought through and understood.
If you can take circular reference into account, you have shown the interviewer that you consider the comprehensibility of the problem. If you can also use WeakMap to solve the problem and clearly explain the purpose of doing so to the interviewer, then your code should be qualified in the eyes of the interviewer.
Performance optimization
In the above code, we use the for in method for traversing groups and objects. In fact, for in is very inefficient in traversing. Let’s compare the performance of the three common for, while and for in loops:
As you can see, while is the most efficient, so we can find a way to change the for in traversal to a while traversal.
Iteratee is a callback function that takes both the value and index parameters of each iteration:
function forEach(array, iteratee) {
let index = - 1;
const length = array.length;
while (++index < length) {
iteratee(array[index], index);
}
return array;
}
Copy the codeLet’s rewrite our cloen function: When iterating through the array, use forEach to iterate directly. When iterating through the Object, use object. keys to retrieve all the keys and then use the value of the forEach function as the key during the iterate:
function clone(target, map = new WeakMap()) {
if (typeof target === 'object') {
const isArray = Array.isArray(target);
let cloneTarget = isArray ? [] : {};
if (map.get(target)) {
return map.get(target);
}
map.set(target, cloneTarget);
const keys = isArray ? undefined : Object.keys(target);
forEach(keys || target, (value, key) => {
if (keys) {
key = value;
}
cloneTarget[key] = clone2(target[key], map);
});
return cloneTarget;
} else {
returntarget; }}Copy the codeNext, we run clone4.test.js to test the previous clone function and the rewritten clone function:
const target = {
field1: 1.field2: undefined.field3: {
child: 'child'
},
field4: [2.4.8].f: { f: { f: { f: { f: { f: { f: { f: { f: { f: { f: { f: {}}}}}}}}}}}},}; target.target = target;console.time();
const result = clone1(target);
console.timeEnd();
console.time();
const result2 = clone2(target);
console.timeEnd();
Copy the codeExecution Result:
It was clear that our performance tuning was working.
At this point, you’ve shown the interviewer that you think about efficiency when writing code, and that you have the ability to abstract generic functions.
Other data types
In the above code, we only consider the common data types object and array. In fact, there are many more reference types. Let’s first try to get the exact type of the object.
Determine the reference type reasonably
First, we need to consider two special data types: function and NULL:
function isObject(target) {
const type = typeof target;
returntarget ! = =null && (type === 'object' || type === 'function');
}
Copy the code if(! isObject(target)) {return target;
}
// ...
Copy the codeGetting the data type
We can use toString to get the exact reference type:
Every reference type has a toString method, and by default, the toString() method is inherited by every Object. If this method is not overridden in a custom object, toString() returns “[object type]”, where type is the type of the object.
Note that toString only works if this method is not overridden in the custom object. In fact, most reference types such as Array, Date, RegExp, and so on override the toString method.
We can call the unoverridden toString() method on the Object prototype directly, using call to redirect this to achieve the desired effect.
function getType(target) {
return Object.prototype.toString.call(target);
}
Copy the code
Let’s pull out some common data types for later use:
const mapTag = '[object Map]';
const setTag = '[object Set]';
const arrayTag = '[object Array]';
const objectTag = '[object Object]';
const boolTag = '[object Boolean]';
const dateTag = '[object Date]';
const errorTag = '[object Error]';
const numberTag = '[object Number]';
const regexpTag = '[object RegExp]';
const stringTag = '[object String]';
const symbolTag = '[object Symbol]';
Copy the codeIn the above set types, we simply divide them into two categories:
- Types that you can continue traversing
- A type that cannot be traversed
We make different copies of each of them.
Types that you can continue to iterate over
Object and Array are the types that can be traversed because they can store other types of data in memory. Map and Set are also the types that can be traversed. We only consider these types here.
To continue recursion, we first need to retrieve their initialization data, such as [] and {} above, which can be obtained generically using constructor.
For example, const target = {} is const target = new Object() syntax sugar. Another benefit of this approach is that since we also use the constructor of the original object, it preserves the data on the object stereotype, which would be lost if we just used the normal {}.
function getInit(target) {
const Ctor = target.constructor;
return new Ctor();
}
Copy the codeNext, let’s rewrite the Clone function to handle the data types we can continue traversing:
function clone(target, map = new WeakMap()) {
// Clone the original type
if(! isObject(target)) {return target;
}
/ / initialization
const type = getType(target);
let cloneTarget;
if (deepTag.includes(type)) {
cloneTarget = getInit(target, type);
}
// Prevent circular references
if (map.get(target)) {
return map.get(target);
}
map.set(target, cloneTarget);
/ / clone set
if (type === setTag) {
target.forEach(value= > {
cloneTarget.add(clone(value,map));
});
return cloneTarget;
}
/ / clone map
if (type === mapTag) {
target.forEach((value, key) = > {
cloneTarget.set(key, clone(value,map));
});
return cloneTarget;
}
// Clone objects and arrays
const keys = type === arrayTag ? undefined : Object.keys(target);
forEach(keys || target, (value, key) => {
if (keys) {
key = value;
}
cloneTarget[key] = clone(target[key], map);
});
return cloneTarget;
}
Copy the codeWe run clone5.test.js to test the following test case:
const target = {
field1: 1.field2: undefined.field3: {
child: 'child'
},
field4: [2.4.8].empty: null,
map,
set,
};
Copy the codeExecution Result:
There is no problem, the completion of the further step, let’s continue to deal with other types:
A type that cannot be traversed
The remaining types are uniformly classified as unprocessable data types, which we process in turn:
Bool, Number, String, String, Date, Error we can create a new object directly using the constructor and the original data:
function cloneOtherType(targe, type) {
const Ctor = targe.constructor;
switch (type) {
case boolTag:
case numberTag:
case stringTag:
case errorTag:
case dateTag:
return new Ctor(targe);
case regexpTag:
return cloneReg(targe);
case symbolTag:
return cloneSymbol(targe);
default:
return null; }}Copy the codeClone Symbol type:
function cloneSymbol(targe) {
return Object(Symbol.prototype.valueOf.call(targe)); } clone regular:function cloneReg(targe) {
const reFlags = /\w*$/;
const result = new targe.constructor(targe.source, reFlags.exec(targe));
result.lastIndex = targe.lastIndex;
return result;
}
Copy the codeThere are actually a lot of data types that I haven’t written about here, but if you’re interested you can explore and implement them.
Can write here, the interviewer has seen you to consider the problem of rigor, your understanding of variables and types, to THE JS API proficiency, I believe the interviewer has begun to admire you.
Cloning function
Finally, I singled out the cloning function separately. There is no practical application for cloning function, and it is not a problem for two objects to use a function that is located in the same address in memory. I took a look at lodash’s treatment of the function:
const isFunc = typeof value == 'function'
if(isFunc || ! cloneableTags[tag]) {return object ? value : {}
}
Copy the codeThere is no special processing done, but I have found that many interviewers are still keen to ask this question, and as far as I know, there are very few people who can write it down…
In fact, this method does not have any difficulty, the main is to investigate your grasp of the foundation of solid not solid.
First, we can distinguish down arrow functions from normal functions by the use of prototype. There is no prototype for arrow functions.
We can regenerate an arrow function directly using eval and the function string. Note that this method does not apply to normal functions.
We can use re to handle ordinary functions:
New Function ([arg1[, arg2[,…argN]],] functionBody) ¶
function cloneFunction(func) {
const bodyReg = / (? <={)(.|\n)+(? =})/m;
const paramReg = / (? < = \ () + (? =\)\s+{)/;
const funcString = func.toString();
if (func.prototype) {
console.log('Ordinary function');
const param = paramReg.exec(funcString);
const body = bodyReg.exec(funcString);
if (body) {
console.log('Match to function body:', body[0]);
if (param) {
const paramArr = param[0].split(', ');
console.log('Match to parameter:', paramArr);
return new Function(... paramArr, body[0]);
} else {
return new Function(body[0]); }}else {
return null; }}else {
return eval(funcString); }}Copy the codeFinally, we run clone6.test.js to test the following test cases:
const map = new Map(a); map.set('key'.'value');
map.set('ConardLi'.'Code Secret Garden');
const set = new Set(a); set.add('ConardLi');
set.add('Code Secret Garden');
const target = {
field1: 1.field2: undefined.field3: {
child: 'child'
},
field4: [2.4.8].empty: null,
map,
set,
bool: new Boolean(true),
num: new Number(2),
str: new String(2),
symbol: Object(Symbol(1)),
date: new Date(),
reg: /\d+/.error: new Error(),
func1: (a)= > {
console.log('Code Secret Garden');
},
func2: function (a, b) {
returna + b; }};Copy the codeExecution Result:
The last
For better reading, let’s use a diagram to show all of the above code:
Complete code: github.com/ConardLi/Co…
As you can see, a small deep copy is still hiding a lot of knowledge.
Don’t ask for the bare minimum. If you’re trying to answer a single question in an interview, you’ll probably only use the bare-bone deep copy above.
But the interviewer is looking at you to see how you think in all directions, so if you write the code above, you can show your versatility:
- Basic implementation
- Recursive ability
- A circular reference
- Consider all aspects of the problem
- Understand the true meaning of WeakMap
- A variety of types
- Consider the rigor of the problem
- Create various reference types of methods, JS API proficiency
- Accurately judge the data type and understand the data type
- General traversal:
- Code can be written with performance tuning in mind
- Understand the efficiency of centralized traversal
- Code abstraction
- Copy function:
- The difference between an arrow function and a normal function
- Regular expression proficiency
See, there’s so much that can be said about you in a small deep copy, and how can an interviewer not be impressed when they see this code?
In fact, you can use this idea to consider all the questions the interviewer gives you. Don’t memorize code for the interview because it will be exposed to an experienced interviewer. Every piece of code you write has to be thought through, why it’s used the way it is, and how it can be optimized… This will give the interviewer the best of you.
reference
- WeakMap
- lodash
summary
Hopefully, after reading this article, you have found the following helpful:
- Understand the true meaning of depth copy
- I can deep copy the various points, in-depth analysis of the problem
- Write a complete deep copy by hand
Feel free to correct any mistakes in the comments section, and if this post has helped you, feel free to like or follow.
For more great articles, you can follow me on github blog, and your star✨, like and follow is what keeps me creating!
I recommend you to follow my wechat public account [Code Secret Garden] and push high-quality articles every day. We communicate and grow together.
We are the r&d team of Bytedance Interactive Entertainment, including Douyin short video, Douyin Volcano version, TikTok, Faceu, Xiaoyan, cut and so on. As of January 2020, Douyin daily active users (DAUs) have exceeded 400 million, and continue to maintain high growth. You will support product development and related architecture, and each line of code will affect millions of users.
Class of 2021: DRZUM5Z
Website delivery: job.toutiao.com/s/JR8SthH