最近在考慮一個(gè)樹(shù)狀結(jié)構(gòu)存儲(chǔ)驱犹。

最終需要將list轉(zhuǎn)化為tree格式

源數(shù)據(jù)示例

源數(shù)據(jù)共401條

[{ "menuId" : "5f50c5fb8f0d74536bbfb7a4", "menuName" : "菜單管理", "parentMenuId" : null },
{ "menuId" : "5f524416ff216c2cbc554907", "menuName" : "頻道管理", "parentMenuId" : "5f50c5fb8f0d74536bbfb7a4" },
{ "menuId" : "5f576677d9588f3d78fbdb74", "menuName" : "分類(lèi)管理", "parentMenuId" : "5f524416ff216c2cbc554907" },
{ "menuId" : "5f588b22499cd2538411b98a", "menuName" : "發(fā)布管理", "parentMenuId" : "5f50c5fb8f0d74536bbfb7a4" },
{ "menuId" : "5f588b85499cd2538411b98b", "menuName" : "權(quán)限管理", "parentMenuId" : "5f50c5fb8f0d74536bbfb7a4" },
{ "menuId" : "5f588f8358bc0d3e647403a1", "menuName" : "菜單管理", "parentMenuId" : "5f588b85499cd2538411b98b" }
...
]

方法1

遞歸遍歷children

共執(zhí)行 遞歸 161202 次 5ms左右時(shí)間（win10/i7 8th/16G）

const list = [...]
// 遞歸 161202 次 5ms左右時(shí)間
const list2tree1 = (list, parentMenuId) => {
    return list.filter(item => {
        if (item.parentMenuId === parentMenuId) {
            item.children = list2tree1(list, item.menuId)
            return true
        }
        return false
    })
}
list2tree1(list, null)

方法2

因?yàn)榉椒?是查詢(xún)的children颁湖，所以每次必須全部遍歷屎媳。

我們換個(gè)思路，查詢(xún)每個(gè)節(jié)點(diǎn)的parent阔逼，查到paret之后兆衅，內(nèi)部循環(huán)就可以截止了。（使用find方法）

共執(zhí)行 68976 次 3.6ms左右

const list = [...]
// 68976 次 3.6ms左右
const list2tree2 = (list, parentMenuId) => {
    return list.filter(item => {
        if (item.parentMenuId !== parentMenuId) {
            let parent = list.find(parent => parent.menuId === item.parentMenuId)
            if (!parent.children) parent.children = []
            parent.children.push(item)
            return false
        }
        return true
    })
}
list2tree2(list, null)

方法3

在方法2的基礎(chǔ)上嗜浮，將每次find的parentNode緩存起來(lái)羡亩，減少相同parent的查詢(xún)次數(shù)

共執(zhí)行 15337 次 1.8ms左右

const list = [...]
// 15337 次 1.8ms左右 cache parent
const list2tree3 = (list, parentMenuId) => {
    let parentObj = {}
    return list.filter(item => {
        if (item.parentMenuId !== parentMenuId) {
            if (!parentObj[item.parentMenuId]) {
                parentObj[item.parentMenuId] = list.find(parent => parent.menuId === item.parentMenuId)
                parentObj[item.parentMenuId].children = []
            }
            parentObj[item.parentMenuId].children.push(item)
            return false
        }
        return true
    })
}
list2tree3(list, null)

方法4

遍歷tree之前，先遍歷一遍數(shù)組危融，將數(shù)據(jù)緩存到object中畏铆。

二次遍歷，直接使用object中的緩存

共執(zhí)行 802 次 0.2ms左右

const list = [...]
// 802 次 0.2ms左右
const list2tree4 = (list, parentMenuId) => {
    let menuObj = {}
    list.forEach(item => {
        item.children = []
        menuObj[item.menuId] = item
    })
    return list.filter(item => {
        if (item.parentMenuId !== parentMenuId) {
            menuObj[item.parentMenuId].children.push(item)
            return false
        }
        return true
    })
}
list2tree4(list, null)