V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
yaphets666
V2EX  ›  算法

扁平数据转树形求助,无 parentId,只有“/a/b/c”的路径

  •  
  •   yaphets666 · 2022-03-04 13:48:57 +08:00 · 1200 次点击
    这是一个创建于 756 天前的主题,其中的信息可能已经有所发展或是发生改变。
    数据类似
    {
    "path": "/顶级目录 /基本资料 /测试文件夹",
    "file_id": "20220223113038833005618826100001"
    },
    {
    "path": "/顶级目录 /学习资料 /学习资料-1/学习资料-1-1",
    "file_id": "20222211646376995968624808413776"
    },
    {
    "path": "/顶级目录 /其他",
    "file_id": "551D3363-900F-4C90-941C-BA2DC8D6D0AD_233D55BD45C64964B848DDCD3A42B1F4"
    },
    {
    "path": "/顶级目录 /其他",
    "file_id": "6AEF3E58-DC5D-4081-9DF0-1DB2D625BC06_CA383FB15A774BF8BFC04BEEB1E1A6B9"
    },
    {
    "path": "/顶级目录 /学习资料 /学习资料-2",
    "file_id": "20220226175423469003578532800001"
    },
    {
    "path": "/顶级目录 /默认文件存放处",
    "file_id": "20220228110816879009037188700001"
    },
    {
    "path": "/顶级目录 /默认文件存放处",
    "file_id": "20220228110821760004283673600001"
    },


    我现在的方法是把,path 转化成数组['顶级目录','学习资料','学习资料-1','学习资料-1-1']后循环,判断创建树形.内部有循环套循环再套 find 的的操作,导致目前性能有问题,网上找不到类似的方法,请大家帮帮忙
    14 条回复    2022-03-04 20:43:22 +08:00
    doommm
        1
    doommm  
       2022-03-04 14:01:05 +08:00
    循环的时候用 HashMap 记录下每一段 path 对应目录的对象?可以把现在的代码发上来看看
    yaphets666
        2
    yaphets666  
    OP
       2022-03-04 14:30:51 +08:00
    @doommm function markFolder(tree) {
    tree.forEach(item => {
    if (item.children) {
    item.children.forEach(child => {
    if ("children" in child) {
    item.hasFolderChild = true;
    }
    });
    markFolder(item.children);
    }
    });
    }
    function addPath(folders) {
    folders.forEach(item => {
    item.isOpen = true;
    item.checked = false;
    item.folder_name = item.folderName;
    if ("children" in item) {
    item.children.forEach(child => {
    child.path = item.path + "/" + child.folderName;
    });
    addPath(item.children);
    }
    });
    }
    function makeTree(data,length = 0) {
    let { files, folders } = data;
    const rootName = files[0].file_folder.slice(1).split("/")[0];
    folders.forEach(item => {
    item.path = "/" + rootName + "/" + item.folderName;
    });
    addPath(folders);
    let tree = [{ children: folders }];
    tree[0].folderName = rootName;
    tree[0].folder_name = rootName;
    tree[0].path = "/" + rootName;
    tree[0].isOpen = true;
    files.forEach(item => {
    console.count(item.file_folder)
    let pathArr = item.file_folder.slice(length + 1).split("/");
    let curr = {}; //指针对象

    pathArr.forEach((path, index) => {
    if (index === 0) {
    let root = tree.find(
    branch => branch.folderName === path || branch.folder_name === path
    );
    if (!root) {
    tree.push({
    folder_name: path,
    children: [],
    isOpen: true,
    root: "root",
    path: "/" + path,
    checked: false
    });
    }
    curr = tree.find(
    branch => branch.folderName === path || branch.folder_name === path
    );
    } else {
    let obj = curr.children.find(
    branch => branch.folderName === path || branch.folder_name === path
    );
    if (!obj) {
    curr.children.push({
    folder_name: path,
    children: [],
    isOpen: true,
    path: curr.path + "/" + path,
    checked: false
    });
    }
    curr = curr.children.find(
    branch => branch.folderName === path || branch.folder_name === path
    );
    }
    });
    curr.children.push(
    Object.assign(
    {
    path: item.file_folder,
    checked: false
    },
    item
    )
    );
    });
    markFolder(tree);
    return tree;
    }




    不光是处理树的代码 还有业务代码 工具代码
    sunjiayao
        3
    sunjiayao  
       2022-03-04 14:45:10 +08:00
    1. 创建一个 hash 对象; k = path ; v = {currentPath,parent,fileIds,child}
    2. 循环数组
    3. path.split("/") 后循环(因为是 / 开头的所以 index 要从 1 开始)
    4. 检测 pathArray[index] 是否存在 hash 内;如果没有创建 v 对象;如果当前 index >1 则说明有 parent; parent = pathArray[index-1]
    5. 当 index = pathArray.length -1 时; 要往 hash.pathArray[index].fileIds 添加当前 fileId
    以上结束后
    循环 hash.values 如果 v.parent 不为空。则把 v 添加进 hash[v.parent].child 内;
    最后 hash[顶级目录] 就是你想要的 tree
    sunjiayao
        4
    sunjiayao  
       2022-03-04 14:47:19 +08:00
    sunjiayao
        5
    sunjiayao  
       2022-03-04 14:47:46 +08:00
    @sunjiayao
    1. 创建一个 hash 对象; k = path ; v = {currentPath,parent,fileIds,child}
    更正为
    1. 创建一个 hash 对象; k = currentPath ; v = {currentPath,parent,fileIds,child}
    imn1
        6
    imn1  
       2022-03-04 15:05:27 +08:00
    我只有 python 的

    xpath2dict 函数

    gist.github.com/ImN1/cbcbfabb9ed2f277c926427f4598bbb7

    --------------------
    最后几行(一个递归)是某国外博客抄过来的,根据数据格式有小改动,当时忘记记下出处,其他是自己写的

    这是我常用的自定义函数,因为 pyqt5 树控件用得很多,经常需要构建
    由于我部分项目传入数据格式是 topnode/node/[leaf] 这种格式(由拼接后得到)
    所以加了段 tryJson 代码,如果觉得没需要,可以去掉,v = tryJson(x[1]) 这句改为 v=x[1]则可
    imn1
        7
    imn1  
       2022-03-04 15:12:21 +08:00
    补充上面:
    传入 xpath 每行无论是否以 / 开头,第一个节点均视为首层(非 root )节点
    因为 x.strip(sep) 把开头的分隔符去掉了,注意一下这点

    @Livid
    为何回复贴 gist url 也视为 spamming ?我要去掉 https 才能发,沙盒测试时没这个限制
    ch2
        8
    ch2  
       2022-03-04 15:15:45 +08:00 via iPhone
    前缀树了解一下
    Livid
        9
    Livid  
    MOD
       2022-03-04 15:22:26 +08:00
    @imn1 收到。你看到的出错提示信息是?
    imn1
        10
    imn1  
       2022-03-04 15:33:41 +08:00
    @Livid #9
    提示就是不要贴链接,会被视为 spamming ,无法提交-->提交还是继续提示
    ZZITE
        11
    ZZITE  
       2022-03-04 15:48:20 +08:00
    根据 Path 来创建 parent 关系
    如 “/顶级目录 /基本资料 /测试文件夹"先转为你说的数组,最后一项'测试文件夹'为自身 id , 前面的所有项再 join('-'),即'顶级目录-基本资料'作为 parentId 。有了这个 parentId 再转树就容易了吧。
    3dwelcome
        12
    3dwelcome  
       2022-03-04 16:05:21 +08:00
    算法没问题啊,我也这样写。

    性能主要瓶颈在于查找已经创建好的树对象。

    可以建立一个全局 hash pair ,专门用于查找; 在 tree.find 参数里,不要传对象,改传字符串,这样查找就能快很多。

    你现在 tree 是结构体,查找数量一多肯定慢。用{}的键值去查。
    Kilerd
        13
    Kilerd  
       2022-03-04 16:07:25 +08:00
    trie 树就好了啊
    yaphets666
        14
    yaphets666  
    OP
       2022-03-04 20:43:22 +08:00
    @sunjiayao
    @imn1
    @ch2
    @ZZITE
    @3dwelcome
    @Kilerd 感谢 我慢慢看下
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2680 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 15:14 · PVG 23:14 · LAX 08:14 · JFK 11:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.