前端数据结构与算法

傷城~ 2022-05-19 11:07 155阅读 0赞

# 前端数据结构与算法 #

#### 递归 ####

> 递归就是自己调用自己，是前端中比较常用的算法。递归的优点：代码简单易懂 缺点：效率上比不上非递归的实现方法

var ids = [2324,2342,123]
    (function sendReg(){ 
        var id = ids.shift()
        if(id){
            $.ajax({
                url:"/get",
                data:id
            }).always(function(){ 
                console.log("finished")
                sendReq()
            })
        }
    })

#### 重复值处理 ####

1.  双重循环

> 对于百级的数据还好，对于千级的数据可能会有压力

let arr = []
    for(let i = 0; i<n;i++){
        for(let j=0 ;j<n;j++){
            /// 处理方法
        }
    }

1.  使用set

> 使用set 和 Array 的区别在于可以减少一重循环，调用set.prototype.has 的函数，set一般是使用红黑树实现的，红黑树是一种平衡查找二叉树。  
> 实际上，chrome V8的set使用哈希实现的

var arr = new set()

1.  使用map

set/map

#### 时间比较 ####

> 当数据量小的时候for 的时间较短；当数据量较多时set/map的耗时远远低于for

## 数组去重 ##

1.  使用 set 和 array

a = [123,3,45,3,5,4,6,3,6,43,46,3,74,64,5,7,457,4,57]
    function uniqueArray(arr){ 
        return Array.from(new Set(arr))
    }

> 优点：代码简洁，速度快  
> 缺点：需要一个额外的Set 和 Array 的存储空间

1.  使用splice

a = [123,3,45,3,5,4,6,3,6,43,46,3,74,64,5,7,457,4,57]
    function uniqueArray(arr){ 
        for(var i=0;i<arr.length;i++){
            for(var j = i+1;j<arr.length;j++){
                if(arr[i]===arr[j]){
                    arr.splice(j--,1)
                }
            }
        }
        return arr
    }

> 优点：不需要使用额外的存储空间  
> 缺点：需要频繁的内存移动，双重循环

1.  只用array

a = [123,3,45,3,5,4,6,3,6,43,46,3,74,64,5,7,457,4,57]
    function uniqueArray(arr){ 
        let retArr = []
        for(var i=0;i<arr.length;i++){ if(retArr.indexOf(arr[i])<0){ retArr.push(arr[i]) }
        }
        return retArr
    }

> 缺点：大数组耗时较高

1.  使用Object + Array

a = [123,3,45,3,5,4,6,3,6,43,46,3,74,64,5,7,457,4,57]
    goog.array.removeDuplicates = function(arr,opt_rv,opt_hashFn){ 
        let returnArray = opt_rv || arr
        let defaultHashFn = function(item){ 
            //prefix each type with a single character representing the type to prevent conflicting keys (e.g. true and 'true')
            return goog.isObject(item) ? 'o' + goog.getUid(item) : (typeof item).charAt(0) + item;
        }
        var hashFn = opt_hashFn || defaultHashFn
    
        var seen = {},cursorInsert = 0,cursorRead = 0;
        while(cursorRead< arr.length){
            var current = arr[cursorRead++]
            var key = hashFn(current)
            if(!Object.prototype.hasOwnProperty.call(seen,key)){
                seen[key] = true
                returnArray[cursorInsert++] = current
            }
        }
        returnArray.length = cursorInsert
    }

> 这个是[goog.array][]中的方法，效率很高，适用于数据量偏大的结构

[goog.array]: https://github.com/google/closure-library/