preface

Deep copy is often used in development, especially when manipulating data of reference type. It is usually used to assign a value to a variable first, and then operate on it to prevent affecting other places where the data is used.

How to achieve a deep copy, in the interview frequency has been high. Because in implementing a deep copy, you can see a lot of things about a candidate.

This column will show you how to implement a deep copy, from bronze to king, and the capabilities associated with each rank.

Bronze grade

JSON.parse(JSON.stringify(data))
Copy the code

This is simple and works for most applications, but it has major drawbacks. If you don’t know what the flaws are, and the implementation doesn’t say anything about you, it’s in the bronze class.

  • A deep copy cannot be implemented correctly if there is a circular reference in the object.
const a = {
    b: 1,
}
a.c = a;
JSON.parse(JSON.stringify(a));
Copy the code

  • ifdataIf there’s a time object in it, thenJSON.stringifyAfter theJSON.parseThe result of the time will just be in the form of a string. Not a time object.
const a = {
    b: new Date(1536627600000),
}
console.log(JSON.parse(JSON.stringify(a)))
Copy the code

  • ifdataIf there are RegExp and Error objects in the string, the serialization result will be an empty object.
Const a = {b: new RegExp(/\d/), c: new Error(' Error ')} console.log(json.parse (json.ify (a)))Copy the code

  • ifdataI have the function,undefined, the result of the serialization will make the function undefined or missing;
const a = {
    b: function (){
        console.log(1)
    },
    c:1,
	d:undefined
}
console.log(JSON.parse(JSON.stringify(a)))
Copy the code

  • ifdataIf NaN, Infinity, and -infinity are in the string, the serialized result will be null
Const a = {b: NaN, c: 1.7976931348623157E+10308, d: 1.7976931348623157 e+10308,} the console. The log (JSON. Parse (JSON. Stringify (a)))Copy the code

The silver grade

The core of a deep copy is copying data of reference types.

function deepClone(target){ if(target ! == null && typeof target === 'object'){ let result = {} for (let k in target){ if (target.hasOwnProperty(k)) { result[k]  = deepClone(target[k]) } } return result; }else{ return target; }}Copy the code

In the above code, the target parameter to the deepClone function is the data to be deep copied.

Perform the target! == null && typeof target === ‘object’ Determines whether target is a reference type.

If not, return target.

If so, create a variable result as the result of the deep copy, iterate over the target, execute deepClone(target[k]) and assign the value of each attribute of the target to the corresponding attribute result[k] of the result of the deep copy. Return result after the traversal is complete.

In deepClone(target[k]), the target[k] type is determined, and the above process is repeated, resulting in a recursive call to deepClone function. The deepClone function will be called to assign a value to the property of the result of the deep copy, no matter how many sub-attributes there are in the data.

Also use for… When the in loop iterates over the properties of an object, all properties on its stereotype chain are accessed. If you want to iterate over only the properties of the object itself, and not the properties inherited from the stereotype chain, use the hasOwnProperty method to filter this.

Here are three programming skills you can show the interviewer.

  • Ability to judge raw and reference type data.
  • The ability to apply recursive thinking.
  • Deep understanding offor... inThe use of.

Gold grade

The silver segment code only considers the case that the data of the reference type is an object, leaving out the case that the data of the reference type is an array.

function deepClone(target){
    if(target !== null && typeof target === 'object'){
        let result = Object.prototype.toString.call(target) === "[object Array]" ? [] : {};
        for (let k in target){
            if (target.hasOwnProperty(k)) {
                result[k] = deepClone(target[k])
            }
        }
        return result;
    }else{
        return target;
    }
}
Copy the code

In the above code, we just added the additional judgment of whether the target parameter is an array. Execution of the Object. The prototype. ToString. Call (target) = = = “[Object Array]” judgment target is an Array, and if the Array, variable result for [], if it is not an Array, variable result for {}.

This is where you can show the interviewer two of your programming skills.

  • The ability to properly understand the concept of reference types.
  • The ability to accurately determine data types.

Platinum Dan

Suppose you want to deep copy the following data: data

let data = {
    a: 1
};
data.f=data
Copy the code

performdeepClone(data)The console will report an error, as shown below.

This is because the stack is out of memory due to recursion into an infinite loop. The root cause is circular references to data, where an object’s attributes refer to itself indirectly or directly.

function deepClone(target) { function clone(target, map) { if (target ! == null && typeof target === 'object') { let result = Object.prototype.toString.call(target) === "[object Array]" ? [] : {}; if (map[target]) { return map[target]; } map[target] = result; for (let k in target) { if (target.hasOwnProperty(k)) { result[k] = clone(target[k],map) } } return result; } else { return target; } } let map = new Map(); const result = clone(target, map); map.clear(); map = null; return result }Copy the code

In the above code, an additional variable map is used to store the mapping between the current object and the copied object. When you need to copy the current object, first go to the map to find whether the object has been copied. If so, return directly, if not, continue to copy.

Map data structure in ES6 is used because, compared with ordinary Object structure, its key value is not limited to strings, and all types of values (including objects) can be used as keys. In other words. The Object structure provides the “string — value” correspondence, and the Map structure provides the “value — value” correspondence. If target is not a string, then all of its keys are [Object Object], causing confusion.

Finally, you need to execute map.clear(); map = null; , free memory to prevent memory leaks.

Here are three programming skills you can show the interviewer.

  • An understanding of circular references and the ability to solve problems caused by circular references.
  • Familiar with the concept and application of Map data structure in ES6
  • Awareness of memory leaks and ability to avoid them.

Dan masonry

At this stage, performance issues should be considered. Map was used above to solve the circular reference problem. But do execute map.clear() at the end; map = null; , free memory to prevent memory leaks.

WeakMap can also be used to resolve circular references. There are two differences between WeakMap data structure and Map data structure:

  • WeakMap only accepts objects as key names (except null) and does not accept other types of values as key names. But target meets the requirements so it doesn’t matter.

  • The object pointed to by the key name of a WeakMap is not included in the garbage collection mechanism. This is illustrated by the following example.

let map = new WeakMap();
let obj = {a : 1}
map.set(obj , 1);
Copy the code

The GC collection policy of modern browsers is to calculate the number of references. That is, the number of references to an object is 1, because the reference between the key name obj and the object obj in the map is weak. That is, the number of references to object obj is 1 without counting the number of references. When obj = null is executed, the number of references to object obj becomes 0 during GC collection, so the memory occupied by object obj will be freed.

Obj = null; obj = null; obj = null; obj = null; obj = null; obj = null Therefore, the memory occupied by OBj cannot be freed.

So using WeakMap can prevent memory leaks caused by forgetting to set the map to NULL. However, is WeakMap a weak reference only to prevent memory leaks? When obj = null, the object obj is reclaimed by GC, but map.get(obj) still returns the value 1. We can take advantage of this feature to do some performance tuning.

In deep copy code. The copied object is used as the key name, and when the copied object is very large, the map takes up a lot of memory.

If the map uses a map data structure, because the objects referenced by the map key names are strongly referenced, the memory used by the copied objects can only be freed unless the map key-value pair is manually cleared when GC is performed by the browser.

If Map uses WeakMap data structure, because the object referenced by the key name of WeakMap is a weak reference, so the browser will regularly perform GC collection, which will directly release the memory occupied by the copy object, so it is not to reduce the memory usage, and indirectly optimize the code running performance.

In addition, in the above code, we use for to walk through groups and objects… In this way, in fact, for… In is very inefficient in traversal, so while is more efficient in traversal.

Function deepClone (target) {/ * * * * @ array traversal data processing function of data to be processed * @ callback callbacks, accepts two parameters of the value of the value of each index each subscript or key. */ function handleWhile(array, callback) { const length = array.length; let index = -1; while (++index < length) { callback(array[index], index) } } function clone(target, map) { if (target ! == null && typeof target === 'object') { let result = Object.prototype.toString.call(target) === "[object Array]" ? [] : {}; If (map.has(target)) {return map.get(target); } map.set(target, result); const keys = Object.prototype.toString.call(target) === "[object Array]" ? undefined : Object.keys( target); Function callback(value, key) {if (key) {// callback(value, key) {if (key) {// callback(value, key) {// callback(value, key) { key = value; } result[key] = clone(target[key], map) } handleWhile(keys || target, callback) return result; } else { return target; } } let map = new WeakMap(); const result = clone(target,map); map = null; return result }Copy the code

“DeepClone” for “while” and “for” for… In The deep copy traversed is denoted as deepClone1. Use console.time() and console.timeend () to calculate the execution time.

let arr = [];
for (let i = 0; i < 1000000; i++) {
    arr.push(i)
}
let data = {
    a: arr
};
console.time();
const result = deepClone(data);
console.timeEnd();
console.time();
const result1 = deepClone1(data);
console.timeEnd();
Copy the code

It is clear from the figure above that deep copies traversed by while perform much better than for… In Deep copy of traversal.

Here are five ways to show your interviewer your programming skills.

  • Familiar with concept and application of WeakMap data structure in ES6
  • Ability to optimize code performance.
  • The ability to understand the efficiency of traversal.
  • To understand++i 和 i++The difference between.
  • The ability to abstract code.

Star yao Dan

The rigor of your code logic should be considered at this stage. Although the above section of the code has met the usual development needs, but there are still a few logical irregularities.

  • If the data type is not a reference type, return target directly. However, there is also a special type of Symbol in the original type. Because each Symbol is unique, it requires additional copying and cannot be returned directly.

  • Typeof target === function’;

  • Only the processing of the data of Array and Object reference types is considered. The data of reference types include Function Function, Date, RegExp, Map data structure, and Set data mechanism, among which Map and Set belong to ES6.

Without further comment, just post the entire code, with comments in it.

The function deepClone (target) {/ / function to get the data type getType (target) {return Object. The prototype. ToString. Call (target)} Function isObject(target) {return target! == null && (typeof target === 'object' || typeof target === 'function'); } function handleOherData(target) {const type = getType(target); switch (type) { case "[object Date]": return new Date(target) case "[object RegExp]": return cloneReg(target) case "[object Function]": Return cloneFunction(target)}} function cloneSymbol(targe) {const a = String(targe); Const b = a.substring(7, a.length-1); Return Symbol(b); // Return Symbol(b); Function cloneReg(target) {const reFlags = /\w*$/;}} function cloneReg(target) {const reFlags = /\w*$/; const result = new target.constructor(target.source, reFlags.exec(target)); result.lastIndex = target.lastIndex; return result; } function cloneFunction(targe) {const bodyReg = /(? <={)(.|\n)+(? =})/m; // Match the regular const paramReg = /(? < = \ () + (? =\)\s+{)/; const targeString = targe.toString(); Const param = paramreg.exec (const param = paramreg.exec (const param = paramreg.exec (const param = paramreg.exec (const param = paramreg.exec)); const body = bodyReg.exec(targeString); if (body) { if (param) { const paramArr = param[0].split(','); Return new Function(...) paramArr, body[0]); } else { return new Function(body[0]); } } else { return null; }} else {return eval(targeString); }} /** * iterates through the data handler * @array * @callback, receiving the value of each item (value) and the index or key of each item (index). */ function handleWhile(array, callback) { let index = -1; const length = array.length; while (++index < length) { callback(array[index], index); } } function clone(target, map) { if (isObject(target)) { let result = null; if (getType(target) === "[object Array]") { result = [] } else if (getType(target) === "[object Object]") { result = {} } else if (getType(target) === "[object Map]") { result = new Map(); } else if (getType(target) === "[object Set]") { result = new Set(); } // Resolve circular references if (map.has(target)) {return map.get(target); } map.set(target, result); if (getType(target) === "[object Map]") { target.forEach((value, key) => { result.set(key, clone(value, map)); }); return result; } else if (getType(target) === "[object Set]") { target.forEach(value => { result.add(clone(value, map)); }); return result; } else if (getType(target) === "[object Object]" || getType(target) === "[object Array]") { const keys = getType(target)  === "[object Array]" ? undefined : Object.keys(target); Function callback(value, key) {if (key) {// callback(value, key) {if (key) {// callback(value, key) {// callback(value, key) { key = value } result[key] = clone(target[key], map) } handleWhile(keys || target, callback) } else { result = handleOherData(target) } return result; } else { if (getType(target) === "[object Symbol]") { return cloneSymbol(target) } else { return target; } } } let map = new WeakMap; const result = clone(target, map); map = null; return result }Copy the code

Here are six programming skills you can show your interviewer.

  • The rigor of the code logic.
  • The ability to gain insight into data types.
  • The ability to skillfully use the JS Api.
  • Understand the difference between an arrow function and a normal function.
  • Proficiency in using regular expressions.
  • The ability to modular development

Dan king

There are many copies of data types in the above code, not implemented, interested words can be realized in the comments, king belongs to you!

conclusion

To sum up, when an interviewer asks you to implement a deep copy, he or she is actually testing your abilities in a variety of ways. For example,

  • The silver grade
    • Ability to judge raw and reference type data.
    • The ability to apply recursive thinking.
  • Gold grade
    • The ability to properly understand the concept of reference types.
    • The ability to accurately determine data types.
  • Platinum Dan
    • An understanding of circular references and the ability to solve problems caused by circular references.
    • Familiar with the concept and application of Map data structure in ES6.
    • Awareness of memory leaks and ability to avoid them.
  • Dan masonry
    • Familiar with concept and application of WeakMap data structure in ES6.
    • Ability to optimize code performance.
    • The ability to understand the efficiency of traversal.
    • To understand++i 和 i++The difference between.
    • The ability to abstract code.
  • Star yao Dan
    • The rigor of the code logic.
    • The ability to gain insight into data types.
    • The ability to skillfully use the JS Api.
    • Understand the difference between an arrow function and a normal function.
    • Proficiency in using regular expressions.
    • The ability to modular development

So instead of cramming hand-written interview questions, write them yourself and see where you stand.