Categories
Uncategorized

US JavaScript data structures and algorithms – The stack memory and heap memory, deep and shallow copy copy

Foreword

I want to write front-end, first Lianhaoneigong.

Stack memory and heap memory, shallow copy and deep copy, the programmer can be said that the front end of the internal organs, to know, know why.

The author wrote the US data structures and algorithms of the series with JavaScript language is JavaScript, aimed at entry-after data structures and algorithms and easy review.

Stack

definition

    Last in, first out, advanced after a person, referred to last in first out (LIFO), which is a typical stack structure.

    The newly added elements are to be deleted or stored at the end of the stack, called the top of the stack, and the other end is called the bottom of the stack.

    In the stack, new elements are close to the top of the stack, old elements are close to the bottom of the stack.

    From the point of view of operational characteristics of the stack, the operation is a restricted linear form, insert and delete data only at one end.

    It does not contain any element of the stack called empty stack.

Stack also be used in programming languages ​​and compilers save variables in memory, such as method calls, such as call stack function.

stack

definition

    Heap data structure is a tree structure.
            Its way to access the data, and the book is very similar to the shelves. We do not care about the book is how to place the order, just know the name of the book can be taken out of the book we want.
            In like JSON-formatted data, we stored key-value is disordered, long known key, the key can be removed corresponding to the value.

Compared with the stack

    The heap is dynamically allocated memory, memory sizes, it will not automatically released.

    The stack is automatically assigned a relatively fixed amount of memory space, it is automatically released by the system.

    Stack, linear structure, LIFO, easy to manage.

    Heap, a chaotic, disorganized, convenience store and open up memory space.

Stack memory and heap memory

In JavaScript variables into basic types and reference types.

  • Simple basic types of data segments stored in the stack memory, their values ​​have a fixed size, saving space in the stack, and automatic allocation values ​​by pressing the automatic release access by the system.
                Such benefits is that memory can be recovered in time, relative to the stack, the more easily manage memory space.
                JavaScript is Boolean, Null, Undefined, Number, String, Symbol are the basic types.

  • Reference type (e.g., an object, an array, functions, etc.) the object is stored in the heap memory, the size of the value is not fixed, the object access address stored in the stack memory heap memory pointing object, JavaScript does not allow direct access to the heap position, and therefore the operation object that references the actual object operation.
                In JavaScript Object, Array, Function, RegExp, Date is a reference type.

Described with examples

let a1 = 0; // 栈内存
let a2 = "this is string" // 栈内存
let a3 = null; // 栈内存
let b = { x: 10 }; // 变量 b 存在于栈中,{ x: 10 } 作为对象存在于堆中
let c = [1, 2, 3]; // 变量 c 存在于栈中,[1, 2, 3] 作为对象存在于堆中

When the reference data types we want to access the heap memory

    1. Gets the object from the stack address reference

    1. Then we need to get data from the heap

Basic types of replication occurs

let a = 20;
let b = a;
b = 30;
console.log(a); // 20

When the data in the stack memory replication behavior occurs, the system automatically assigned to the new variable a new value, the last of these variables are independent of each other, they affect each other.

Reference type replication occurs

let a = { x: 10, y: 20 }
let b = a;
b.x = 5;
console.log(a.x); // 5

    Reference type of replication, the same new variable b is assigned a new value, is stored in the stack memory, the difference is, the address pointer value is only a reference type.

    Both of them point to the same value, which is the same as the address pointer, access to specific objects in the heap memory is actually the same.

    Therefore change b.x, a.x also changed, which is a reference to the type of characteristics.

Understood in conjunction with the FIG.

to sum up

Stack memory

Heap

Storing basic data types

Storing reference data types

Access by value

Access by Reference

A fixed storage size value

Variable size stored values, can be dynamically adjusted

Automatically by the system allocates memory space

Specified by the code assigned

Small space, high operating efficiency

Space, relatively low operating efficiency

Last-out, LIFO

Storage disorder, reference can be directly obtained according to

Shallow copy and deep copy

Mentioned above referenced type of copy is shallow copy, copy the resulting access point to the same memory address space. Therefore, one of which is the modified value, the additional change too.

Deep Copy: copy the resulting access point to a different memory address space, independent of each other. So modify a value, the other does not change.

When the array replication normal use, most of us will use =, this is just a shallow copy, there are many problems. such as:

let arr = [1,2,3,4,5];
let arr2 = arr;
console.log(arr) //[1, 2, 3, 4, 5]
console.log(arr2) //[1, 2, 3, 4, 5]
arr[0] = 6;
console.log(arr) //[6, 2, 3, 4, 5]
console.log(arr2) //[6, 2, 3, 4, 5]
arr2[4] = 7;
console.log(arr) //[6, 2, 3, 4, 7]
console.log(arr2) //[6, 2, 3, 4, 7]

Obviously, the shallow copy, and the copy is copied each array are affected.

Therefore, there must be a way to not be affected, and that is a deep copy.

Deep copy of the copy process

let a = { x: 10, y: 20 }
let b = JSON.parse(JSON.stringify(a));
b.x = 5;
console.log(a.x); // 10
console.log(b.x); // 5

Array

A, for circulation

//for 循环 copy
function copy(arr) {
    let cArr = []
    for(let i = 0; i < arr.length; i++){
      cArr.push(arr[i])
    }
    return cArr;
}
let arr3 = [1,2,3,4];
let arr4 = copy(arr3) //[1,2,3,4]
console.log(arr4) //[1,2,3,4]
arr3[0] = 5;
console.log(arr3) //[5,2,3,4]
console.log(arr4) //[1,2,3,4]

Two, slice method

//slice实现深拷贝
let arr5 = [1,2,3,4];
let arr6 = arr5.slice(0);
arr5[0] = 5;
console.log(arr5); //[5,2,3,4]
console.log(arr6); //[1,2,3,4]

Three, concat method

//concat实现深拷贝
let arr7 = [1,2,3,4];
let arr8 = arr7.concat();
arr7[0] = 5;
console.log(arr7); //[5,2,3,4]
console.log(arr8); //[1,2,3,4]

Four, es6 extended operation

//es6 扩展运算实现深拷贝
let arr9 = [1,2,3,4];
let [...arr10] = arr9;
arr9[0] = 5;
console.log(arr9) //[5,2,3,4]
console.log(arr10) //[1,2,3,4]

Five, JSON.parse and JSON.stringify

let arr9 = [1,2,3,4];
let arr10 = JSON.parse(JSON.stringify(arr9))
arr9[0] = 5;
console.log(arr9) //[5,2,3,4]
console.log(arr10) //[1,2,3,4]

Note: In the process a greater amount of data, there will be a performance problem.

Objects

First, the circulation of objects

//  循环 copy 对象
let obj = {
    id:'0',
    name:'king',
    sex:'man'
}
let obj2 = copy2(obj)
function copy2(obj) {
    let cObj = {};
    for(var key in obj){
      cObj[key] = obj[key]
    }
    return cObj
}
obj2.name = "king2"
console.log(obj) // {id: "0", name: "king", sex: "man"}
console.log(obj2) // {id: "0", name: "king2", sex: "man"}

Two, JSON.parse and JSON.stringify

var obj1 = {
    x: 1, 
    y: {
        m: 1
    },
    a:undefined,
    b:function(a,b){
      return a+b
    },
    c:Symbol("foo")
};
var obj2 = JSON.parse(JSON.stringify(obj1));
console.log(obj1) //{x: 1, y: {m: 1}, a: undefined, b: ƒ, c: Symbol(foo)}
console.log(obj2) //{x: 1, y: {m: 1}}
obj2.y.m = 2; //修改obj2.y.m
console.log(obj1) //{x: 1, y: {m: 1}, a: undefined, b: ƒ, c: Symbol(foo)}
console.log(obj2) //{x: 1, y: {m: 2}}

Deep copies can be multi-dimensional objects.

Note: for the JSON.stringify () of the process sequence, undefined, functions, and any value symbol, in the sequence of the process will be ignored (occurs when a property value array of non-object) or is converted into null (appears in an array).

Three, es6 extended operation

let obj = {
    id:'0',
    name:'king',
    sex:'man'
}
let {...obj4} = obj
obj4.name = "king4"
console.log(obj) //{id: "0", name: "king", sex: "man"}
console.log(obj4) //{id: "0", name: "king4", sex: "man"}

Four, Object.assign ()

Object.assign () can only achieve a deep copy-dimensional object.

var obj1 = {x: 1, y: 2}, obj2 = Object.assign({}, obj1);
console.log(obj1) // {x: 1, y: 2}
console.log(obj2) // {x: 1, y: 2}

obj2.x = 2; // 修改 obj2.x
console.log(obj1) // {x: 1, y: 2}
console.log(obj2) // {x: 2, y: 2}

var obj1 = {
    x: 1, 
    y: {
        m: 1
    }
};
var obj2 = Object.assign({}, obj1);
console.log(obj1) // {x: 1, y: {m: 1}}
console.log(obj2) // {x: 1, y: {m: 1}}

obj2.y.m = 2; // 修改 obj2.y.m
console.log(obj1) // {x: 1, y: {m: 2}}
console.log(obj2) // {x: 2, y: {m: 2}}

General Method deep copy

Simple version

let clone = function (v) {
    let o = v.constructor === Array ? [] : {};
    for(var i in v){
      o[i] = typeof v[i] === "object" ? clone(v[i]) : v[i];
    }
    return o;
}
// 测试
let obj = {
    id:'0',
    name:'king',
    sex:'man'
}
let obj2 = clone(obj)
obj2.name = "king2"
console.log(obj) // {id: "0", name: "king", sex: "man"}
console.log(obj2) // {id: "0", name: "king2", sex: "man"}

let arr3 = [1,2,3,4];
let arr4 = clone(arr3) // [1,2,3,4]
arr3[0] = 5;
console.log(arr3) // [5,2,3,4]
console.log(arr4) // [1,2,3,4]

But deep copy of the above method encounters a circular reference, recursive process will fall into a cycle, resulting explosion stack, so to avoid.

let obj1 = {
    x: 1, 
    y: 2
};
obj1.z = obj1;
let obj2 = clone(obj1);
console.log(obj2) 

The results are as follows:

Summary: a deep understanding of the depth of copies javascript, you can use a flexible array of objects, and can avoid a lot of bug.

7. Finally

All of the text in the code and test cases have been put up on my GitHub.

If you find it useful or the like, on the point of collection, like the way a point of it, your support is my greatest encouragement!

Reference article:

JavaScript stack memory and heap memory
    JavaScript implementation method deep shallow copy copy Analysis
    Shallow copy and deep copy (JavaScript)

Leave a Reply