您好,登錄后才能下訂單哦!
這篇文章主要介紹“web前端怎么將扁平數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)Tree”,在日常操作中,相信很多人在web前端怎么將扁平數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)Tree問(wèn)題上存在疑惑,小編查閱了各式資料,整理出簡(jiǎn)單好用的操作方法,希望對(duì)大家解答”web前端怎么將扁平數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)Tree”的疑惑有所幫助!接下來(lái),請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧!
我們看下題目:打平的數(shù)據(jù)內(nèi)容如下:
let arr = [ {id: 1, name: '部門(mén)1', pid: 0}, {id: 2, name: '部門(mén)2', pid: 1}, {id: 3, name: '部門(mén)3', pid: 1}, {id: 4, name: '部門(mén)4', pid: 3}, {id: 5, name: '部門(mén)5', pid: 4}, ]
輸出結(jié)果
[
{
"id": 1,
"name": "部門(mén)1",
"pid": 0,
"children": [
{
"id": 2,
"name": "部門(mén)2",
"pid": 1,
"children": []
},
{
"id": 3,
"name": "部門(mén)3",
"pid": 1,
"children": [
// 結(jié)果 ,,,
]
}
]
}
]
我們的要求很簡(jiǎn)單,可以先不用考慮性能問(wèn)題。實(shí)現(xiàn)功能即可,回頭分析了面試的情況,結(jié)果使我大吃一驚。
10%的人沒(méi)思路,沒(méi)碰到過(guò)這種結(jié)構(gòu)
60%的人說(shuō)用過(guò)遞歸,有思路,給他個(gè)筆記本,但就是寫(xiě)不出來(lái)
20%的人在引導(dǎo)下,磕磕絆絆能寫(xiě)出來(lái)
剩下10%的人能寫(xiě)出來(lái),但性能不是最佳
感覺(jué)不是在招聘季節(jié)遇到一個(gè)合適的人真的很難。
接下來(lái),我們用幾種方法來(lái)實(shí)現(xiàn)這個(gè)小算法
判斷一個(gè)算法的好壞,一般從執(zhí)行時(shí)間和占用空間來(lái)看,執(zhí)行時(shí)間越短,占用的內(nèi)存空間越小,那么它就是好的算法。對(duì)應(yīng)的,我們常常用時(shí)間復(fù)雜度代表執(zhí)行時(shí)間,空間復(fù)雜度代表占用的內(nèi)存空間。
時(shí)間復(fù)雜度的計(jì)算并不是計(jì)算程序具體運(yùn)行的時(shí)間,而是算法執(zhí)行語(yǔ)句的次數(shù)。
隨著n的不斷增大,時(shí)間復(fù)雜度不斷增大,算法花費(fèi)時(shí)間越多。 常見(jiàn)的時(shí)間復(fù)雜度有
常數(shù)階O(1)
對(duì)數(shù)階O(log2 n)
線性階O(n)
線性對(duì)數(shù)階O(n log2 n)
平方階O(n^2)
立方階O(n^3)
k次方階O(n^K)
指數(shù)階O(2^n)
選取相對(duì)增長(zhǎng)最高的項(xiàng)
最高項(xiàng)系數(shù)是都化為1
若是常數(shù)的話用O(1)表示
舉個(gè)例子:如f(n)=3*n^4+3n+300 則 O(n)=n^4
通常我們計(jì)算時(shí)間復(fù)雜度都是計(jì)算最壞情況。計(jì)算時(shí)間復(fù)雜度的要注意的幾個(gè)點(diǎn)
如果算法的執(zhí)行時(shí)間不隨n的增加而增長(zhǎng),假如算法中有上千條語(yǔ)句,執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類算法的時(shí)間復(fù)雜度是O(1)。 舉例如下:代碼執(zhí)行100次,是一個(gè)常數(shù),復(fù)雜度也是O(1)。
let x = 1; while (x <100) { x++; }
有多個(gè)循環(huán)語(yǔ)句時(shí)候,算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的方法決定的。舉例如下:在下面for循環(huán)當(dāng)中,外層循環(huán)每執(zhí)行一次,內(nèi)層循環(huán)要執(zhí)行n次,執(zhí)行次數(shù)是根據(jù)n所決定的,時(shí)間復(fù)雜度是O(n^2)。
for (i = 0; i < n; i++){ for (j = 0; j < n; j++) { // ...code } }
循環(huán)不僅與n有關(guān),還與執(zhí)行循環(huán)判斷條件有關(guān)。舉例如下:在代碼中,如果arr[i]不等于1的話,時(shí)間復(fù)雜度是O(n)。如果arr[i]等于1的話,循環(huán)不執(zhí)行,時(shí)間復(fù)雜度是O(0)。
for(var i = 0; i<n && arr[i] !=1; i++) { // ...code }
空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間的大小。
忽略常數(shù),用O(1)表示
遞歸算法的空間復(fù)雜度=(遞歸深度n)*(每次遞歸所要的輔助空間)
計(jì)算空間復(fù)雜度的簡(jiǎn)單幾點(diǎn)
僅僅只復(fù)制單個(gè)變量,空間復(fù)雜度為O(1)。舉例如下:空間復(fù)雜度為O(n) = O(1)。
let a = 1; let b = 2; let c = 3; console.log('輸出a,b,c', a, b, c);
遞歸實(shí)現(xiàn),調(diào)用fun函數(shù),每次都創(chuàng)建1個(gè)變量k。調(diào)用n次,空間復(fù)雜度O(n*1) = O(n)。
function fun(n) { let k = 10; if (n == k) { return n; } else { return fun(++n) } }
主要思路是提供一個(gè)遞getChildren的方法,該方法遞歸去查找子集。 就這樣,不用考慮性能,無(wú)腦去查,大多數(shù)人只知道遞歸,就是寫(xiě)不出來(lái)。。。
/** * 遞歸查找,獲取children */ const getChildren = (data, result, pid) => { for (const item of data) { if (item.pid === pid) { const newItem = {...item, children: []}; result.push(newItem); getChildren(data, newItem.children, item.id); } } } /** * 轉(zhuǎn)換方法 */ const arrayToTree = (data, pid) => { const result = []; getChildren(data, result, pid) return result; }
從上面的代碼我們分析,該實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(2^n)。
主要思路是先把數(shù)據(jù)轉(zhuǎn)成Map去存儲(chǔ),之后遍歷的同時(shí)借助對(duì)象的引用,直接從Map找對(duì)應(yīng)的數(shù)據(jù)做存儲(chǔ)
function arrayToTree(items) { const result = []; // 存放結(jié)果集 const itemMap = {}; // // 先轉(zhuǎn)成map存儲(chǔ) for (const item of items) { itemMap[item.id] = {...item, children: []} } for (const item of items) { const id = item.id; const pid = item.pid; const treeItem = itemMap[id]; if (pid === 0) { result.push(treeItem); } else { if (!itemMap[pid]) { itemMap[pid] = { children: [], } } itemMap[pid].children.push(treeItem) } } return result; }
從上面的代碼我們分析,有兩次循環(huán),該實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(2n),需要一個(gè)Map把數(shù)據(jù)存儲(chǔ)起來(lái),空間復(fù)雜度O(n)
主要思路也是先把數(shù)據(jù)轉(zhuǎn)成Map去存儲(chǔ),之后遍歷的同時(shí)借助對(duì)象的引用,直接從Map找對(duì)應(yīng)的數(shù)據(jù)做存儲(chǔ)。不同點(diǎn)在遍歷的時(shí)候即做Map存儲(chǔ),有找對(duì)應(yīng)關(guān)系。性能會(huì)更好。
function arrayToTree(items) { const result = []; // 存放結(jié)果集 const itemMap = {}; // for (const item of items) { const id = item.id; const pid = item.pid; if (!itemMap[id]) { itemMap[id] = { children: [], } } itemMap[id] = { ...item, children: itemMap[id]['children'] } const treeItem = itemMap[id]; if (pid === 0) { result.push(treeItem); } else { if (!itemMap[pid]) { itemMap[pid] = { children: [], } } itemMap[pid].children.push(treeItem) } } return result; }
從上面的代碼我們分析,一次循環(huán)就搞定了,該實(shí)現(xiàn)的時(shí)間復(fù)雜度為O(n),需要一個(gè)Map把數(shù)據(jù)存儲(chǔ)起來(lái),空間復(fù)雜度O(n)
方法 | 1000(條) | 10000(條) | 20000(條) | 50000(條) |
---|---|---|---|---|
遞歸實(shí)現(xiàn) | 154.596ms | 1.678s | 7.152s | 75.412s |
不用遞歸,兩次遍歷 | 0.793ms | 16.499ms | 45.581ms | 97.373ms |
不用遞歸,一次遍歷 | 0.639ms | 6.397ms | 25.436ms | 44.719ms |
從我們的測(cè)試結(jié)果來(lái)看,隨著數(shù)量的增大,遞歸的實(shí)現(xiàn)會(huì)越來(lái)越慢,基本成指數(shù)的增長(zhǎng)方式。
到此,關(guān)于“web前端怎么將扁平數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)Tree”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí),請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站,小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。