Board logo

标题: 【出题】将 哈希节点关系清单 还原为 多层级哈希结构 [打印本页]

作者: 523066680    时间: 2021-12-16 21:31     标题: 【出题】将 哈希节点关系清单 还原为 多层级哈希结构

本帖最后由 523066680 于 2021-12-18 08:49 编辑

备用标题:将数据节点关系清单还原为多层级哈希结构
  1. 数据是从跨境电商平台获取的类目清单,但是这个清单是二维的,提供了所有键值的关系 [ 父级ID,当前项ID,当前项的名称,以及当前的类目层级 ]
  2. 在制作平台类目交易指数数据可视化的时候需要分级显示,于是就必须把这些平面展开的关联信息还原为多层级的数据结构
  3. 处理要求:只需要还原ID层级结构,结构中不需要包含项的中文名等信息。同层级的清单使用数组或者哈希映射没有要求,只要能递进枚举就行。
  4. 语言:不限
复制代码
有一种很粗暴的方法,就是多次扫描整个列表。第一次扫描寻找0为父级ID的项,创建第一层键值关系;针对每一个子键,扫描清单寻找该键的子节点,创建第二层关系。
但这种方式效率极低,期待不一样的答案。

附精简过的原始数据(plain.json),
  1. {
  2.    "data" : [
  3.       [ 0, 30, "安全防护", 1 ],
  4.       [ 30, 3030, "门禁", 2 ],
  5.       [ 30, 3009, "消防器材", 2 ],
  6.       [ 30, 3011, "视频监控", 2 ],
  7.       [ 3011, 200327188, "视频监控配件", 3 ],
  8.       [ 30, 3007, "劳动保护用品", 2 ],
  9.       [ 0, 21, "办公、文化及教育用品", 1 ],
  10.       [ 21, 2213, "期刊与杂志", 2 ],
  11.       [ 21, 212002, "展示告示用品", 2 ],
  12.       [ 212002, 21200202, "黑板", 3 ],
  13.       [ 212002, 100003132, "白板擦、黑板擦等", 3 ],
  14.       [ 100003132, 100003183, "黑板擦", 4 ],
  15.       [ 100003132, 100003182, "白板擦", 4 ],
  16.       [ 0, 509, "电话和通讯", 1 ],
  17.       [ 509, 100001205, "手机配件", 2 ],
  18.       [ 509, 50906, "对讲机", 2 ],
  19.       [ 0, 7, "电脑和办公", 1 ],
  20.       [ 7, 200001083, "笔记本电脑部件及配件", 2 ],
  21.       [ 7, 70806, "电脑连线及接插件", 2 ],
  22.       [ 0, 44, "消费电子", 1 ],
  23.       [ 44, 629, "零配件", 2 ],
  24.       [ 44, 100000305, "摄影摄像", 2 ]
  25.    ]
  26. }
复制代码
处理后的结果(只做参考,不强制约束格式,参考前面的处理要求):
  1. {
  2.    "0" : {
  3.       "21" : {
  4.          "212002" : {
  5.             "100003132" : {
  6.                "100003182" : {},
  7.                "100003183" : {}
  8.             },
  9.             "21200202" : {}
  10.          },
  11.          "2213" : {}
  12.       },
  13.       "30" : {
  14.          "3007" : {},
  15.          "3009" : {},
  16.          "3011" : {
  17.             "200327188" : {}
  18.          },
  19.          "3030" : {}
  20.       },
  21.       "44" : {
  22.          "100000305" : {},
  23.          "629" : {}
  24.       },
  25.       "509" : {
  26.          "100001205" : {},
  27.          "50906" : {}
  28.       },
  29.       "7" : {
  30.          "200001083" : {},
  31.          "70806" : {}
  32.       }
  33.    }
  34. }
复制代码
------------------ 2021-12-17 扩展 -----------------
假如源头数据不一定是按节点层级顺序排列呢?
也就是有可能 上级节点在子节点之后,
  1.      [ 211111, 200656001, "石膏像", 3 ],
  2.      [ 21, 211111, "艺术用品", 2 ],
  3.      [ 211111, 201330804, "智能取色笔", 3 ],
  4.      [ 0, 21, "办公、文化及教育用品", 1 ],
  5.      [ 21, 100003131, "美工工具", 2 ],
复制代码
以及节点的ID值不一定是按层级从小到大的,有些类目有可能因为创建的时间比较晚,ID值比某些子节点更大。
可以依靠的信息就是 数组末尾的层级信息,以及前两个ID的匹配关系
作者: 523066680    时间: 2021-12-16 21:47

本帖最后由 523066680 于 2021-12-16 21:50 编辑

发一个实际应用的截图,
(提取所有键的交易指数,重新整合出层级占比数据,结合echarts可视化,得到类似以下的类目分层级交易占比图。平台数据只对卖家开放,这个不作为题目)

作者: flashercs    时间: 2021-12-17 07:56

本帖最后由 flashercs 于 2021-12-17 07:58 编辑

其实是个tree 的遍历;每组数据只读一次. 改了部分json 数据,包含2级以上目录. powershell脚本
  1. #Requires -Version 5
  2. $sJson = @'
  3. {
  4.   "data" : [
  5.      [ 0, 30, "安全防护", 1 ],
  6.      [ 30, 3030, "门禁", 2 ],
  7.      [ 30, 200327231, "楼宇自动化", 2 ],
  8.      [ 30, 200327211, "救灾用品", 2 ],
  9.      [ 30, 200001791, "急救箱", 2 ],
  10.      [ 30, 3009, "消防器材", 2 ],
  11.      [ 30, 200004310, "楼宇对讲", 2 ],
  12.      [ 30, 200330186, "物联传感设备", 2 ],
  13.      [ 30, 200327212, "公共应急广播系统", 2 ],
  14.      [ 30, 3015, "交通安全", 2 ],
  15.      [ 3015, 42578, "交通安全_1", 3 ],
  16.      [ 42578, 9527, "交通安全_1_1", 4 ],
  17.      [ 30, 200327196, "保险柜/保险箱", 2 ],
  18.      [ 30, 200004311, "防盗报警设备", 2 ],
  19.      [ 30, 200328267, "安检防爆检测设备", 2 ],
  20.      [ 30, 200328217, "自卫防身及安保用品", 2 ],
  21.      [ 30, 200004309, "智能一卡通系统", 2 ],
  22.      [ 30, 200004343, "传输设备及电缆", 2 ],
  23.      [ 30, 200332185, "安防无人机和机器人", 2 ],
  24.      [ 30, 3011, "视频监控", 2 ],
  25.      [ 30, 3007, "劳动保护用品", 2 ],
  26.      [ 3007, 0, "劳动保护用品_0", 3 ],
  27.      [ 3007, 1, "劳动保护用品_1", 3 ],
  28.      [ 0, 21, "办公、文化及教育用品", 1 ],
  29.      [ 21, 211111, "艺术用品", 2 ],
  30.      [ 21, 100003131, "美工工具", 2 ],
  31.      [ 21, 100003135, "教学设备及用品", 2 ],
  32.      [ 21, 2213, "期刊与杂志", 2 ],
  33.      [ 21, 2209, "地图和地图集", 2 ],
  34.      [ 21, 2112, "办公用纸及纸制品", 2 ],
  35.      [ 21, 212002, "展示告示用品", 2 ],
  36.      [ 21, 200001562, "印刷制品", 2 ],
  37.      [ 21, 100003125, "学生用品", 2 ],
  38.      [ 21, 100003134, "胶带、胶水、包装带等", 2 ],
  39.      [ 21, 211106, "桌上收纳用品", 2 ],
  40.      [ 21, 100003155, "笔记本、拍纸本等书写用品", 2 ],
  41.      [ 21, 100003129, "办公装订用品", 2 ],
  42.      [ 21, 200001743, "钢笔,铅笔及书写工具", 2 ],
  43.      [ 21, 200004276, "文具贴纸/儿童贴纸", 2 ],
  44.      [ 21, 2139, "绘图工具", 2 ],
  45.      [ 21, 200652001, "财会用品", 2 ],
  46.      [ 21, 201236701, "书籍", 2 ],
  47.      [ 21, 201330702, "邮寄和装运", 2 ],
  48.      [ 21, 201338004, "文件夹、文件袋等收纳用品", 2 ],
  49.      [ 0, 509, "电话和通讯", 1 ],
  50.      [ 509, 100001205, "手机配件", 2 ],
  51.      [ 509, 100001204, "通信设备", 2 ],
  52.      [ 509, 200380144, "对讲机配附件", 2 ],
  53.      [ 509, 50906, "对讲机", 2 ],
  54.      [ 509, 201084002, "手机部件", 2 ],
  55.      [ 1, 7, "电脑和办公", 1 ],
  56.      [ 7, 200001083, "笔记本电脑部件及配件", 2 ],
  57.      [ 7, 70806, "电脑连线及接插件", 2 ],
  58.      [ 7, 708022, "电脑清洁用品", 2 ],
  59.      [ 7, 200001081, "电脑外设", 2 ],
  60.      [ 7, 200185144, "开发板及配件", 2 ],
  61.      [ 7, 100005329, "切换器", 2 ],
  62.      [ 7, 200003782, "办公电子", 2 ],
  63.      [ 7, 200001085, "平板电脑配件", 2 ],
  64.      [ 0, 44, "消费电子", 1 ],
  65.      [ 44, 629, "零配件", 2 ],
  66.      [ 44, 100000305, "摄影摄像", 2 ],
  67.      [ 44, 100000310, "游戏及配附件", 2 ],
  68.      [ 44, 100000308, "家用音视频设备", 2 ],
  69.      [ 44, 100000306, "便携音视频设备", 2 ],
  70.      [ 44, 200003803, "智能电子", 2 ]
  71.   ]
  72. }
  73. '@
  74. $oJson = ConvertFrom-Json -InputObject $sJson
  75. # return type: Dictionary[string,object]
  76. function ParseTreeData {
  77.   param (
  78.     [object[]]$Data
  79.   )
  80.   $stack = New-Object System.Collections.Stack
  81.   $nodeRoot = New-Object 'System.Collections.Generic.SortedDictionary[string,object]'
  82.   $stack.Push($nodeRoot)
  83.   foreach ($arr in $Data) {
  84.     $parentId = $arr[0].ToString()
  85.     $currentId = $arr[1].ToString()
  86.     $currentLevel = $arr[3]
  87.     # tree hierarchy from deep level to shallow level,simulate recurse call back
  88.     while ($stack.Count - 1 -gt $currentLevel) {
  89.       $null = $stack.Pop()
  90.     }
  91.     # if recurse call back to level 1, then back to 0, because node in level 1 MAY not appear
  92.     if ($stack.Count - 1 -eq $currentLevel -and $currentLevel -eq 1) {
  93.       $null = $stack.Pop()
  94.     }
  95.     # tree hierarchy from shallow level to deep level
  96.     if ($stack.Count - 1 -lt $currentLevel ) {
  97.       $peek = $stack.Peek()
  98.       if (-not $peek.ContainsKey($parentId)) {
  99.         $peek.Add($parentId, (New-Object 'System.Collections.Generic.SortedDictionary[string,object]'))
  100.       }
  101.       $stack.Push($peek[$parentId])
  102.     }
  103.     # add current item to the tree
  104.     $peek = $stack.Peek()
  105.     $peek.Add($currentId, (New-Object 'System.Collections.Generic.SortedDictionary[string,object]'))
  106.   }
  107.   return $nodeRoot
  108. }
  109. $nodeRoot = ParseTreeData -Data $oJson.Data
  110. 'Enumerate data hierarchy:'
  111. $nodeRoot["0"]["30"]
  112. $nodeRoot["0"]["30"]["3015"]
  113. $nodeRoot["0"]["30"]["3015"]["42578"]
  114. 'ConvertTo-Json:'
  115. $nodeRoot | ConvertTo-Json -Depth 100
  116. # 包含中文名称
  117. "`r`n #################### json data with name:"
  118. class Node {
  119.   [string]$Name
  120.   [System.Collections.Generic.SortedDictionary[string, Node]]$Nodes = [System.Collections.Generic.SortedDictionary[string, Node]]::new()
  121.   Node() { }
  122.   Node([string]$name) {
  123.     $this.Name = $name
  124.   }
  125. }
  126. function ParseTreeData2 {
  127.   param (
  128.     [object[]]$Data
  129.   )
  130.   $stack = New-Object System.Collections.Stack
  131.   $nodeRoot = New-Object Node
  132.   $stack.Push($nodeRoot)
  133.   foreach ($arr in $Data) {
  134.     $parentId = $arr[0].ToString()
  135.     $currentId = $arr[1].ToString()
  136.     $currentName = $arr[2]
  137.     $currentLevel = $arr[3]
  138.     # tree hierarchy from deep level to shallow level,simulate recurse call back
  139.     while ($stack.Count - 1 -gt $currentLevel) {
  140.       $null = $stack.Pop()
  141.     }
  142.     # if recurse call back to level 1, then back to 0, because node in level 1 MAY not appear
  143.     if ($stack.Count - 1 -eq $currentLevel -and $currentLevel -eq 1) {
  144.       $null = $stack.Pop()
  145.     }
  146.     # tree hierarchy from shallow level to deep level
  147.     if ($stack.Count - 1 -lt $currentLevel ) {
  148.       $peek = $stack.Peek().Nodes
  149.       if (-not $peek.ContainsKey($parentId)) {
  150.         $peek.Add($parentId, (New-Object Node))
  151.       }
  152.       $stack.Push($peek[$parentId])
  153.     }
  154.     # add current item to the tree
  155.     $peek = $stack.Peek().Nodes
  156.     $peek.Add($currentId, (New-Object Node -ArgumentList @($currentName)))
  157.   }
  158.   return $nodeRoot
  159. }
  160. $nodeRoot2 = ParseTreeData2 -Data $oJson.Data
  161. $nodeRoot2.Nodes["0"].Nodes["30"] | Format-Table -AutoSize
  162. $nodeRoot2.Nodes["0"].Nodes["21"].Nodes["100003125"] | Format-Table -AutoSize
  163. $nodeRoot2 | ConvertTo-Json -Depth 100
复制代码

作者: slimay    时间: 2021-12-17 09:25

嗯, 因此 第一次扫描全部数据,就应该按照层级 ,将数据分成 1层级的数据, 2层级的数据, 3层级的数据。 然后先循环1层级的数据建立主干, 再循环二层级数据建立分支, 依次建立子层级...
如果有n行数据,那么最多只需要循环 2n次, 也就是   O(2n)时间复杂度。应该都是这么干的。
作者: 523066680    时间: 2021-12-17 09:49

本帖最后由 523066680 于 2021-12-17 10:13 编辑

操作上可以更简
作者: netbenton    时间: 2021-12-17 09:58

本帖最后由 netbenton 于 2021-12-17 12:02 编辑

[ 30, 3030, "门禁", 2 ]
上面例子,中的“2”,直接指明是第几层的数据
就根据它进行处理,遍历一次就好了。
  1. @echo off
  2. setlocal enabledelayedexpansion
  3. for /l %%a in (1,1,5) do set "tab=!tab! "
  4. ::排版用的
  5. set n=0
  6. echo;{
  7. rem 从0级开始
  8. for /f "tokens=2 delims=[]" %%a in (test.txt) do (
  9. set str=%%a
  10. rem 有引号,用到变量处理
  11. for /f "tokens=1-4 delims= " %%1 in ("!str!") do (
  12. for /f "tokens=1-4 delims=," %%1 in ("%%1,%%2,3,%%4") do (
  13. rem 第3项有 “,” 号,所以要把它先拿掉
  14. rem 根据最后项数值变化判断处于哪一级,
  15. rem 同级,升级,降级,做不同的处理,并排版。
  16. rem 排序也可以做,就是效率有点低,如果不影响就算了。
  17. if !n! lss %%4 (
  18. if not defined v%%1 (
  19. echo;!tab:~-%%4!"%%1":{
  20. set v%%1=1
  21. ) else (
  22. echo;!tab:~-%%4! %%2
  23. )
  24. set one=%%2
  25. set n=%%4
  26. ) else (
  27. if !n! gtr %%4 (
  28. echo; !tab:~-%%4!}
  29. set n=%%4
  30. ) else (
  31. if defined one (
  32. echo;!tab:~-%%4! "!one!":{},&set one=
  33. )
  34. echo;!tab:~-%%4! "%%2":{},<nul
  35. )
  36. )
  37. ))
  38. )
  39. rem 收尾了,做 “}” 号对齐
  40. for /l %%a in (!n!,-1,1) do (
  41. echo;!tab:~-%%a!}
  42. )
  43. echo;}
  44. pause
复制代码

作者: 523066680    时间: 2021-12-17 16:38

本帖最后由 523066680 于 2021-12-17 18:22 编辑

回复 6# netbenton

    JSON的格式有一些约束,比如
  1.             "200004343":{},
  2.             "200332185":{},
  3.             "3011":{},
  4.             "3007":{},
  5.         }
复制代码
这里  "3007":{}, 作为该范围最后一个元素,末尾的逗号会导致JSON解释器报错(这个约束可以放宽,不是必须要求,先 PASS

第二个是
  1.             "3007":{},
  2.         }
  3.         "21":{
  4.             "211111":{},
复制代码
21之前的节点的 末尾标记 } 后面没有加逗号,这样JSON解释器读取时会变成 } "21":{ ... 导致出错

另外层次结构多的时候会产生 花括号数量不对称的问题,测试数据:
  1. {
  2.     "data": [
  3.         [0, 1, 0, 1],
  4.         [1, 101, 0, 2],
  5.         [101, 10101, 0, 3],
  6.         [1, 102, 0, 2],
  7.         [102, 10201, 0, 3],
  8.         [0, 2, 0, 1],
  9.         [2, 201, 0, 2],
  10.         [201, 20101, 0, 3],
  11.         [2, 202, 0, 2],
  12.         [202, 20201, 0, 3],
  13.         [0, 3, 0, 1],
  14.         [3, 301, 0, 2],
  15.         [301, 30101, 0, 3],
  16.         [3, 302, 0, 2],
  17.         [302, 30201, 0, 3]
  18.     ]
  19. }
复制代码
以上也是不限制语言的原因,因为其他语言处理JSON有现成的库,可以直接着手处理数据。
作者: netbenton    时间: 2021-12-17 18:19

回复 7# 523066680

改好了!
再看看。
  1. @echo off
  2. setlocal enabledelayedexpansion
  3. for /l %%a in (1,1,5) do set "tab=!tab! "
  4. ::排版用的
  5. set n=0
  6. echo;{
  7. rem 从0级开始
  8. for /f "tokens=2 delims=[]" %%a in (test.txt) do (
  9. set str=%%a
  10. rem 有引号,用到变量处理
  11. for /f "tokens=1-4 delims= " %%1 in ("!str!") do (
  12. for /f "tokens=1-4 delims=," %%1 in ("%%1,%%2,3,%%4") do (
  13. rem 第3项有 “,” 号,所以要把它先拿掉
  14. rem 根据最后项数值变化判断处于哪一级,
  15. rem 同级,升级,降级,做不同的处理,并排版。
  16. rem 排序也可以做,就是效率有点低,如果不影响就算了。
  17. if !n! lss %%4 (
  18. if not defined v%%1 (
  19. echo;!tab:~-%%4!"%%1":{
  20. set v%%1=1
  21. ) else (
  22. echo;!tab:~-%%4! %%2
  23. )
  24. set one=%%2
  25. set/a n=%%4,m=n-1
  26. ) else (
  27. if !n! gtr %%4 (
  28. for /l %%a in (!m!,-1,%%4) do (
  29. if defined one (
  30. echo;!tab:~-%%a! "!one!":{}&set one=
  31. )
  32. echo; !tab:~-%%a!},
  33. )
  34. set n=%%4
  35. ) else (
  36. if defined one (
  37. echo;!tab:~-%%4! "!one!":{},
  38. )
  39. set one=%%2
  40. )
  41. )
  42. ))
  43. )
  44. if defined one (
  45. echo;!tab:~-%n%! "!one!":{}&set one=
  46. )
  47. rem 收尾了,做 “}” 号对齐
  48. for /l %%a in (!n!,-1,1) do (
  49. echo;!tab:~-%%a!}
  50. )
  51. echo;}
  52. pause
复制代码

作者: 523066680    时间: 2021-12-17 18:49

本帖最后由 523066680 于 2021-12-17 18:59 编辑

补充一下信息:
源头数据不一定是按节点层级顺序排列的。
也就是有可能 上级节点在子节点之后,
  1.       
  2.      [ 211111, 200656001, "石膏像", 3 ],
  3.      [ 21, 211111, "艺术用品", 2 ],
  4.      [ 211111, 201330804, "智能取色笔", 3 ],
  5.      [ 0, 21, "办公、文化及教育用品", 1 ],
  6.      [ 21, 100003131, "美工工具", 2 ],
复制代码
以及节点的ID值不一定是按层级从小到大的,有些类目有可能因为创建的时间比较晚,ID值比某些子节点更大。
可以依靠的信息就是 数组末尾的层级信息,以及前两个ID的匹配关系
作者: netbenton    时间: 2021-12-17 19:38

回复 9# 523066680

你给出的数据测试没问题。
只要升级没有跳级,就没有问题,降级可以跳级,已经有处理了
作者: 523066680    时间: 2021-12-17 19:46

回复 10# netbenton

    测试数据
  1. {
  2.     "data": [
  3.         [0, 1, 0, 1],
  4.         [1, 101, 0, 2],
  5.         [101, 10101, 0, 3],
  6.         [101, 10102, 0, 3],
  7.         [101, 10103, 0, 3],
  8.         [10103, 1010300, 0, 4],
  9.         [101, 10104, 0, 3],
  10.         [1, 102, 0, 2],
  11.         [102, 10201, 0, 3],
  12.         [102, 10202, 0, 3],
  13.         [10202, 1020200, 0, 4],
  14.         [102, 10203, 0, 3],
  15.         [102, 10204, 0, 3]
  16.     ]
  17. }
复制代码

作者: 523066680    时间: 2021-12-17 19:54

本帖最后由 523066680 于 2021-12-17 20:30 编辑

回复 4# slimay

        借你的思路优化了以前写过的一个方案。一共做了两种方案,明天公布代码

作者: netbenton    时间: 2021-12-17 22:47

回复 11# 523066680


  又改好了。
  1. @echo off
  2. setlocal enabledelayedexpansion
  3. for /l %%a in (1,1,5) do set "tab=!tab! "
  4. ::排版用的
  5. set n=0
  6. echo;{
  7. rem 从0级开始
  8. for /f "tokens=2 delims=[]" %%a in (test.txt) do (
  9. set str=%%a
  10. rem 有引号,用到变量处理
  11. for /f "tokens=1-4 delims= " %%1 in ("!str!") do (
  12. for /f "tokens=1-4 delims=," %%1 in ("%%1,%%2,3,%%4") do (
  13. rem 第3项有 “,” 号,所以要把它先拿掉
  14. rem 根据最后项数值变化判断处于哪一级,
  15. rem 同级,升级,降级,做不同的处理,并排版。
  16. rem 排序也可以做,就是效率有点低,如果不影响就算了。
  17. if !n! lss %%4 (
  18. if not defined v%%1 (
  19. echo;!tab:~-%%4!"%%1":{
  20. set v%%1=1
  21. ) else (
  22. echo;!tab:~-%%4! %%2
  23. )
  24. set one=%%2
  25. set/a n=%%4
  26. ) else (
  27. if !n! gtr %%4 (
  28. set /a m=%%4+1
  29. rem $$$$$$ 修改了这里 $$$$$$$
  30. for /l %%a in (!n!,-1,!m!) do (
  31. if defined one (
  32. echo;!tab:~-%%a! "!one!":{}&set one=
  33. )
  34. echo;!tab:~-%%a!},
  35. set n=%%4
  36. )
  37. set one=%%2
  38. rem $$$$$$$ 修改了这里  $$$$$$
  39. ) else (
  40. if defined one (
  41. echo;!tab:~-%%4! "!one!":{},
  42. )
  43. set one=%%2
  44. )
  45. )
  46. ))
  47. )
  48. if defined one (
  49. echo;!tab:~-%n%! "!one!":{}&set one=
  50. )
  51. rem 收尾了,做 “}” 号对齐
  52. for /l %%a in (!n!,-1,1) do (
  53. echo;!tab:~-%%a!}
  54. )
  55. echo;}
  56. pause
复制代码

作者: slimay    时间: 2021-12-18 00:26

本帖最后由 slimay 于 2021-12-18 00:30 编辑

回复 12# 523066680
主要C语言写起来,得一个字符一个字符解析, 感觉还是用脚本好点。脚本思路清晰。
作者: 523066680    时间: 2021-12-18 18:04

本帖最后由 523066680 于 2021-12-18 18:46 编辑

回复 3# flashercs

用你的方案尝试重写,在遇到这种情况的时候做了一些思考
  1.       [ 0, 30, "安全防护", 1 ],
  2.       [ 30, 3011, "视频监控", 2 ],
  3.       [ 3011, 200327188, "视频监控配件", 3 ],
  4.       [ 0, 21, "办公、文化及教育用品", 1 ],
复制代码
如果从第三层跳回第一层,需要两次 pop,那应该也可以直接调取前两层的节点引用,直接修改。
于是发现 push 和 pop 也是可以不要的,用一维数组存储相应层"最近"的节点,无论当前处理到哪一层,随意调取指定层的最新节点(通过引用)进行处理,然后更新。

以上代码假设节点顶部从 "0" 开始;表单是按树结构顺序排列的,也就是 [0, 1, label, level] 一定在 [1, 201, label, level] 之前。

附完整类目表单:
Category_Plain.json
作者: 523066680    时间: 2021-12-18 19:10

本帖最后由 523066680 于 2021-12-18 19:41 编辑

原来写的方案之一


$tree 是将要创建的结构体
$ref 是一个协助构建$tree层级关系的哈希表。考虑类目所有ID的唯一性,所有ID都可以通过 $ref->{$id} 查到对应 $tree 中相应的引用位置。
于是:
  1.     if ( not exists $ref->{$foo}{$bar} )
  2.     {      
  3.         $ref->{$foo}{$bar} = {};              # $ref->{$foo} 得到 $tree 中 $foo 键的引用,新增{$bar}子键的操作直接作用于 $tree 的对应节点
  4.         $ref->{$bar} = $ref->{$foo}{$bar};    # 将 $bar 节点更新到引用表单
  5.     }
复制代码
优点是关联数据的表单可以随意打乱,最终都能得到完整结果。
缺点是需要确保表单中的层级(第四项)是升序的,这个通过 sort { $a->[3] <=> $b->[3] } @{$data->{data}} 对层级排序,
以及空间复杂度比15楼多了一个n
作者: flashercs    时间: 2021-12-19 00:42

回复 15# 523066680


    数据来源应该可以控制是树的遍历顺序是 pre-order 或post-order; 固定pre-order 就可以用此法.
作者: 523066680    时间: 2021-12-19 18:24

本帖最后由 523066680 于 2021-12-19 19:24 编辑

回复 13# netbenton

    把你的方案翻译成其他语言,加载改用JSON解析器一次性加载(逐行解析相对耗时)
处理过程是复刻你的逻辑,实测70W行数据只需要0.9秒完成输出(到文件)


15楼代码 1.3秒
16楼代码 2.2秒
  1. use Modern::Perl;
  2. use File::Slurp;
  3. use Time::HiRes qw/time/;
  4. use JSON qw/from_json/;
  5. use feature 'signatures';
  6. no warnings 'experimental::signatures';
  7. STDOUT->autoflush(1);
  8. my $ta = time();
  9. my $n = 0;
  10. open my $FH, ">:raw", "Category_Tree_benton.json";
  11. say $FH "{";
  12. my %hash;
  13. my $prev;
  14. my $raw = read_file( "gener_big.json" );
  15. my $data = from_json( $raw, {relaxed => 1} );
  16. for my $e ( @{$data->{data}} )
  17. {
  18.     my ( $parent, $child, $label, $lv ) = @$e;
  19.     next unless defined $lv;
  20.     if ( $n < $lv )
  21.     {
  22.         if ( not defined $hash{$parent} )
  23.         {
  24.             say $FH "\t"x$lv, qq("$parent"), ":{";
  25.             $hash{$parent} = 1;
  26.         }
  27.         else
  28.         {
  29.             say $FH "\t"x($lv+1), $child;
  30.         }
  31.         $prev = $child;
  32.         $n = $lv;
  33.     }
  34.     elsif ( $n > $lv )
  35.     {
  36.         my $m = $lv + 1;
  37.         for my $e ( reverse ($m .. $n)  )
  38.         {
  39.             if ( defined $prev ) {
  40.                 say $FH "\t"x($e+1), qq("$prev"), ":{}" ;
  41.                 undef $prev;
  42.             }
  43.             say $FH "\t"x$e, "},";
  44.             $n = $lv;
  45.         }
  46.         $prev = $child;
  47.     }
  48.     else
  49.     {
  50.         if ( defined $prev ) {
  51.             say $FH "\t"x($lv+1), qq("$prev"), ":{},";
  52.         }
  53.         $prev = $child;
  54.     }
  55. }
  56. if ( defined $prev )
  57. {
  58.     say $FH "\t"x$n, qq("$prev"), ":{}";
  59.     undef $prev;
  60. }
  61. # 收尾
  62. grep { say $FH "\t"x$_, "}"; } reverse ( 0 .. $n );
  63. close $FH;
  64. time_delta(\$ta);
  65. sub time_delta ($t)
  66. {
  67.     printf "Time Delta: %.2f\n", time() - $$t;
  68.     $$t = time();
  69. }
复制代码

作者: tigerpower    时间: 2022-1-20 14:13

升级、降级、跳级都可以。打乱列表次序也可以。
  1. #python 3
  2. import json, networkx as nx
  3. with open("Category_Plain.json") as f:
  4.     el = [i[:2] for i in json.load(f)['data']]
  5.     g = nx.from_edgelist(el, create_using=nx.DiGraph())
  6.     print(json.dumps(nx.tree_data(g, root=0), indent=2))
复制代码





欢迎光临 批处理之家 (http://bathome.net./) Powered by Discuz! 7.2