Parent Child Hierarchies (II)

螺旋矛盾 / / M套路108式, 困难

第二章的主题为在最大层数MaxLv未知的情况下构建和展开路径图，在开始之前需要讲解如何使用生成数据（第一章节的内容）的附件。首先，请把附件中Data文件夹解压至C:\中。然后，请按以下表格的指示更新文件夹中每一个工作簿的A2单元格后按下快捷键Alt+A+R+A:

工作簿名称工作表名称旧值新值
DB1.xlsxRow44
DB2.xlsxRow4100
DB3.xlsxRow41,000
DB4.xlsxRow410,000
DB5.xlsxRow4100,000
DB6.xlsxRow41,000,000

完成更新后的DB5.xlsx和DB6.xlsx的行数比较多，如果使用这两个工作簿作为数据源建议使用64位的Excel2016或者更新的版本。打开DB1.xlsx并激活Data工作表，如下表格为当前工作表A1:B5单元格的值：

上图所示的隶属关系意味着最大层数MaxLv为4, 行数Row为4, 以及组数为1.为了方便讲解代码，将以上图所表达的隶属关系为例讲解代码。在此前提下，本文所指的路径图为：

Path
A000001
A000001|B000001
A000001|B000001|C000001
A000001|B000001|C000001|D000001

路径图的展开指的是由以上表格到以下表格的转换：

Lv1Lv2Lv3Lv4
A000001A000001A000001A000001
A000001B000001B000001B000001
A000001B000001C000001C000001
A000001B000001C000001D000001

读者可以在附件中的Solution Step by Step.xlsm找到逐步完成以上转换的代码。其中的查询Filename为一文本值，该文本值对应当前载入的数据源名称(DB1.xlsx).

查询Data为一表格，该表格为数据源。

首先，需要把数据源表格Data分为两组，其中一组（TopParent）只含有处于最顶层的成员，其余的成员置于另一组(NonTopParent)。以下为把最顶层的成员分离出来的代码：

let
    Source = Table.SelectRows( Data, each [Parent] = [Child] )
in
    Source

以上代码的意思为筛选出Parent与Child相等的行出来。以下为把其他成员分为另一组的代码：

let
    Source = Table.SelectRows( Data, each [Parent] ˂˃ [Child] )
in
    Source

以上代码的意思为筛选出Parent与Child不相等的行出来。不难发现，处于最顶层的成员的路径图就是Child列或者Parent列本身。由于之后用不上Parent列，所以只要把Parent列的名称改为"Path"就做好这层的路径图（查询的名称记为Lv1Path）：

let
    Source = Table.RenameColumns( TopParent, { "Parent", "Path" } )
in
    Source

以下为构建下一层的路径图需要使用的代码（查询的名称记为Lv2Path）：

let
    InnerJoin=
        Table.NestedJoin(
            NonTopParent,
            "Parent",
            Lv1Path,
            "Child",
            "NTable",
            JoinKind.Inner
        ),
    Expansion=
        Table.ExpandTableColumn(
            InnerJoin,
            "NTable",
            {"Path"},
            {"PrePath"}
        ),
    AddCol=
        Table.AddColumn(
            Expansion,
            "Path",
            each
                Text.Combine(
                    {
                        [PrePath],
                        "|",
                        [Child]
                    }
                ),
            type text
        ),
    RemoveCol=
        Table.RemoveColumns(
            AddCol,
            { "Parent", "PrePath" }
        )
in
    RemoveCol

处于第二层的成员的Parent等于处于顶层的成员的Child，代码中的InnerJoin步骤就是利用这一点通过内连接把第二层的成员从NonTopParent表格中找出来。因为第二层的路径图需要基于第一层的路径图才能构造出来，所以需要把内嵌的Lv1Path的Path列展开并重命名为"PrePath"。之后，只要添加一计算列把PrePath的文本与Child的文本连接起来就完成第二层路径图的构造。最后，把接下来用不上的Parent列与PrePath列移除。以下为查询Lv2Path的结果：

不难发现，此时NonTopParent的第一行在接下来的步骤中已经用不上，为了减少接下来内连接中左表的行数，需要使用左反连接把该行移除，以下为对应的代码（查询的名称记为Lv3Lv4）：

let
    Source=
        Table.NestedJoin(
            NonTopParent,
            "Child",
            Lv2Path,
            "Child",
            "NTable",
            JoinKind.LeftAnti
        ),
    RemoveCol=
        Table.RemoveColumns(
            Source,
            "NTable"
        )
in
    RemoveCol

因为Child列的值不重复，所以在左反连接中设定了Child列为左反连接的键。连接完成后，会多出不需要的NTable列，所以在最后需要使用Table.RemoveColumns()移除该列。以下为查询Lv3Lv4的结果：

以下为构建第三层的路径图需要使用的代码（查询的名称记为Lv3Path）：

let
    InnerJoin=
        Table.NestedJoin(
            Lv3Lv4,
            "Parent",
            Lv2Path,
            "Child",
            "NTable",
            JoinKind.Inner
        ),
    Expansion=
        Table.ExpandTableColumn(
            InnerJoin,
            "NTable",
            {"Path"},
            {"PrePath"}
        ),
    AddCol=
        Table.AddColumn(
            Expansion,
            "Path",
            each
                Text.Combine(
                    {
                        [PrePath],
                        "|",
                        [Child]
                    }
                ),
            type text
        ),
    RemoveCol=
        Table.RemoveColumns(
            AddCol,
            { "Parent", "PrePath" }
        )
in
    RemoveCol

处于第三层的成员的Parent等于处于第二层的成员的Child，代码中的InnerJoin步骤就是利用这一点通过内连接把第三层的成员从Lv3Lv4表格中找出来。因为第三层的路径图需要基于第二层的路径图才能构造出来，所以需要把内嵌的Lv2Path的Path列展开并重命名为"PrePath"。之后，只要添加一计算列把PrePath列的文本与Child列的文本连接起来就完成第三层路径图的构造。最后，把接下来用不上的Parent列与PrePath列移除。以下为查询Lv3Path的结果：

不难发现，此时Lv3Lv4表格的第一行在接下来的步骤中已经用不上，为了减少接下来内连接中左表的行数，需要使用左反连接把该行移除，以下为对应的代码（查询的名称记为Lv4）：

let
    Source=
        Table.NestedJoin(
            Lv3Lv4,
            "Child",
            Lv3Path,
            "Child",
            "NTable",
            JoinKind.LeftAnti
        ),
    RemoveCol=
        Table.RemoveColumns(
            Source,
            "NTable"
        )
in
    RemoveCol

因为Child列的值不重复，所以在左反连接中设定了Child列为左反连接的键。连接完成后，会多出不需要的NTable列，所以在最后需要使用Table.RemoveColumns()移除该列。以下为查询Lv4的结果：

以下为构建第四层的路径图需要使用的代码（查询的名称记为Lv4Path）：

let
    InnerJoin=
        Table.NestedJoin(
            Lv4,
            "Parent",
            Lv3Path,
            "Child",
            "NTable",
            JoinKind.Inner
        ),
    Expansion=
        Table.ExpandTableColumn(
            InnerJoin,
            "NTable",
            {"Path"},
            {"PrePath"}
        ),
    AddCol=
        Table.AddColumn(
            Expansion,
            "Path",
            each
                Text.Combine(
                    {
                        [PrePath],
                        "|",
                        [Child]
                    }
                ),
            type text
        ),
    RemoveCol=
        Table.RemoveColumns(
            AddCol,
            { "Parent", "PrePath" }
        )
in
    RemoveCol

处于第四层的成员的Parent等于处于第三层的成员的Child，代码中的InnerJoin步骤就是利用这一点通过内连接把第四层的成员从Lv4表格中找出来。因为第四层的路径图需要基于第三层的路径图才能构造出来，所以需要把内嵌的Lv3Path的Path列展开并重命名为"PrePath"。之后，只要添加一计算列把PrePath列的文本与Child列的文本连接起来就完成第四层路径图的构造。最后，把接下来用不上的Parent列与PrePath列移除。以下为查询Lv4Path的结果：

由于最大的层数被假设为未知的，移除内连接左表首行会再进行一次，以下为对应的代码（查询的名称被记为Lv5）:

let
    Source=
        Table.NestedJoin(
            Lv4,
            "Child",
            Lv4Path,
            "Child",
            "NTable",
            JoinKind.LeftAnti
        ),
    RemoveCol=
        Table.RemoveColumns(
            Source,
            "NTable"
        )
in
    RemoveCol

因为Child列的值不重复，所以在左反连接中设定了Child列为左反连接的键。连接完成后，会多出不需要的NTable列，所以在最后需要使用Table.RemoveColumns()移除该列。以下为查询Lv5的结果：

由于最大的层数被假设为未知的，内连接会再进行一次产生一个空表触发跳出循环的条件，以下为对应的代码（查询的名称被记为Lv5Path）:

let
    InnerJoin=
        Table.NestedJoin(
            Lv5,
            "Parent",
            Lv4Path,
            "Child",
            "NTable",
            JoinKind.Inner
        ),
    Expansion=
        Table.ExpandTableColumn(
            InnerJoin,
            "NTable",
            {"Path"},
            {"PrePath"}
        ),
    AddCol=
        Table.AddColumn(
            Expansion,
            "Path",
            each
                Text.Combine(
                    {
                        [PrePath],
                        "|",
                        [Child]
                    }
                ),
            type text
        ),
    RemoveCol=
        Table.RemoveColumns(
            AddCol,
            { "Parent", "PrePath" }
        )
in
    RemoveCol

处于第五层的成员的Parent等于处于第四层的成员的Child，代码中的InnerJoin步骤就是利用这一点通过内连接把第五层的成员从Lv5表格中找出来。但是因为Lv5表格是个空表，所以内连接的结果也是一个空表。之后的列展开，添加计算列和移除计算列能成功进行，不过结果也是一个空表。以下为的查询Lv5Path的结果：

要对Lv1Path进行向右展开，首先需要提取Path列使之转化为串列，然后利用List.Repeat()使{"A0000001"｝转化为{"A0000001","A0000001","A0000001","A0000001"｝，以下为对应的代码和结果(查询的结果记为Lv1List)：

let
    Source = Table.Column( Lv1Path, "Path" ),
    Repetition = List.Repeat( Source, 4 )
in
    Repetition

要对Lv2Path进行向右展开，首先需要提取Path列使之转化为串列，之后通过深化取出第一项的值"A0000001|B0000001"，并通过Text.Split()把该值转化为{"A0000001"，"B0000001"}。然后，利用List.Repeat()使{"A0000001","B0000001"｝转化为{"A0000001","B0000001","A0000001","B0000001","A0000001","B0000001"｝后利用List.Alternate()使之转换为{"A0000001","B0000001","B0000001","B0000001"｝。以下为对应的代码(查询的结果记为Lv2List)：

let
    Source = Table.Column( Lv2Path, "Path" ),
    ToList = Text.Split( Source{0}, "|" ),
    Repetition = List.Repeat( ToList, 3 ),
    Outcome = List.Alternate( Repetition, 1, 1, 2 )
in
    Outcome

要对Lv3Path进行向右展开，首先需要提取Path列使之转化为串列，之后通过深化取出第一项的值"A0000001|B0000001|C000001"，并通过Text.Split()把该值转化为{"A0000001","B000001", "C0000001"}。然后，利用List.LastN()把该串列转化为{"C0000001"}，最后把{"A0000001","B000001", "C0000001"}与{"C0000001"}连接起来得到{"A0000001","B000001", "C0000001","C0000001"}，以下为对应的代码（查询的名称记为Lv3List）：

let
    Source = Table.Column( Lv3Path, "Path" ),
    ToList = Text.Split( Source{0}, "|" ),
    LastN = List.LastN( ToList,1 ),
    Outcome = List.Combine( { ToList, LastN } )
in
    Outcome

要对Lv4Path进行向右展开，首先需要提取Path列使之转化为串列，之后通过深化取出第一项的值"A0000001|B0000001|C000001|D0000001"，并通过Text.Split()把该值转化为{"A0000001","B000001", "C0000001","D0000001}。以下为对应的代码（查询的名称记为Lv4List）:

let
    Source = Table.Column( Lv4Path, "Path" ),
    ToList = Text.Split( Source{0}, "|" )
in
    ToList

最后只要把{Lv1List, Lv2List, Lv3List, Lv4List}代入Table.FromRows()就能得到目标表格。以下为对应的代码（查询的名称记为Outcome）:

let
    Source=
        Table.FromRows(
                {
                    Lv1List,
                    Lv2List,
                    Lv3List,
                    Lv4List
                },
            type table [Lv1=text, Lv2=text, Lv3=text, Lv4=text]
        )
in
    Source

接下来要引入循环把以上孤立的转换联系起来，对应的代码可以在附件的Solution1.xlsm中找到。首先还是要把处于顶层的成员找出来（查询的名称记为FilterLv1）：

let
    Source=
        Table.RenameColumns(
            Table.SelectRows(
                Data,
                each [Child] = [Parent]
            ),
            { "Parent", "Path" }
        )
in
    Source

以上代码的意思为把Child列与Parent列相同的成员从Data表中找出，然后把筛选结果的Parent列的列名称改为"Path"。之后，需要把不处于最顶层的成员从Data表中找出来：

let
    Source=
        Table.SelectRows(
            Data,
            each [Child] ˂˃ [Parent]
        )
in
    Source

不处于最顶层的成员的Parent列与Child列不相等，Table.SelectRows()就是利用这一逻辑关系把这些成员归为一组。完成分组后就可以开始路径图的构建，以下为对应的代码(查询的名称记为Path)：

let
    SList=
        List.Buffer(
            List.Generate(
                ()=˃{ FilterNonLv1, FilterLv1 },
                each not Table.IsEmpty( _{1} ),
                each
                    if
                        Table.IsEmpty( _{0} )
                    then
                        { #table( {}, {} ), #table( {}, {} ) }
                    else
                        let
                            TempRecordList=
                                List.Buffer(
                                    Table.TransformRows(
                                        Table.RemoveColumns(
                                            Table.ExpandTableColumn(
                                                Table.NestedJoin(
                                                    _{0},
                                                    "Parent",
                                                    _{1},
                                                    "Child",
                                                    "NTable",
                                                    JoinKind.Inner
                                                ),
                                                "NTable",
                                                {"Path"}
                                            ),
                                            "Parent"
                                        ),
                                        (x)=˃
                                            Record.TransformFields(
                                                x,
                                                {
                                                    "Path",
                                                    each
                                                        Text.Combine(
                                                            {
                                                                _,
                                                                "|",
                                                                x[Child]
                                                            }
                                                            
                                                        )
                                                }
                                            )
                                    )
                                )
                        in
                            {
                                Table.RemoveMatchingRows(
                                    _{0},
                                    TempRecordList,
                                    "Child"
                                ),
                                Table.FromRecords(
                                    TempRecordList,
                                    type table [Child=text, Path=text]
                                )
                            },
                each _{1}
            )
        )
in
    SList

如下图所示，以上代码对应之前逐步转换的Lv1Path到Lv5Path。

虽然本文假设的MaxLv为4，但是由于右表（左右是相对内连接而言）为空时才会触发List.Generate()跳出循环，实际循环次数为MaxLv+1=5。为了减少在最后一次循环中右表产生空表所需要的时间，以上代码引入了if..then..else使左表为空时强制右表为空。因为通过Table.NestedJoin()实现的左反连接所需要的运行时间较长，因此以上代码使用了Table.RemoveMatchingRows()实现左反连接的效果。但是这个函数的第二个参数只接受结构为{[]..[]}的复合串列，为了减少重复运算以上代码使用了Table.TransformRows()代替Table.AddColumns()完成路径图的构建。为了减少代码运行的时间，需要在List.Generate()外面套一个List.Buffer()。出于类似的理由，也需要在Table.TransformRows()外面套一个List.Buffer()。不难发现，查询Path的结果{#table()..#table()}的元素个数等于MaxLv，因此可以把该结果代入List.Count()得出MaxLv（查询的名称记为MaxLv）:

let
    Source = List.Count( Path )
in
    Source

得到最大层数后就可以对构造的路径图进行展开，以下为对应的代码(查询的名称记为FillRight)：

let
    Source=
        List.Transform(
            List.Numbers( 0, MaxLv ),
            (x)=˃
                if
                    x = 0
                then
                    let
                        TempList1=
                            List.Transform(
                                List.Split(
                                    Table.Column( Path{ 0 }, "Path" ),
                                    1
                                ),
                                each List.Buffer( _ )
                            )
                    in
                        List.Transform(
                            TempList1,
                            (w)=˃ List.Repeat( w, MaxLv )
                        )
                else if
                    x ˂ MaxLv - 2
                then
                    let
                        TempValue1 = MaxLv - x,
                        TempValue2 = x + 1
                    in
                        List.Transform(
                            Table.Column( Path{ x }, "Path" ),
                            (y)=˃
                                List.Alternate(
                                    List.Repeat(
                                        Text.Split( y, "|" ),
                                        TempValue1
                                    ),
                                    x,
                                    1,
                                    TempValue2
                                )
                        )
                else if
                    x = MaxLv - 2
                then
                    List.Transform(
                        Table.Column( Path{ x }, "Path" ),
                        (y)=˃
                            let
                                TempList2 = Text.Split( y, "|" )
                            in
                                List.Combine(
                                    {
                                        TempList2,
                                        List.LastN( TempList2, 1 )
                                    }
                                )
                    )
                else
                    List.Transform(
                        Table.Column( Path{ x }, "Path" ),
                        (z)=˃ Text.Split( z, "|" )
                    )
        )
in
    Source

如下图所示，以上代码对应之前逐步转换的Lv1List至Lv4List。

唯一需要注意的是最顶层路径图的展开，按照正常的思路List.Transform( Path[Path], each List.Repeat( {_}, MaxLv ) )就可以完成展开了，但是运行起来貌似比使用List.Alternate()进行展开还要慢，所以使用了List.Split( Path[Path], 1 )把Path[Path]中的每一个元素化作串列再使用List.Repeat()完成展开。有趣的是，转化得来的串列还需要加上List.Buffer()才能达到减少运行时间的效果。完成路径图的展开后，把查询FillRight的结果带入Table.FromRows就完成所有的转换了：

let    
    ToTable=
        Table.FromRows(
            List.Combine( FillRight ),
            fnTableType( MaxLv )
        )
in
    ToTable

以上代码的fnTableType对应的代码为：

( ColCount as number )=˃
    let
        TableType=
            Expression.Evaluate(
                Text.Combine(
                    {
                        "type table [",
                        Text.Combine(
                            List.Transform(
                                List.Numbers( 1, ColCount ),
                                each
                                    Text.Combine(
                                        {
                                            "Lv",
                                            Text.From( _ ),
                                            "=text"
                                        }
                                        
                                    )
                            ),
                            ","
                        ),
                        "]"
                    }
                )
            )
    in
        TableType

以上函数，首先构造文本"type table [Lv1=text, Lv2=text, Lv3=text, Lv4=text]"，然后把该文本代入Expression.Evaluate()中使之转化为type table [Lv1=text, Lv2=text, Lv3=text]。实际上由于左反连接减少的运行时间小于使用Table.TransformRows()增加的时间，因此移除与左反连接相关的转换，运行时间反而会减少，以下为只使用内连接构造路径图的代码：

let
    Source=
        List.Buffer(
            List.Generate(
                ()=˃FilterLv1,
                each not Table.IsEmpty( _ ),
                each
                    Table.Buffer(
                        Table.RemoveColumns(
                            Table.AddColumn(
                                Table.ExpandTableColumn(
                                    Table.NestedJoin(
                                        FilterNonLv1,
                                        "Parent",
                                        _,
                                        "Child",
                                        "NTable",
                                        JoinKind.Inner
                                    ),
                                    "NTable",
                                    {"Path"},
                                    {"PrePath"}
                                ),
                                "Path",
                                each
                                    Text.Combine(
                                        {
                                            [PrePath],
                                            "|",
                                            [Child]
                                        }
                                    ),
                                type text
                            ),
                            { "Parent", "PrePath" }
                        )
                    )
            )
        )
in
    Source

如下图所示，以上代码对应圈中的查询：

以上代码中，由于每一次循环的结果都是一个表格，所以需要在该表格外面套一个Table.Buffer()才能达到减少运行时间的效果。如果对以上两种方法的运行时间感兴趣，可以打开附件Solution1.xlsm(Solution2.xlsm)然后按下Alt+F8再按下Alt+R。如下图所示，使用了左反连接的解法在不同行数的数据中运行所需要的时间为：

如下图所示，仅使用内连接的解法在不同行数的数据中运行所需要的时间为：

目前为止，M语言已经有多达900个函数，相信以上解法一定不是最好的。如果各位M语言爱好者有新的发现，希望能以留言方式与大家分享一下，文本会及时更新。

附件

打赏微海报分享

2 Replies to “Parent Child Hierarchies (II)”

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注