对象拷贝、函数柯里化、防抖节流、数组扁平化、数组去重

JavaScript进阶（三）JavaScript经典算法

一、对象拷贝

首先需要了解两个概念：数据类型、数据占用的内存空间

JS的基本数据类型有6种：number、string、boolean、null、undefined、symbol

剩下的都可以归为一类object，包括：array、set、map等等

基本数据类型因为占据空间小、大小固定，属于被频繁使用数据，所以放入栈中存储。

object引用类型因为占据空间大、大小不固定。如果存储在栈中，将会影响程序运行的性能；所以储存在堆中，堆中的地址放到栈里面，变量赋值得到的实际上是一个地址指针（指向堆）

赋值，就是直接将object变量赋值给另外一个变量，两者共同同一个对象（同一块堆内存）

浅拷贝，就是将第一层的对象，在堆内存中复制另外一份，但是对象里面嵌套的对象并没有复制，所以内部嵌套的对象仍然是共享的

深拷贝，就是将所有层的对象，都在堆内存中复制新的一份，所有对象不在共享。

1.1、浅拷贝

1.1.1 已有的方法

//针对Array数组
var arr = [1,2,[3,4]]
var arr1 = arr.slice()	//浅拷贝
var arr2 = arr.concat()	//浅拷贝

//针对对象
var obj = {a:1,b:{c:2}}
var obj1 = Object.assign({},obj) //使用Object.assign()
var obj2 = {...obj}				//使用解构赋值

1.1.2 手写浅拷贝函数

需要考虑对象中包含Function函数、RegExp正则表达式、Date日期、Map、Set的情况

function shallowClone(target){
    if(target && typeof target === 'object'){
        if(/^(function|regexp|date|map|set)$/i.test(target.constructor.name)){
            return new target.construcotr(target)
        }
        let result = Array.isArray(target)?[]:{}
        for(key in target){
            result[key] = target[key]
        }
    }else{
        return target
    }
}

1.2、深拷贝

1.2.1 简单的深拷贝

如果可以保证对象中只包含基本类型、数组、常规对象，那么就可以使用JSON序列化和反序列化的过程进行深拷贝。这种方法不支持含有函数、RegExp、Date对象、undefined类型的对象

function deepColne(obj) {
  return JSON.parse(JSON.stringify(obj))
}
//JSON.stringify()：将JS对象转换为JSON字符串
//JSON.parse()：将JSON字符串解析为对应的JS值或对象

1.2.2 手写深拷贝函数

深拷贝与浅拷贝的区别在于，如果对象的属性依然是Object类型，那么需要将对象的属性也拷贝一遍。需要通过递归来实现

同样需要考虑对象中包含Function函数、RegExp正则表达式、Date日期、Map、Set的情况。

同时还需要考虑对象属性中循环引用的问题

/**
* param {Objcet} target 要拷贝到对象
* param {Map} map 用于储存循环引用对象的地址，防止递归中出现环造成内存泄漏
*/
function deepClone(target={},map=new Map){
    if(target===null || typeof target !== 'object') return target
    if(/^(function|regexp|date|set|map)$/i.test(target.constructor.name)){
        return new target.constructor(target)
    }
    if(map.get(target)) return map.get(target)
    let result = Array.isArray(target)?[]:{}
    map.set(target,result)	//只有object对象或者Array数组，才可能存在循环引用，所以只有这两种类型的属性要保存到map中
    for(key in target){
        result[key] = deepClone(target[key])
    }
    return result
}

二、函数柯里化

柯里化（currying）指的是将一个多参数的函数拆分成一系列函数，每个拆分后的函数都只接受一个参数（unary）。利用闭包形成了一个保存在内存中的作用域，把接收到的部分参数保存在这个作用域中，等待后续使用。并且返回一个新函数接收剩余参数

柯里化思想：降低适用范围，提高适用性

函数柯里化的作用

• 参数复用，把前面部分参数相同的函数，封装成一个新的函数
• 提前返回
• 延迟执行

具体应用场景的案例参考：前端面试手写代码——函数柯里化 - 知乎 (zhihu.com)

前置知识

var fn = function (a, b, c) {return a + b + c}
fn.length	//3，代表形参的数量

2.1 手写柯里化函数

function curryIt(fn){
    let args = []
    
    return function curried(arg){		//每次只接受一个参数
        args.push(arg)
        if(args.length >= fn.length){
            return fn.apply(this,args)	//如果参数数量已经足够了，调用fn函数计算结果并返回
        }else{
            return function(arg2){
                return curried.call(this,arg2)	//如果参数数量还不够，返回一个函数，递归调用curried
            }
        }
    }
}
var fn = (a,b,c) => a+b+c
curryIt(fn)(1)(2)(3)	//6

//上面的柯里化函数，每次只接受一个参数。这里扩展一下：每次可以接受不定数量的参数
function curryIt(fn){
    let args = []
    return function curried(){
        args = args.concat(...arguments)	//这里的arguments是函数curried的参数对象
        if(args.length>=fn.length){
            return fn.apply(this,args)
        }else{
            return function(){
                return curried.apply(this,arguments)	//注意：这里的arguments是匿名函数的
            }
        }
    }
}
var fn = (a,b,c) => a+b+c
curryIt(fn)(1,2)(3)	//6

2.2 利用bind实现柯里化

利用 bind()方法 创建偏函数。关于 bind 更多的细节，请参考：《JavaScript进阶（四）手写JS经典函数》

function curryIt(fn){
    return function fun(a){
        if(fn.length===1) return fn(a)
        fn = fn.bind(this,a)
        return fun
    }
}
var fn = (a,b,c) => a+b+c
curryIt(fn)(1)(2)(3)	//6

//扩展：让fun接受不定数量的参数
function curryIt(fn){
    return function fun(){
        if(fn.length===1) return fn(arguments[0])
        fn = fn.bind(this,...arguments)
        return fun
    }
}
var fn = (a,b,c) => a+b+c
curryIt(fn)(1,2)(3)	//6

三、防抖节流

在前端开发的过程中，我们经常会需要绑定一些持续触发的事件，如 resize、scroll、mousemove 等等，但有些时候我们并不希望在事件持续触发的过程中那么频繁地去执行函数。

关键词：闭包、事件监听、setTimeout、setInterval

节流与防抖的前提都是某个行为持续地触发

节流就是减少执行次数，实现的方式是对于连续触发的事件一段时间内执行一次回调函数

防抖就是只执行一次，实现的方式是在连续触发事件结束后一段时间执行一次回调函数

3.1、防抖

适用场景：搜索框输入、手机号输入检测

场景实例演示，可以参看本地文件【Projects/前端练习/防抖节流.html】

核心在于：setTImeout的使用

3.1.1 动作结束后执行

触发动作时，设置定时器，如果两段触发之间的间隔小于指定时间（如1s），定时器刷新、重新计时。如果停止触发超过指定时间（如1s），执行回调函数

<div class="content">1</div>
<script>
    const display = document.getElementsByClassName('content')[0]
	var num = 1
    function count(){
        display.innerHTML = num++
    }
    function debounce(fn,wait){//翻译：去抖动
        let timeout
        return function(){	//返回一个函数，事件触发点时候，执行它
            const context = this
            const args = arguments
            if(timeout){clearTimeout(timeout)}	//如果距离上一次触发wait时间内，又触发了事件回调，中断定时器事件
            timeout = setTimeout(()=>{			//并重新设置定时器事件
                fn.apply(context,args)
            },wait)
        }
    }
    display.addEventListener('mousemove',debounce(count,1000))
</script>

3.1.2 动作开始时执行

<div class="content">1</div>
<script>
    const display = document.getElementsByClassName('content')[0]
	var num = 1
    function count(){
        display.innerHTML = num++
    }
    function debounce(fn,wait){//翻译：去抖动
        let timeout = null
        return function(){	//返回一个函数，事件触发点时候，执行它
            if(timeout){clearTimeout(timeout)}	//如果距离上一次触发wait时间内，又触发了事件回调，中断定时器事件
            let callNow = !timeout		//第一次执行时，timeout还没被赋值，所以 !timeout 为真
            if(callNow){
                fn.apply(this,arguments)
            }
            timeout = setTimeout(()=>{			
                timeout = null			//只有两次触发之间的间隔大于wait，timeout才会被重置。这里timeout相当于限制位
            },wait)
        }
    }
    display.addEventListener('mousemove',debounce(count,1000))
</script>

3.2、节流

适用场景：滚动加载、搜索框联想

3.2.1 时间戳版本

<div class="content">1</div>
<script>
	const display = document.getElementsByClassName('content')[0]
	var num = 1
    function count(){
        display.innerHTML = num++
    }
    function throttle(fn,interval){//翻译：节流阀
        let pre = 0
        return function(){
            const now = Date.now()
            if(now-pre>interval){
                fn.apply(this,arguments)
                pre = now
            }
        }
    }
    display.addEventListener('mousemove',throttle(count,500))
</script>

触发事件时，立即执行。触发事件停止后不再执行。连续触发过程中间隔interval执行一次回调函数

3.2.2 定时器版本

<div class="content">1</div>
<script>
	const display = document.getElementsByClassName('content')[0]
	var num = 1
    function count(){
        display.innerHTML = num++
    }
    function throttle(fn,interval){//翻译：节流阀
        let timeoutId = null
        
        return function(){
            if(!timeoutId){
                const context = this
                const args = arguments
                timeoutId = setInterval(()=>{
                    clearInterval(timeoutId)
                    fn.apply(context,args)
                    timeoutId = null
                },interval)
            }
        }
    }
    
    //相比于上面，直接把throttle()塞进addEventListener的写法，下面这种写法可能更好理解
    //实际上，事件回调函数式throttle()返回的那个函数，而不是throttle
    //也就是说，每次事件触发时，执行的是throttle()返回的那个函数，而不是throttle函数本身
    //throttle函数只执行一次，返回一个函数f。之后每次触发执行的都是f
    const fn = throttle(count,500)
    display.addEventListener('mousemove',fn)
</script>

第一次触发时，不执行。停止触发后，再执行一次

四、数组扁平化

4.1、some+扩展操作符+concat

some(fn)：检测Array中是否有元素符合指定条件

扩展操作符...，拆开数组。示例：concat(…[a,b,c]) = concat(a,b,c)

concat()，将参数拼接到调用该函数的数组上，如果参数是数组会将它拆开一层（但当调用者为空数组时除外）

所以这里扁平化实际上依赖的是扩展操作符！

const flatten = arr => {
    while(arr.some(item=>Array.isArray(item))){
        arr = [].concat(...arr)
    }
    return arr
}
var arr = [1,[2,3,[4,5,[6]],7],8]
flatten(arr)	//[1, 2, 3, 4, 5, 6, 7, 8]

4.2、递归

function flatten(arr){
    let res = []
    arr.forEach(item=>{
        if(Array.isArray(item)){
            res = res.concat(arguments.callee(item))
        }else{
            res.push(item)
        }
    })
    return res
}
var arr = [1,[2,3,[4,5,[6]],7],8]
flatten(arr)	// [1, 2, 3, 4, 5, 6, 7, 8]

可以看到，这里将数组一层层拆解的，依然是concat

4.3、reduce+递归

上面是依靠forEach遍历数组，而在这里使用reduce实现对数组的迭代

const flatten = arr => {
    return arr.reduce((target,item)=>{
        return target.concat(Array.isArray(item)?flatten(item):item)
    },[])	//必须设置一个空数组为初始值，否则第一次调用concat可能会报错（如果arr第一个元素不是Array的话）
}

五、逆扁平化

将扁平化的数组，转为树（对象）。（在恒生的笔试题中出现过）

第一种方式，普通的递归，时间复杂度为O(2^n)

// id表示当前元素的索引，pid表示当前元素的父级索引。需要将下面的数组转成嵌套的对象
var arr = [
 {id: 1, name: '1', pid: 0},
 {id: 2, name: '2', pid: 1},
 {id: 3, name: '3', pid: 1},
 {id: 4, name: '4', pid: 3},
 {id: 5, name: '5', pid: 3},
]

function arrayToTree(items){
    let res = []
    const getChildren = (res,pid)=>{
        for(i of items){
            if(i.pid == pid){
                const newItem = {...i,children:[]}
                res.push(newItem)
                getChildren(newItem.children, newItem.id)
            }
        }
    }
    getChildren(res,0)
    return res
}
arrayToTree(arr)
//返回值如下：
{
    id:1, name:'1',
    children:[
        {
            id:2, name:'2',children:[]
        },
        {
            id:3, name:'3',children:[
                {
                    id:4,name:'4',children:[]
                },
                {
                    id:5,name:'5',children:[]
                }
            ]
        }
    ]
}

第二种方式，优化时间复杂度。借助Map，可以通过id访问到对应的数据，不用每次都从头到尾遍历一次。

// id表示当前元素的索引，pid表示当前元素的父级索引。需要将下面的数组转成嵌套的对象
var arr = [
 {id: 1, name: '1', pid: 0},
 {id: 2, name: '2', pid: 1},
 {id: 3, name: '3', pid: 1},
 {id: 4, name: '4', pid: 3},
 {id: 5, name: '5', pid: 3},
]

function arrayToTree(items){
    let M = new Map
    for(const i of items){
        M.set(i.id,{...i,children:[]})
    }
    
    let res = []
    for(const i of items){
        const newItem = M.get(i.id)
        if(newItem.pid === 0){
            res.push(newItem)
        }else{
            if(M.has(i.pid)){
                M.get(i.pid).children.push(newItem)
            }
        }
    }
    return res
}
arrayToTree(arr)	//测试通过

六、数组去重

最简单有效的方法：Array -> Set ->Array

//测试用例
var arr = [1,1,2,3,4,4,NaN,NaN,undefined,undefined]	

//最简单的方法，转为Set再转回Array
const deleteRepeat = arr => [...new Set(arr)]
deleteRepeat(arr)	//[1, 2, 3, 4, NaN, undefined]

方法二：filter+indexOf。缺点：无法正确处理NaN

//测试用例
var arr = [1,1,2,3,4,4,NaN,NaN,undefined,undefined]	

function deleteRepeat(array){
    return arr.filter((item,index,arr)=>{
        return arr.indexOf(item)===index
    })
}
deleteRepeat(arr)	//[1, 2, 3, 4, undefined]

方法三：reduce。缺点：同样无法正确处理NaN

var arr = [1,1,2,3,4,4,NaN,NaN,undefined,undefined]	

function deleteRepeat(arr){
    return arr.reduce((pre,cur)=>{
        if(pre.indexOf(cur)===-1){
            pre.push(cur)
        }
        return pre
    },[])
}
deleteRepeat(arr)	//[1, 2, 3, 4, NaN, NaN, undefined]