201611 SICP系列 第7讲 流计算模型 学习笔记 (二) - xiaoxianfaye/Learning GitHub Wiki

7 Stream

7.1 Name it – Stream

我们现在想要描述的是在那些方框中穿梭的那些流，那些Stream中流走的都是数据。一方面前面的编程方式导致我们没办法按照一个个流的处理方式组织程序；另一方面如果我们希望能够控制数据的话，肯定需要有一个名字，给它一个名字还不够，既然是数据抽象，还需要有一些方式能把它构建出来，还要有一些方式能把它的组成部分通过选择器选择出来。

Stream constructor and selector

Stream George's contract

Stream是在那些Enumerate、Map、Filter、Accumulator等方框中流走的数据。

上面第一幅图是Stream的构造器和选择器。对任意的X和Y，如果用cons_stream把它们粘合(glue)在一起，那么取head就是X，取tail就是Y。the_empty_stream()是从无到有的过程。is_empty_stream()是用于判断的选择器。

上面第二幅图是跟George签订的协议。应该加一条：is_empty_stream(the_empty_stream()) = true。不允许在the_empty_stream()上取head和tail。不可能用cons_stream()创建一个空流。从无到有一定是the_empty_stream()。cons_stream(the_empty_stream(), the_empty_stream())是把一个空流附加到一个空流上，出来的是只有一个元素的流，不是两个空流相加。

7.2 Operations on stream

7.2.1 Constructor & Selector of Stream (Using List Temporarily)

先暂时用List实现Stream的构造器和选择器，以便后续编写Stream的操作函数时可以写测试验证。

cons_stream(H, T) -> [H|T].
the_empty_stream() -> [].

head(S) -> hd(S).
tail(S) -> tl(S).
is_empty_stream(S) -> S =:= [].

7.2.2 Map on streams

map_stream(Proc, S) ->
    case is_empty_stream(S) of
        true ->
            the_empty_stream();
        false ->
            cons_stream(Proc(head(S)), map_stream(Proc, tail(S)))
    end.

test_map_stream() ->
    [2, 4] = map_stream(fun(X) -> X * 2 end, [1, 2]),
    test_map_stream_ok.

7.2.3 Filter on streams

filter_stream(F, S) ->
    case is_empty_stream(S) of
        true ->
            the_empty_stream();
        false ->
            case F(head(S)) of
                true ->
                    cons_stream(head(S), filter_stream(F, tail(S)));
                false ->
                    filter_stream(F, tail(S))
            end
    end.

test_filter_stream() ->
    [2, 4] = filter_stream(fun(X) -> X rem 2 =:= 0 end, [1, 2, 3, 4]),
    test_filter_stream_ok.

7.2.4 Accumulation on streams

acc_stream(Proc, A, S) ->
    case is_empty_stream(S) of
        true ->
            A;
        false ->
            Proc(head(S), acc_stream(Proc, A, tail(S)))
    end.

test_acc_stream() ->
    10 = acc_stream(fun(X, Y) -> X + Y end, 0, [1, 2, 3, 4]),
    10 = acc_stream_2(fun(X, Y) -> X + Y end, 0, [1, 2, 3, 4]),
    test_acc_stream_ok.

这里要稍微约定一下，A是初始值，Proc是两个参数的累积操作，S是流，先取出head，把剩下的部分用acc算出一个东西以后，把Proc应用在head元素和用acc算出的东西上。

Stream是一个递归定义的数据结构，对它的处理一定也是一个递归处理。返回的Acc可以是数，也可以是其他东西，取决于Proc。Acc在Stream为空流的情况下返回。

以列表[1,2,3]求和为例，展开递归计算过程如下：

  acc_stream('+', 0, [1, 2, 3])
= '+'(1, acc_stream('+', 0, [2, 3]))
= '+'(1, '+'(2, acc_stream('+', 0, [3])))
= '+'(1, '+'(2, '+'(3, acc_stream('+', 0, []))))
= '+'(1, '+'(2, '+'(3, 0)))
= '+'(1, '+'(2, 3))
= '+'(1, 5)
= 6

acc_stream()还有一种尾递归的写法，但这种写法不符合之前的约定。前面的递归写法类似于lists:foldr，尾递归的写法类似于lists:foldl。

acc_stream_2(Proc, A, S) ->
    case is_empty_stream(S) of
        true ->
            A;
        false ->
            acc_stream_2(Proc, Proc(head(S), A), tail(S))
    end.

仍以列表[1,2,3]求和为例，展开尾递归计算过程如下：

  acc_stream_2('+', 0, [1, 2, 3])
= acc_stream_2('+', '+'(1, 0), [2, 3])
= acc_stream_2('+', 1, [2, 3])
= acc_stream_2('+', '+'(2, 1), [3])
= acc_stream_2('+', 3, [3])
= acc_stream_2('+', '+'(3, 3), [])
= acc_stream_2('+', 6, [])
= 6

7.3 Enumerate the leaves of a tree (append_stream)

把一棵二叉树的叶子节点枚举出来，输入是二叉树，输出是个流。

单独看左树，enumerate出来是一个流，单独看右树，enumerate出来也是一个流，但cons_stream()左边是个元素。因此，在目前给定的构造器中，不能用cons_stream将两个流拼到一起。用append_stream(S1, S2)把S2追加到S1后面。

对单个数N，只有这一个叶子节点，它出来的流中应该只有一个元素N。在目前给定的构造器中，用cons_stream可以构造出只有一个元素的流，左边是N，右边是the_empty_stream。

append_stream(S1, S2) ->
    case is_empty_stream(S1) of
        true ->
            S2;
        false ->
            cons_stream(head(S1), append_stream(tail(S1), S2))
    end.

enumerate_tree({Left, Right}) ->
    append_stream(enumerate_tree(Left), enumerate_tree(Right));
enumerate_tree(N) ->
    cons_stream(N, the_empty_stream()).

test_append_stream() ->
    [1, 2, 3, 4] = append_stream([1, 2], [3, 4]),
    test_append_stream_ok.

test_enumerate_tree() ->
    [1, 2, 7, 19, 12, 14] = enumerate_tree({{1, {2, 7}}, {19, {12, 14}}}),
    test_enumerate_tree_ok.

通过类型思考，通过目前能够提供的算子思考，虽然逻辑还不是那么清楚，但除了这样写，找不到其他方式写。

7.4 Enumerate an interval

给定一个区间，产生这个区间的整数流。

enumerate_interval(Low, High) when Low > High ->
    the_empty_stream();
enumerate_interval(Low, High) ->
    cons_stream(Low, enumerate_interval(Low + 1, High)).

test_enumerate_interval() ->
    [1, 2, 3, 4] = enumerate_interval(1, 4),
    test_enumerate_interval_ok.

7.5 Procedures in stream’s view

Procedure1 from stream view

sum_odds_square_s(T) ->
    acc_stream(fun add/2, 0, 
               map_stream(fun square/1, 
                          filter_stream(fun is_odd/1, 
                                        enumerate_tree(T)))).

square(N) -> N * N.

add(X, Y) -> X + Y.

框图中非常清楚的程序概念和组织方式，跟下面的程序是能够完全一一对应的。

Procedure2 from stream view

odd_fibs_s(N) ->
    acc_stream(fun({Idx, _E}, A) -> [Idx|A] end, [], 
               filter_stream(fun is_odd_idx/1, 
                             map_stream(fun fib_idx/1, 
                                        enumerate_interval(1, N)))).

is_odd_idx({_Idx, E}) ->
    is_odd(E).

fib_idx(Idx) ->
    {Idx, fib(Idx)}.

7.6 Mix-Match & Conventional Interface

Mix match

这两幅图干的本来是不一样的事情，但从程序组织的范式角度来看，它们其实基本上是一样的，而且按照这种范式来组织以后，程序的组合性更加好了。模块化是为了能够构建出更复杂的程序来应对现实世界的复杂性，像这样的可以组装的方式应对复杂性的能力更强。

中间的方框可以随意替换，比如用“Enumerate Leaves”替换“Enumerate Interval”。完全可以混搭。大部分程序的生成范式、为软件写的测试的生成范式，都可以用上面的方式组装起来，例如大数据量的、重复性的测试，往往都是在测试数据上做一个映射变成另外一组数据，或者从中间获取或者正常、或者异常、超出门限的数据，然后再对它们进行一个统计等。可以带着这些想法重新审视一下原来写的程序。

语言的三要素：Primitive Elements、Means of Combination、Means of Abstraction。在我们这里，原生的(Primitive)元素是Stream，它是一个数据抽象，它有基本的构造手段和从中选择组成部分的选择子。然后，我们可以在上面做一些组合，把一个流经过映射变成另外一个流，也可以把这个流过滤形成一个流，还可以在这个流上做一些累积的计算。

7.7 Processing on stream of stream -- Flatten and Flatmap

有了一些组合以后，希望再往前走一步。到目前为止，流中的元素还是原生数据，流中的元素除了是原生数据以外，还可以是一个流，Stream of stream。

flatten的意思是把流拉平。流中的每一个元素都是一个Stream，flatten的输入参数是Stream of stream，输出结果是拉平后的一个流。

flatten(StOfSt) ->
    acc_stream(fun append_stream/2, the_empty_stream(), StOfSt).

test_flatten() ->
    [1, 2, 3, 4, 5] = flatten([[1, 2], [3, 4, 5]]),
    test_flatten_ok.

目前的map_stream，针对Stream的每一个元素产生一个新的元素，有时候希望针对Stream的每一个元素产生一个新的流，然后把这个流再拉平，即flatmap。flatmap的参数和map是一样的，接受一个Proc和Stream，Proc对Stream的每个元素产生一个新的Stream，即Stream of Stream，然后拉平产生一个新的Stream。

flatmap(P, S) ->
    flatten(map_stream(P, S)).

test_flatmap() ->
    [1, 2, 1, 2, 3] = flatmap(fun(X) -> lists:seq(1, X) end, [2, 3]),
    test_flatmap_ok.

7.8 A new way to do a familiar kind of problem

I J pair prime

给定一个整数N，找到这中间所有的I和J的Pair，I和J要满足0<J<I<=N并且I+J是素数。

prime_sum_pairs(N) ->
    filter_stream(
        fun({_, _, S}) -> 
            is_prime(S) 
        end, 
        flatmap(
            fun(I) -> 
                map_stream(
                    fun(J) -> 
                        {I, J, I + J} 
                    end, 
                    enumerate_interval(1, I - 1)) 
            end, 
            enumerate_interval(1, N))).

is_prime(N) -> is_prime(2, N).

is_prime(I, N) when I >= N -> 
    true;
is_prime(I, N) ->
    if
        N rem I =:= 0 ->
            false;
        true ->
            is_prime(I + 1, N)
    end.

test_is_prime() ->
    true = is_prime(2),
    true = is_prime(3),
    false = is_prime(4),
    true = is_prime(5),
    test_is_prime_ok.

test_prime_sum_pairs() ->
    [{2,1,3}, {3,2,5}, {4,1,5}, {4,3,7}, {5,2,7}] = prime_sum_pairs(5),
    test_prime_sum_pairs_ok.

7.9 Embedded Flatmap

用流的方式来考虑问题，再来一个练习。

Triples

triples(N) ->
    flatmap(
        fun(I) -> 
            flatmap(
                fun(J) -> 
                    map_stream(fun(K) -> {I, J, K} end, enumerate_interval(1, J - 1)) 
                end, enumerate_interval(1, I - 1)) 
        end, enumerate_interval(1, N)).    

test_triples() ->
    [{3,2,1}, 
     {4,2,1}, {4,3,1}, {4,3,2},
     {5,2,1}, {5,3,1}, {5,3,2}, {5,4,1}, {5,4,2}, {5,4,3}] = triples(5),
     test_triples_ok.

7.10 Eight Queens Problem

Eight queens problem

八皇后问题。希望找到一种排列方式，不能有两个皇后在同一行、不能有两个皇后在同一列、不能有两个皇后在同一个对角线。

给定8，求解摆放位置，即一组行列，例如图中的[{1, 6}, {2, 2}, {3, 7}, {4, 1}, {5, 4}, {6, 8}, {7, 5}, {8, 3}]。

George’s Contract：

  • the_empty_board()：空棋盘
  • is_safe(Row, Col, RestPositions)：新摆放的位置{Row, Col}和已有的位置(RestPositions)是否不冲突(不在同一行、不在同一列、不在对角线)。
  • adjoin_position(Row, Col, RestPositions)：如果不冲突，把新摆放的位置{Row, Col}和RestPositions合在一起。

7.10.1 Backtracking Search

AI中很有名的“回溯搜索”。(数独问题中是“依赖传播”)。

思路：

Eight queens problem backtracking

  1. 从第1行开始摆，有8种摆法，先摆在第1列，{Row1, Col1}；
  2. 再摆第2行，其实也有8种摆法，只是说这8种摆法是否合适要判断。
    1. 尝试摆在第1列，同一列不行，回到{Row1, Col1}；
    2. 尝试摆在第2列，对角线不行，回到{Row1, Col1}；
    3. 尝试摆在第3列，可以，摆在{Row2, Col3}。
  3. 再摆第3行(Row3)，其实也有8种摆法，只是说这8种摆法是否合适要判断。
    1. 尝试摆在第1列，同一列不行，回到{Row2, Col3}；
    2. 尝试摆在第2列，对角线不行，回到{Row2, Col3}；
    3. 尝试摆在第3列，同一列不行，回到{Row2, Col3}；
    4. 尝试摆在第4列，对角线不行，回到{Row2, Col3}；
    5. 尝试摆在第5列，可以，摆在{Row3, Col5}。
  4. 再摆第4行(Row4)……。

is_safe为true，就往下，is_safe为false，就往上回溯，上回试到哪儿了，就试它的下一个分支，如果8个分支都试完了还不行，要继续往上回溯……，直到8行都安全摆好。

与思路相对应的主要代码如下：

%% Backtracking, stop after the first solution gotten
bt_queen(N) ->
    bt_queen(N, 1, 1, the_empty_board()).

bt_queen(TR, CurRow, _CurCol, CurPos) when CurRow > TR ->
    CurPos;
bt_queen(TR, _CurRow, CurCol, CurPos) when CurCol > TR ->
    case split_position(CurPos) of
        {{LastRow, LastCol}, RestPos} ->
            bt_queen(TR, LastRow, LastCol + 1, RestPos);
        none ->
            no_solutions
    end;
bt_queen(TR, CurRow, CurCol, CurPos) ->
    NewPoses = adjoin_position(CurRow, CurCol, CurPos),
    case is_safe(NewPoses) of
        true ->
            bt_queen(TR, CurRow + 1, 1, NewPoses);
        false ->
            bt_queen(TR, CurRow, CurCol + 1, CurPos)
    end.

说明：

  1. 要保存的状态包括：正在做哪一行(CurRow)、正在做哪一列(CurCol)、已经摆好的位置(CurPos)，已经摆好的位置中隐含了要回退的状态。
  2. 以8皇后为例，
    1. 一开始棋盘上什么都没有(the_empty_board)，从第1行、第1列开始。
    2. 第三个匹配分支：是个一般情况，要把{CurRow, CurCol}摆到CurPos中，先adjoin_position连接一把，然后调用is_safe判断是否能摆，如果能摆，从下一行的第1列开始摆，并且CurPos是NewPoses；如果不能摆，从本行的下一列开始摆。
    3. 第二个匹配分支：CurCol可能会出现大于TR(8)的情况，都第9列了没有可摆的，说明这一行都尝试完了。split_position可能会出现两种情况：有{LastRow, LastCol}和什么都没有(none)。“什么都没有(none)”表示已经回溯到最上面了都没有解，所以是no_solutions。有{LastRow, LastCol}的情况下，要再往上回溯一层，行LastRow，列LastCol+1。
    4. 第一个匹配分支：当CurRow大于TR(TotalRow? 8)，说明能顺利地摆到第9行，那就说明已经摆好了。

代码看上去应该是这样，其实不简单，因为我们在考虑这个问题的时候，跟时间紧密关联。从某一层往上回溯的时候，要知道回溯到哪一个地方，也就是说，要记住刚才已经遍历过哪些内容，正因如此，整个计算和时间、已经遍历过的内容搅在一起，使得事情不是看上去那么简单。

其他代码：

split_position([]) -> none;
split_position(Pos) -> {hd(Pos), tl(Pos)}.

the_empty_board() -> [].

adjoin_position(Row, Col, RestPos) -> [{Row, Col} | RestPos].

is_safe([{Row, Col}|RestPos]) ->
    case lists:keyfind(Col, 2, RestPos) of
        false ->
            Diff = [{abs(Row - Row1), abs(Col - Col1)} || {Row1, Col1} <- RestPos],
            lists:all(fun({Dif, Dif}) -> false; 
                         (_) -> true
                      end, Diff);
        _ -> 
            false
    end.

test_bt_queen() ->
    [{8, 4}, {7, 2}, {6, 7}, {5, 3}, {4, 6}, {3, 8}, {2, 5}, {1, 1}] =  bt_queen(8),

    no_solutions = bt_queen(3),

    [{4, 3}, {3, 1}, {2, 4}, {1, 2}] = bt_queen(4),

    test_bt_queen_ok.

关于is_safe/1，没有判断行，是因为本来就是一行一行往下摆的，行是不可能冲突的，所以只要判断对角线和列就可以了。

上面的代码只算出八皇后的一个解。想要八皇后的所有解，目前的状态不够，至少还需要一个保存所有解的列表。CurPos既是返回值，也保存了回溯路径，保存所有解的列表同时也保存了所有的回溯路径。

  1. 第一个匹配分支，说明只是找到了一个解，把这个CurPos放到保存所有解的列表中，并继续尝试LastRow的LastCol+1。
  2. 第二个匹配分支，有{LastRow, LastCol}的情况，代码不用做任何修改，什么都没有(none)的情况，说明已经回溯尝试到最上面了，如果保存所有解的列表不为空，则返回所有解，如果为空，则是no_solutions。
  3. 第三个匹配分支，也不用做任何修改。
%% Backtracking, all solutions
bt_queen_2(N) ->
    bt_queen_2(N, 1, 1, the_empty_board(), []).

bt_queen_2(TR, CurRow, _CurCol, CurPos, Solutions) when CurRow > TR ->
    [{LastRow, LastCol} | RestPos] = CurPos,
    bt_queen_2(TR, LastRow, LastCol + 1, RestPos, [CurPos|Solutions]);
bt_queen_2(TR, _CurRow, CurCol, CurPos, Solutions) when CurCol > TR ->
    case split_position(CurPos) of
        {{LastRow, LastCol}, RestPos} ->
            bt_queen_2(TR, LastRow, LastCol + 1, RestPos, Solutions);
        none ->
            if
                Solutions =:= [] -> no_solutions;
                true -> Solutions
            end
    end;
bt_queen_2(TR, CurRow, CurCol, CurPos, Solutions) ->
    NewPoses = adjoin_position(CurRow, CurCol, CurPos),
    case is_safe(NewPoses) of
        true ->
            bt_queen_2(TR, CurRow + 1, 1, NewPoses, Solutions);
        false ->
            bt_queen_2(TR, CurRow, CurCol + 1, CurPos, Solutions)
    end.

test_bt_queen_2() ->
    92 = length(bt_queen_2(8)),
    2 = length(bt_queen_2(4)),
    no_solutions = bt_queen_2(3),

    test_bt_queen_2_ok.

7.10.2 Recursive Strategy

为什么觉得BackTracking复杂，是因为在这个过程中要考虑状态，而状态会随着时间变化。在树的搜索过程中，要记住整个路径，要记住在某一层搜索到了哪儿，回退时才能回退到合适的地方，还要不断往上回退……，在每个时刻需要记住的东西特别多。

我们换一种思路，不这样去看整个计算过程。在回溯方式中，整个过程看上去有点像一棵树，但这棵树是一步一步的方式在生成。换个方式，不考虑一点一点去改变状态、去生成这棵树。用“流”的方式思考。

现在要一行一行摆，假设手里已经有了前面K行已经摆好(safe)的东西，怎么摆的不管，现在来摆第K+1行，怎么摆呢？

第K行的每一个元素在第K+1行都会有8种摆法，从中过滤出Safe的摆法，就是第K+1行的摆法。

这是一种递归的解决思路。这种思路是可行的，因为K行摆好了，K+1行就摆好了；K-1行摆好了，K行就摆好了，一直往上……，直到第0行。摆到第0行是empty_board，也就是说，总能摆到一个base，这个base肯定有解。根据我们的推导，如果base有解的话，往下一层也有解……。

递归的解题思路之所以能够解决是因为问题的规模在不断缩小，一直缩小到问题肯定能有解，这个问题肯定能有解的情况是空棋盘，空棋盘什么都不用摆就解决了。

递归问题的解决在于规模在降解，重要的是规模不但在降解，而且规模降解到base case的时候是能够找到解决路径的，就可以把这个问题给解决了，递归问题就有可能是有解的。

回溯方式的复杂性在于把时间直接考虑其中，递归方式中不是一步一步生成树，和时间不相关。

%% Recursive, all solutions
re_queen(N) -> fill_rows(N, N).

fill_rows(_Size, 0) ->
    cons_stream(the_empty_board(), the_empty_stream());
fill_rows(Size, Row) ->
    filter_stream(
        fun is_safe/1,
        flatmap(
            fun(RestPos) ->
                map_stream(
                    fun(Col) ->
                        io:format("re_queen Row ~p Col ~p RestPos ~p~n", 
                                  [Row, Col, RestPos]),
                        adjoin_position(Row, Col, RestPos)
                    end, 
                    enumerate_interval(1, Size))
            end, 
            fill_rows(Size, Row - 1))).

test_re_queen() ->
    92 = length(re_queen(8)),
    2 = length(re_queen(4)),
    [] = re_queen(3),

    test_re_queen_ok.

说明：

  1. 一行一行摆：fill_rows(Size, Row)，从第8行开始摆。
  2. fill_rows是一个递归程序，递归程序有规模降解，其base case是第0行的时候，fill_rows(_Size, 0)，首先这个解法是一个流，只不过针对0来说，这个流中只有一个元素the_empty_board。
  3. 当Row≠0时，Row行依赖于前Row-1行，fill_rows(Size, Row-1)是前Row-1行的摆法，写一个函数针对它产生一个新的流，首先要知道列的位置，enum_interval(1, Size)产生列Col，这个Col和Row合在一起就是一个新的Position，用adjoin_position将这个新的Position和已有的RestPos连接在一起，产生一个新的流。也就是说针对第Row-1行每个位置去扩展第Row行中每一列的位置，然后再flatmap和filter。
  4. 递归方式会穷举出所有解法。

7.10.3 Back tracking Search vs. Recursive Strategy

  1. 在回溯方式中，在每一步过程中都要记住进行到了哪一步，要回退的时候要从哪一步开始回退，跟时间、跟执行顺序是紧密相关的。
  2. 在递归方式中，假设前K行已经摆好了，第K行的每一个元素在第K+1行都会有8种摆法，罗列出第K+1行所有摆法，从中过滤出Safe的摆法，就是第K+1行的摆法。
  3. 递归方式和回溯方式最大的不同是：不需要记住上一次的状态。这是看问题的视角的不同。在回溯方式中，把计算过程当作具有和时间相关的状态的计算过程，而在递归方式中已经看不到这些了。迭代过程中的那些参数就是状态，这就是为什么把递归程序转成迭代程序时要很清楚其中的状态的原因。我们改变了我们自己本身看问题的视角，不再把计算过程看作具有和时间相关的状态的计算过程，使得程序写起来更简单、更清晰、更优雅。

7.10.4 If you swap the traversing order

在前面的代码中，遍历的顺序是RestPos -> Col，如果我们调换一下遍历的顺序Col -> RestPos，同时用timer:tc测试一下两种写法。

re_queen_2(N) -> fill_rows_2(N, N).

fill_rows_2(_Size, 0) ->
    cons_stream(the_empty_board(), the_empty_stream());
fill_rows_2(Size, Row) ->
    filter_stream(
        fun is_safe/1,
        flatmap(
            fun(Col) ->
                map_stream(
                    fun(RestPos) -> 
                        io:format("re_queen_2 Row ~p Col ~p RestPos ~p~n", 
                                  [Row, Col, RestPos]),
                        adjoin_position(Row, Col, RestPos)
                    end, 
                    fill_rows_2(Size, Row - 1))
            end, 
            enumerate_interval(1, Size))).

test_re_queen_2() ->
    92 = length(re_queen_2(8)),
    2 = length(re_queen_2(4)),
    [] = re_queen_2(3),

    test_re_queen_2_ok.

profile(Prompt, Func, N) ->
    {TimeCost, _} = timer:tc(queen, Func, [N]),
    io:format("~p : ~p~n", [Prompt, TimeCost]).

profile() ->
    profile("re_queen RestPos -> Col", re_queen, 3),
    profile("re_queen_2 Col -> RestPos", re_queen_2, 3).

运行结果：

Queen profile result

从逻辑上来看，两种写法求出的都是N皇后问题的所有解，为什么第二种写法比第一种写法慢了好几个数量级呢？我们可以用三皇后加打印信息看一下具体遍历顺序，虽然三皇后问题是无解的，但用来看具体遍历顺序是可以的，要不打印信息太多了。

re_queen，RestPos -> Col，共遍历3 + 9 + 6 = 18次。

re_queen Row 1 Col 1 RestPos []
re_queen Row 1 Col 2 RestPos []
re_queen Row 1 Col 3 RestPos []
re_queen Row 2 Col 1 RestPos [{1,1}]
re_queen Row 2 Col 2 RestPos [{1,1}]
re_queen Row 2 Col 3 RestPos [{1,1}]
re_queen Row 2 Col 1 RestPos [{1,2}]
re_queen Row 2 Col 2 RestPos [{1,2}]
re_queen Row 2 Col 3 RestPos [{1,2}]
re_queen Row 2 Col 1 RestPos [{1,3}]
re_queen Row 2 Col 2 RestPos [{1,3}]
re_queen Row 2 Col 3 RestPos [{1,3}]
re_queen Row 3 Col 1 RestPos [{2,3},{1,1}]
re_queen Row 3 Col 2 RestPos [{2,3},{1,1}]
re_queen Row 3 Col 3 RestPos [{2,3},{1,1}]
re_queen Row 3 Col 1 RestPos [{2,1},{1,3}]
re_queen Row 3 Col 2 RestPos [{2,1},{1,3}]
re_queen Row 3 Col 3 RestPos [{2,1},{1,3}]
"re_queen RestPos -> Col" : 19000

re_queen_2，Col -> RestPos，共遍历20 + 20 + 20 = 60次。

re_queen_2 Row 1 Col 1 RestPos []
re_queen_2 Row 1 Col 2 RestPos []
re_queen_2 Row 1 Col 3 RestPos []
re_queen_2 Row 2 Col 1 RestPos [{1,1}]
re_queen_2 Row 2 Col 1 RestPos [{1,2}]
re_queen_2 Row 2 Col 1 RestPos [{1,3}]
re_queen_2 Row 1 Col 1 RestPos []
re_queen_2 Row 1 Col 2 RestPos []
re_queen_2 Row 1 Col 3 RestPos []
re_queen_2 Row 2 Col 2 RestPos [{1,1}]
re_queen_2 Row 2 Col 2 RestPos [{1,2}]
re_queen_2 Row 2 Col 2 RestPos [{1,3}]
re_queen_2 Row 1 Col 1 RestPos []
re_queen_2 Row 1 Col 2 RestPos []
re_queen_2 Row 1 Col 3 RestPos []
re_queen_2 Row 2 Col 3 RestPos [{1,1}]
re_queen_2 Row 2 Col 3 RestPos [{1,2}]
re_queen_2 Row 2 Col 3 RestPos [{1,3}]
re_queen_2 Row 3 Col 1 RestPos [{2,1},{1,3}]
re_queen_2 Row 3 Col 1 RestPos [{2,3},{1,1}]
re_queen_2 Row 1 Col 1 RestPos []
re_queen_2 Row 1 Col 2 RestPos []
re_queen_2 Row 1 Col 3 RestPos []
re_queen_2 Row 2 Col 1 RestPos [{1,1}]
re_queen_2 Row 2 Col 1 RestPos [{1,2}]
re_queen_2 Row 2 Col 1 RestPos [{1,3}]
re_queen_2 Row 1 Col 1 RestPos []
re_queen_2 Row 1 Col 2 RestPos []
re_queen_2 Row 1 Col 3 RestPos []
re_queen_2 Row 2 Col 2 RestPos [{1,1}]
re_queen_2 Row 2 Col 2 RestPos [{1,2}]
re_queen_2 Row 2 Col 2 RestPos [{1,3}]
re_queen_2 Row 1 Col 1 RestPos []
re_queen_2 Row 1 Col 2 RestPos []
re_queen_2 Row 1 Col 3 RestPos []
re_queen_2 Row 2 Col 3 RestPos [{1,1}]
re_queen_2 Row 2 Col 3 RestPos [{1,2}]
re_queen_2 Row 2 Col 3 RestPos [{1,3}]
re_queen_2 Row 3 Col 2 RestPos [{2,1},{1,3}]
re_queen_2 Row 3 Col 2 RestPos [{2,3},{1,1}]
re_queen_2 Row 1 Col 1 RestPos []
re_queen_2 Row 1 Col 2 RestPos []
re_queen_2 Row 1 Col 3 RestPos []
re_queen_2 Row 2 Col 1 RestPos [{1,1}]
re_queen_2 Row 2 Col 1 RestPos [{1,2}]
re_queen_2 Row 2 Col 1 RestPos [{1,3}]
re_queen_2 Row 1 Col 1 RestPos []
re_queen_2 Row 1 Col 2 RestPos []
re_queen_2 Row 1 Col 3 RestPos []
re_queen_2 Row 2 Col 2 RestPos [{1,1}]
re_queen_2 Row 2 Col 2 RestPos [{1,2}]
re_queen_2 Row 2 Col 2 RestPos [{1,3}]
re_queen_2 Row 1 Col 1 RestPos []
re_queen_2 Row 1 Col 2 RestPos []
re_queen_2 Row 1 Col 3 RestPos []
re_queen_2 Row 2 Col 3 RestPos [{1,1}]
re_queen_2 Row 2 Col 3 RestPos [{1,2}]
re_queen_2 Row 2 Col 3 RestPos [{1,3}]
re_queen_2 Row 3 Col 3 RestPos [{2,1},{1,3}]
re_queen_2 Row 3 Col 3 RestPos [{2,3},{1,1}]
"re_queen_2 Col -> RestPos" : 58000

在第二种写法中，针对每一列都要做一次fill_Rows(Size, Row-1)，这个计算量就非常大了。如果把fill_Rows(Size, Row-1)放在外面，每个Row只要做一次fill_Rows(Size, Row-1)。

⚠️ **GitHub.com Fallback** ⚠️