订座问题

有如下表格，共有3列。第一列记录了座位的编号，第二列记录了该座位处在第几排，最后一列如果是1时表明该座位已经被预定否则为0时代表该座位处于无人订座的状态。有一团体现需要订10个座位，需要所有的座位处于同一排并且是连着的，现在要求你根据这个表格把所有符合条件的组合（排号，起始号和结束号）筛选出来，供该团体参考。

这道题的常规解题思路非常简单，第一步把Seat_No处于当前行的Seat_No和当前行的Seat_No + 9之间的行筛选出来，然后看这些被筛选出来的行是否满足（1）行数有10行，（2）所有的Status都等于0以及（3）所有的Row_ID是否都等于当前行的Row_ID。如下为以上思路对应的代码：

let
    Filtering =
        Table.SelectRows(
            Data,
            (x)=˃
                let
                    Filtered_Tbl =
                        Table.SelectRows(
                            Data,
                            (y)=˃
                                y[Seat_No] ˃= x[Seat_No]
                            and
                                y[Seat_No] ˂= x[Seat_No] + 9
                        ),
                    
                    Result =
                        List.AllTrue(
                            {
                                Table.MatchesAllRows(
                                    Filtered_Tbl,
                                    (z)=˃
                                        z[Status] = 0
                                    and
                                        z[Row_ID] = x[Row_ID]
                                ),
                                Table.RowCount(Filtered_Tbl) = 10
                            }
                        )
                in
                    Result
        ),
    Cols_Selection =
        Table.SelectColumns(
            Filtering,
            {
                "Row_ID",
                "Seat_No"
            }
        ),
    Rename_Cols =
        Table.RenameColumns(
            Cols_Selection,
            {
                "Seat_No",
                "Start_No"
            }
        ),
    Add_Col =
        Table.AddColumn(
            Rename_Cols,
            "End_No",
            each [Start_No] + 9,
            Int64.Type
        )
in
    Add_Col

以上思路简单明了，但是即使在1万行的数据中运行所需的时间也非常之长。之所以会这样，笔者的看法是这个解法在每一次迭代中都需要从源数据中把符合条件的行筛选出来，假设源数据有1万行，整个迭代过程下来，涉及到的筛选次数会达到至少10的8次方次。

要有效地减少运行时间，最关键的一步在于利用分组，代码如下：

let
    Ten_Zeros =
        List.Repeat(
            {0},
            10
        ),
    Grouping =
        Table.Group(
            Data,
            "Row_ID",
            {
                "nTable",
                (x)=˃
                    let
                        All_Status =
                            List.Buffer(
                                Table.Column(
                                    x,
                                    "Status"
                                )
                            ),
                        Add_Col =
                            Table.AddColumn(
                                x,
                                "10_Seats",
                                (y)=˃
                                    List.Range(
                                        All_Status,
                                        y[Seat_No] - (y[Row_ID] - 1) * 1000 -1,
                                        10
                                    ),
                                type list
                            )
                    in
                        Add_Col,
                type table
                    [
                        Seat_No = Int64.Type,
                        Row_ID = Int64.Type,
                        Status = Int64.Type,
                        10_Seats = list
                    ]
            }
        ),
    Expansion =
        Table.ExpandTableColumn(
            Grouping,
            "nTable",
            {
                "Seat_No",
                "10_Seats"
            }
        ),
    Row_Selection =
        Table.SelectRows(
            Expansion,
            each [10_Seats] = Ten_Zeros
        ),
    Result =
        Table.AddColumn(
            Table.RenameColumns(
                Table.SelectColumns(
                    Row_Selection,
                    {
                        "Row_ID",
                        "Seat_No"
                    }
                ),
                {
                    "Seat_No",
                    "Start_No"
                }
            ),
            "End_No",
            each [Start_No] + 9,
            Int64.Type
        )
in
    Result

以上解法在以Row_ID为单位分组后，会把组内的所有Status以List的形式提取出来并命名为All_Status，然后再使用List.Range()从All_Status中把当前行以及之后9行的Status以List的形式提取出来并命名为10_Seats。在接下来的一步中，Table.ExpandTableColumn()把Row_ID和10_Seats展开。这时每一行都有3列，第一列为Row_ID, 第二列为座位编号Seat_No, 以及第三列为包括当前行的最近10个座位的订座情况。有了这些信息后，最后一步只需要比较第三列是否与{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}相等，如果相同说明座位编号始于当前行的Seat_No并结束于该Seat_No + 9的这十个座位都没有人预定。