SPL=Surpass Python Language
6 回帖  •  359 浏览  • 
已解决      ...

Parent-Child 层级展开

 
集算器(187)

大佬们，下午好😄 😄
我有这么一个问题，恳请大佬们有空的时候看看有没有更加简洁高效的实现方式。如下所示，要把左边的两列数据转换成右边的形式。左侧数据源中 1/1 是 1 的 Child,1/1/1 是 1/1 的 Child…以此类推。

imagepng

为了方便测试，数据源如下所示，可以复制使用：

1	1/1
1	1/2
1	1/3
1/1	1/1/1
1/1	1/1/2
1/1/1	1/1/1/1
2	2/1
2	2/2
2	2/3
2/1	2/1/1
2/1	2/1/2
2/1/2	2/1/2/1
2/1/2	2/1/2/2
2/1/2	2/1/2/3
2/2	2/2/1
2/2	2/2/2

我写的 spl 语句如下:

=spl("=(x=?).select(!x.(~(2)).contain(~(1))).id(~(1)).([~])
=99.iterate((i=~,~~.news([P=~].insert(0,s=x.select(~(1)==P.m(i)));(x.delete(s),if(#>1,P.(null).insert(0,~.m(2)),P))).(#1)),A1,x==[])
",B2:C17)

简单解释一下：上述语句中 x 代表数据源，首先选出第一列 (父级) 中不存在于第二列 (子级) 中的值，也就是先确定最顶级的值[[1],[2]]，然后再从数据源 x 的第一列中选出等于当前子级的数据后做笛卡尔积展开，同时从数据源中删除掉选出的值，进入下一轮迭代，直到数据源删完变成空后，迭代停止。很常规的思路，更谈不上算法，所以效率很一般，特别是 select 时的全表遍历复杂度应该很高，虽然每一次的遍历量都在减少，但感觉对整体的时间复杂度助力不大。spl 中有相关的 prior 和 nodes 函数，但这两个函数的运用我一直没吃透，运用起来有点费劲。所以不得已用 iterate 按条件迭代 99 次，这样不烧脑。

还有一种方法是深度优先遍历，用递归回溯，不知道会不会快一些：

A B C D
1 1 1/1 1 1/2 1 1/3 1/1 1/1/1 1/1 1/1/2 1/1/1 1/1/1/1 2 2/1 2 2/2 2 2/3 2/1 2/1/1 2/1 2/1/2 2/1/2 2/1/2/1 2/1/2 2/1/2/2 2/1/2 2/1/2/3 2/2 2/2/1 2/2 2/2/2
2 =A1.import@fw() =A2.select(isdigit(~(1))) =B2.id(~(1)).conj() C2 的值表示最顶级 ["1","2"]
3 func B3 表示递归最终结果 C3 表示递归临时路径
4 =A2.pselect@a(~(1)==A3) B4 的值表示位置，用位置索引
5 if B4==[] >C3.insert(0,A3) 找不到位置时把当前值插入临时路径
6 >B3.insert(0,[C3.m(:)]) 此时要把临时路径插入结果集
7 >C3.delete(-1) 同时临时路径要弹出刚插入的值，回溯
8 for B4 >v=A2.m(B8)(2) 下一个进入递归的值
9 >C3.insert(0,A3) if 语句避免重复插入结果，因为结果结构特殊，所以递归时也要对结果集赋值
10 if #B8==1 >B3.insert(0,[C3.m(:)])
11 >C3.run(~=null) 如果不需要相同的为空可省略此步赋值为空
12 >func(A3,v,B3,C3) 递归
13 >C3.delete(-1) 临时路径弹出插入的值，回溯
14 return B3
15 =C2.conj(func(A3,~,[],[]))
16 =E@pb(A15).array().m(2:)
17 =E@pb(A16)

越琢磨越复杂。恳请大佬们有兴趣有闲时出手指点一下，给予帮助，谢谢！

集算器(187)