北京Web培訓
達內北京萬壽路中心

010-62126400

熱門課程

北京Web培訓 > 疑難解答 >北京web培訓:為什么說數據結構與算法對前端很重要?

北京web培訓:為什么說數據結構與算法對前端很重要?

  • 時間:2020-03-26 15:14
  • 發布:北京Web培訓
  • 來源:疑難解答

達內北京web培訓機構:為什么說數據結構與算法對前端很重要?

從一個需求談起,在之前的項目中,曾經遇到過這樣一個需求,編寫一個級聯選擇器,大概是這樣:

達內北京web培訓機構

圖中的示例使用的是Ant-Design的Cascader組件。

要實現這一功能,我需要類似這樣的數據結構:

var data = [{

"value": "浙江",

"children": [{

"value": "杭州",

"children": [{

"value": "西湖"

}]

}]

}, {

"value": "四川",

"children": [{

"value": "成都",

"children": [{

"value": "錦里"

}, {

"value": "方所"

}]

}, {

"value": "阿壩",

"children": [{

"value": "九寨溝"

}]

}]

}]

一個具有層級結構的數據,實現這個功能非常容易,因為這個結構和組件的結構是一致的,遞歸遍歷就可以了。

但是,由于后端通常采用的是關系型數據庫,所以返回的數據通常會是這個樣子:

var data = [{

"province": "浙江",

"city": "杭州",

"name": "西湖"

}, {

"province": "四川",

"city": "成都",

"name": "錦里"

}, {

"province": "四川",

"city": "成都",

"name": "方所"

}, {

"province": "四川",

"city": "阿壩",

"name": "九寨溝"

}]

前端這邊想要將數據轉換一下其實也不難,因為要合并重復項,可以參考數據去重的方法來做,于是我寫了這樣一個版本。

'use strict'

/**

* 將一個沒有層級的扁平對象,轉換為樹形結構({value, children})結構的對象

* @param {array} tableData - 一個由對象構成的數組,里面的對象都是扁平的

* @param {array} route - 一個由字符串構成的數組,字符串為前一數組中對象的key,最終

* 輸出的對象層級順序為keys中字符串key的順序

* @return {array} 保存具有樹形結構的對象

*/

var transObject = function(tableData, keys) {

let hashTable = {}, res = []

for( let i = 0; i < tableData.length; i++ ) {

if(!hashTable[tableData[i][keys[0]]]) {

let len = res.push({

value: tableData[i][keys[0]],

children: []

})

// 在這里要保存key對應的數組序號,不然還要涉及到查找

hashTable[tableData[i][keys[0]]] = { $$pos: len - 1 }

}

if(!hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]]) {

let len = res[hashTable[tableData[i][keys[0]]].$$pos].children.push({

value: tableData[i][keys[1]],

children: []

})

hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]] = { $$pos: len - 1 }

}

res[hashTable[tableData[i][keys[0]]].$$pos].children[hashTable[tableData[i][keys[0]]][tableData[i][keys[1]]].$$pos].children.push({

value: tableData[i][keys[2]]

})

}

return res

}

var data = [{

"province": "浙江",

"city": "杭州",

"name": "西湖"

}, {

"province": "四川",

"city": "成都",

"name": "錦里"

}, {

"province": "四川",

"city": "成都",

"name": "方所"

}, {

"province": "四川",

"city": "阿壩",

"name": "九寨溝"

}]

var keys = ['province', 'city', 'name']

console.log(transObject(data, keys))

還好keys的長度只有3,這種東西長了根本沒辦法寫,很明顯可以看出來這里面有重復的部分,可以通過循環搞定,但是想了很久都沒有思路,就擱置了。

后來,有一天晚飯后不是很忙,就跟旁邊做數據的同事聊了一下這個需求,請教一下該怎么用循環來處理。他看了一下,就問我:“你知道trie樹嗎?”。我頭一次聽到這個概念,他簡單的給我講了一下,然后說感覺處理的問題有些類似,讓我可以研究一下trie樹的原理并試著優化一下。

講道理,trie樹這個數據結構網上確實有很多資料,但很少有使用JavaScript實現的,不過原理倒是不難。嘗試之后,我就將transObject的代碼優化成了這樣。(關于trie樹,還請讀者自己閱讀相關材料)

var transObject = function(tableData, keys) {

let hashTable = {}, res = []

for (let i = 0; i < tableData.length; i++) {

let arr = res, cur = hashTable

for (let j = 0; j < keys.length; j++) {

let key = keys[j], filed = tableData[i][key]

if (!cur[filed]) {

let pusher = {

value: filed

}, tmp

if (j !== (keys.length - 1)) {

tmp = []

pusher.children = tmp

}

cur[filed] = { $$pos: arr.push(pusher) - 1 }

cur = cur[filed]

arr = tmp

} else {

cur = cur[filed]

arr = arr[cur.$$pos].children

}

}

}

return res

}

這樣,解決方案就和keys的長短無關了。

這大概是我第一次,真正將數據結構的知識和前端項目需求結合在一起。

面試過程中遇到過的問題

目前為止我參加過幾次前端開發方面的面試,確實有不少面試官會問道一些算法。通常會涉及的,是鏈表、樹、字符串、數組相關的知識。前端面試對算法要求不高,似乎已經是業內的一種共識了。雖說算法好的前端面試肯定會加分,但是僅憑常見的面試題,而不去聯系需求,很難讓人覺得,算法對于前端真的很重要。

直到有一天,有一位面試官問我這樣一個問題,下面我按照自己的回憶把對話模擬出來,A指面試官,B指我:

A:你有寫過瀑布流嗎?

B:我寫過等寬瀑布流。實現是當用戶拉到底部的一定高度的時候,向后端請求一定數量的圖片,然后再插入到頁面中。

A:那我問一下,如何讓幾列圖片之間的高度差最小?

B:這個需要后端發來的數據里面有圖片的高度,然后我就可以看當前高度最小的是哪里列,將新圖片插入那一列,然后再看看新的高度最小的是哪一列。

A:我覺得你沒有理解我的問題,我的意思是如何給后端發來的圖片排序,讓幾列圖片之間的高度差最小?

B:(想了一段時間)對不起,這個問題我沒有思路。

A:你是軟件工程專業的對吧?你們數據結構課有沒有學動態規劃?

B:可能有講吧,但是我沒什么印象了。

對話大概就是這樣,雖然面試最終還是pass了,但這個問題確實讓我很在意,因為我覺得,高度差“最”小,真的能用很簡單的算法就解決嗎?

這個問題的實質,其實就是有一個數組,將數組元素分成n份,每份所有元素求和,如何使每份的和的差最小。

搜索上面這個問題,很快就能找到相關的解答,很基本的一類動態規劃問題——背包問題。

之前我確實看過背包問題的相關概念(也僅僅是相關概念)。當時我看到這樣一段話:

許多使用遞歸去解決的編程問題,可以重寫為使用動態規劃的技巧去解決。動態規劃方案通常會使用一個數組來建立一張表,用于存放被分解成眾多子問題的解。當算法執行完畢,最終的解將會在這個表中很明顯的地方被找到。

后面是一個用動態規劃重寫斐波那契數列的例子。我看到它只是將遞歸的結果,保存在了一個數組中,就天真的以為動態規劃是優化遞歸的一種方法,并沒有深入去理解。

不求甚解,確實早晚會出問題的。當時我雖然以為自己知道了算法的重要性,但其實還是太年輕。

動態規劃可以求解一類“最優解”問題,這在某種程度上讓我耳目一新。由于本文主要還是為了說明數據結構與算法對于前端的意義。

一道思考題

將如下扁平對象,轉為樹形對象。parent字段為空字符串的節點為根節點:

var input = {

h3: {

parent: 'h2',

name: '副總經理(市場)'

},

h1: {

parent: 'h0',

name: '公司機構'

},

h7: {

parent: 'h6',

name: '副總經理(總務)'

},

h4: {

parent: 'h3',

name: '銷售經理'

},

h2: {

parent: 'h1',

name: '總經理'

},

h8: {

parent: 'h0',

name: '財務總監'

},

h6: {

parent: 'h4',

name: '倉管總監'

},

h5: {

parent: 'h4',

name: '銷售代表'

},

h0: {

parent: '',

name: 'root'

}

};

這個需求在前端其實也很實際,示例中的對象是一個公司組織結構圖。如果需求是讓你在前端用svg之類的技術畫出這樣一張圖,就需要這個功能。(另外我想到的一種應用場景,就是在前端展示類似windows資源管理器的文件樹)

我當時想了很久,沒有想到一個循環解決的方法,后來在stackoverflow上找到了答案:

var plain2Tree = function (obj) {

var key, res

for(key in obj) {

var parent = obj[key].parent

if(parent === '') {

res = obj[key]

} else {

obj[parent][key] = obj[key]

}

}

return res

}

這段代碼,就是利用了JavaScript里面的引用類型,之后的思路,和操作指針沒什么區別,就是構造一棵樹。

但對于我來說,從來都沒有往樹和指針的那方面思考,就很被動了。

上一篇:web前端入行門檻低嗎?怎樣才能學好?
下一篇:準備轉行web前端:你的入門學習方法正確嗎?

馬上預約七天免費體驗課

姓名:

電話:

北京Web培訓班:2020年二季度Web安全工具

北京Web培訓班:Web前端開發到底是什么?

北京web培訓:拿高薪的web前端都是怎么學的?

web前端工程師,未來這些發展方向可以試試!

選擇城市和中心
江西省

貴州省

廣西省

海南省

女人和女人做人爱视频