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

2022-03-04 13:48:57 +08:00
 yaphets666
数据类似
{
"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 的的操作,导致目前性能有问题,网上找不到类似的方法,请大家帮帮忙
1226 次点击
所在节点    算法
14 条回复
doommm
2022-03-04 14:01:05 +08:00
循环的时候用 HashMap 记录下每一段 path 对应目录的对象?可以把现在的代码发上来看看
yaphets666
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
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
2022-03-04 14:47:19 +08:00
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
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
2022-03-04 15:12:21 +08:00
补充上面:
传入 xpath 每行无论是否以 / 开头,第一个节点均视为首层(非 root )节点
因为 x.strip(sep) 把开头的分隔符去掉了,注意一下这点

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

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

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

你现在 tree 是结构体,查找数量一多肯定慢。用{}的键值去查。
Kilerd
2022-03-04 16:07:25 +08:00
trie 树就好了啊
yaphets666
2022-03-04 20:43:22 +08:00
@sunjiayao
@imn1
@ch2
@ZZITE
@3dwelcome
@Kilerd 感谢 我慢慢看下

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/837936

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX