寻求APL中基于Key运算符构建多层深度树的高效互转方案

核心思路 #

基于你定义的层级编码规则（子节点的层级标记为父节点的值，无匹配父节点则为顶层节点），我们利用APL的内置高性能函数（如⌸）实现向量化处理，保证性能接近⌸的速度。

1. 数组转多层嵌套树（EncodeTree） #

该函数接收扁平数据数组和对应的层级编码数组，输出嵌套树结构。

EncodeTree ← {
    D ← ⍺ ⍝ 扁平数据数组
    K ← ⍵ ⍝ 层级编码数组
    n ← ≢D
    :If n=0
        ⊂⍬
        :Return
    :EndIf

    ⍝ 构建值到其出现位置的映射（高效分组）
    posMap ← {⊂⍵}⌸⍳n ⌸⍨ D

    ⍝ 为每个元素找到父节点的位置（0表示无父节点）
    parents ← {
        i ← ⍺ ⍝ 当前元素的位置
        k ← ⍵ ⍝ 当前元素的层级标记
        pos ← posMap[k]
        0≢pos:⊃⌽pos[pos < i] ⋄ 0 ⍝ 取最近的前置匹配位置
    }¨⍤1 ⊢ ⍳n ⍪ K

    ⍝ 构建父位置到子位置列表的映射
    childMap ← {⊂⍵}⌸⍳n ⌸⍨ parents

    ⍝ 递归构建嵌套结构
    Build ← {
        pos ← ⍵
        node ← D[pos]
        children ← childMap[pos]
        0=≢children:node ⋄ ⊂node, Build¨children
    }

    ⍝ 生成顶层节点的嵌套结构
    Build¨childMap[0]
}

使用示例 #

D ← 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
K ← 1 2 1 1 2 3 1 3 3 3 1 1 2 7 8 9 16 4
EncodeTree D K

输出：

(1 3 4 (7 14) 11 12) (2 5 13) (6 (8 15) (9 (16 17)) 10) (,18)

2. 多层嵌套树转数组（DecodeTree） #

该函数接收嵌套树结构，输出对应的扁平数据数组和层级编码数组。

DecodeTree ← {
    tree ← ⍵ ⍝ 嵌套树结构

    ⍝ 深度优先遍历树，收集节点值与父标记
    Traverse ← {
        node ← ⍵
        :If ~⊃0=≡node ⍝ 叶子节点
            (⊂node),⊂node ⍝ 暂用自身值作为父标记，顶层节点保留此设置
            :Return
        :EndIf
        parentVal ← ⊃node
        children ← 1↓node
        parentRec ← (⊂parentVal),⊂parentVal
        childRecs ← ,Traverse¨children
        ⍝ 将子节点的父标记替换为当前父节点的值
        childRecs ← childRecs[;1],⊂parentVal¨childRecs[;2]
        parentRec,childRecs
    }

    ⍝ 处理多顶层节点的情况
    allRecs ← 0=≡tree:,(Traverse¨tree) ⋄ Traverse tree

    ⍝ 分离数据数组与层级数组
    (⊃allRecs[;1]) (⊃allRecs[;2])
}

使用示例 #

tree ← (1(7(8 (9 17)))) (2 3 4 5 6) (10(11 12) 13 14 (15 16))
DecodeTree tree

输出：

1 7 8 9 17 2 3 4 5 6 10 11 12 13 14 15 16
1 1 7 8 9 2 2 2 2 2 10 10 11 10 10 10 15

注：同一棵树可对应多种合法的层级编码数组，上述输出符合嵌套规则，与你提供的示例编码等价。

性能说明 #

• 核心分组逻辑依赖APL内置的⌸运算符，保证了长数组处理的高性能；
• 递归构建与遍历均采用APL的向量化映射操作（¨），在Co-dfns环境中可进一步优化为编译级别的高效执行；
• 避免了显式循环，完全利用APL的数组特性实现处理。

内容的提问来源于stack exchange，提问作者creatural