小毛的胡思乱想

凡走过,必留痕迹.

Hello Erlang, Part 4

| Comments

练习重点

列表解析和高阶函数是erlang的基本用法之一,熟练掌握还是很有必要的。 作为一个阶段的学习总结,按照书上的一个练习题,尝试实现列表模块中的一些方法。

后续学习计划

再找时间总结一下位匹配用法,然后就开始客户端服务器编程模型, 网络和分布式方面的内容。

相关内容虽然都看过一下,但是没有敲过代码,感觉心里没底。还是那个硬道理:纸上得来终觉浅呀。

简单的测试用例

作为另外一个章节的内容,单元测试。我顺便实践一下erlang的单元测试框架eunit, 里边使用了宏来作为assert语句(使用eclipse插件可以有很好的提示), 总的来说,xunit的基本风格都差不多,注意import eunit的包,方法名采用_test结束。 执行的时候调用模块的test方法就可以了。我简单写了一些测试用例:

-module(myliststest).
-include_lib("eunit/include/eunit.hrl").
-import_all(mylists).

%% EUnit TestCase

%% all/2
all_empty_test() ->
  ?assert(mylists:all(fun(E) -> E > 10 end, [])).
all_test() ->
  ?assertNot(mylists:all(fun(E) -> E > 10 end, [11,12,10])).

%% any/2
any_empty_test() ->
  ?assertNot(mylists:any(fun(E) -> E > 10 end, [])).
any_test() ->
  ?assert(mylists:any(fun(E) -> E > 10 end, [11,12,10])).

%% append/1
append_1_test() ->
  ?assertEqual([1,2,3,a,b,4,5,6], mylists:append([[1, 2, 3], [a, b], [4, 5, 6]])).

%% append/2
append_2_test() ->
  ?assertEqual("abcdef", mylists:append("abc", "def")).

%% delete/2
delete_test() ->
  ?assertEqual([1,2,4], mylists:delete(3, [1,2,3,4])).

%% dropwhile/2
dropwhile_test() ->
  ?assertEqual([1,2], mylists:dropwhile(fun(E) -> E >= 3 end, [1,2,3,4])).

%% duplicate/2
duplicate_test() ->
  ?assertEqual([x, x], mylists:duplicate(2, x)).

%% filter/2
filter_test() ->
  ?assertEqual([3,4], mylists:filter(fun(E) -> E >= 3 end, [1,2,3,4])).

%% reverse/1
reverse_test() ->
  ?assertEqual([4,3,2,1], mylists:reverse([1,2,3,4])).

%% min/1
min_test() ->
  ?assertEqual(2, mylists:min([3,4,2,5])).

%% zip/2
zip_2_test() ->
  ?assertEqual([{1,3},{2,4}], mylists:zip([1,2], [3,4,5])).

%% zip/3
zip_3_test() ->
  ?assertEqual([{1,3,5},{2,4,7}], mylists:zip3([1,2], [3,4,5], [5,7])).

%% zipwith/3
zipwith_test() ->
  ?assertEqual([5,7,9], mylists:zipwith(fun(X, Y) -> X+Y end, [1,2,3], [4,5,6])).

%% zipwith/4
zipwith3_test() ->
  ?assertEqual([[a,x,1],[b,y,2],[c,z,3]], mylists:zipwith3(fun(X, Y, Z) -> [X,Y,Z] end, [a,b,c], [x,y,z], [1,2,3])).

示例代码

根据上面的测试用例,我写了实现代码,如下所示。注意的时候,我偷懒使用了export_all, 但是min/2好像默认有一个已经被引入了,所以需要去除这个模块。就export_all本身来说, 也不是推荐方式,还是应该严格区分public api和local api。

-module(mylists).
-compile(export_all).
-compile({no_auto_import,[min/2]}).

%% all/2
all(_P, []) -> 
  true;
all(P, [H|T]) ->
  case P(H) of
    true -> all(P, T);
    false -> false
  end.

%% any/2
any(_P, []) ->
  false;
any(P, [H|T]) ->
  case P(H) of
    true -> true;
    false -> any(P, T)
  end.

%% append/1
append(LL) ->
  [X || L <- LL, X <- L].

%% append/2
append(LA, LB) ->
  LA ++ LB.

%% delete/2
delete(E, L) ->
  [X || X <- L, E /= X].

%% dropwhile/2
dropwhile(P, L) ->
  [X || X <- L, not P(X)].

%% duplicate/2
duplicate(N, E) ->
  duplicate(N, E, []).
duplicate(0, _E, L) ->
  L;
duplicate(N, E, L) when N > 0 ->
  duplicate(N-1, E, [E|L]).

%% filter/2
filter(P, L) ->
  [X || X <- L, P(X)].

%% reverse/1
reverse(L) ->
  reverse(L, []).
reverse([], L) ->
  L;
reverse([H|T], L) ->
  reverse(T, [H|L]).

%% min/1
min([H|T]) ->
  min(T, H).
min([], M) ->
  M;
min([H|T], M) ->
  if
    H < M -> min(T, H);
    true -> min(T, M)
  end.

%% zip/2
zip(LA, LB) ->
  reverse(zip(LA, LB, [])).
zip([], _LB, L) ->
  L;
zip(_LA, [], L) ->
  L;
zip([HA|TA], [HB|TB], L) ->
  zip(TA, TB, [{HA,HB}|L]).

%% zip/3
zip3(LA, LB, LC) ->
  reverse(zip3(LA, LB, LC, [])).
zip3([], _LB, _LC, L) ->
  L;
zip3(_LA, [], _LC, L) ->
  L;
zip3(_LA, _LB, [], L) ->
  L;
zip3([HA|TA], [HB|TB], [HC|TC], L) ->
  zip3(TA, TB, TC, [{HA,HB,HC}|L]).

%% zipwith/3
zipwith(P, LA, LB) ->
  [P(X,Y) || {X,Y} <- zip(LA, LB)].

%% zipwith/4
zipwith3(P, LA, LB, LC) ->
  [P(X,Y,Z) || {X,Y,Z} <- zip3(LA, LB, LC)].

Hello Erlang, Part 3

| Comments

练习重点

并发编程是erlang的重要话题,所以这次先来热身,熟悉一下erlang中进程的基本用法。

练习1:进程环

编写一个程序,它生成N个进程并相连形成一个环,一旦启动,这些进程会环绕发送M个消息。 然后当收到消息的时候正常终止。调用ring:start(M, N, Message)来启动环。

思路及编程示例

首先,为了形成环状,就是让最后一个进程能够给第一个进程发送消息, 调用spawn生成进程的时候,需要把第一个pid一直传递到最后一个。所以需要有个start的方法, 但需要多加个第一个进程id的参数,关注参数N=1作为临界点。

还有,需要等待消息,然后给下一个进程发送消息,之后继续等待消息,直到M=0。 所以需要一个等待消息的方法,同时需要关注参数M=0作为临界点。

最后,整个环,所有的进程一开始都在等待,需要有个消息来启动环, 可以在第一个进程启动下一个进程之前,往自身邮箱里边发送一条消息, 这样第一个进程进入等待消息的时候,就能接收到消息,从而启动环。

我的代码示例如下:

-module(ring).

%% Exported Functions
-export([start/3]).
-export([start/4]).

%% API Functions
start(M, N, Message) ->
  self() ! {self(), start},
  start(M, N, Message, self()).

start(M, 1, Message, Rid) ->
  waitmessage(M, 1, Message, Rid);

start(M, N, Message, Rid) ->
  Pid = spawn(ring, start, [M, N-1, Message, Rid]),
  waitmessage(M, N, Message, Pid).

waitmessage(0, _N, _Message, _Pid) ->
  receive
    {Pd, Msg} ->
      io:format("pid ~p receive message ~p from ~p~n", [self(), Msg, Pd])
      ok
  end;

waitmessage(M, N, Message, Pid) ->
  receive
    {Pd, Msg} ->
      io:format("pid ~p receive message ~p from ~p~n", [self(), Msg, Pd]),
      Pid ! {self(), Message},
      waitmessage(M-1, N, Message, Pid)
  end.

通过简单的测试,如果去掉io:format的话,效率会提高不少。IO操作消耗的时间还是不可小视呀。 另外,测试大数量进程的时候,内存也用得比较厉害,毕竟这个练习更像是一个同步操作。

Hello Erlang, Part 2

| Comments

练习重点

  1. 依然是熟悉erlang匹配模式的编程方式,对于用习惯了判断,循环操作的人来说,这个变化很大
  2. 熟悉erlang列表操作
  3. 为后面学习高阶函数fun,还有更多高级数据类型打好基础

练习1:压缩有序列表

类似搜索里边的倒排索引,需要对词对应的文档列表进行存放。 在这里,我们将一个有序列表转换成另外一种形式,如

%% 原始形式
[1,1,2,4,5,6,6,98,100,101,102,102].
%% 最终形式
[{1,2},{4,6},{98,98},{100,102}].

示例代码

multi(L) -> lists:reverse(multi_local(L, [])).
multi_local([], R) -> R;
multi_local([H|L], R) ->
    {LL, E} = multi_r(L, H),
    multi_local(LL, [{H, E}|R]).

%% 获取L里边里边和H同属一组的最后一个数,同时返回剩余的列表
%% 如果L以H开头,表示出现重复数
%% 如果L以H+1开头,表示出现序列数
multi_r(L, H) ->
    N = H + 1,
    case L of
        [H|LL] -> multi_r(LL, H);
        [N|LL] -> multi_r(LL, N);
        [] -> {[], H};
        _ -> {L, H}
    end.

效率问题

这里和上次不一样的是,这里没有使用lists:append方法,而是在最后使用了reverse.

[1] ++ [2, 3].
lists:append([1], [2, 3]).
lists:reverse([3|[2, 1]]).

上面三种方式得到的结果是一样的。前面两种,每增加一个元素,都会遍历左边的列表,所以在递归里边处理的话, 效率并不好。把元素添加到表头,在递归完成后进行反转,效果就会好些。

练习2:马踏棋盘

作为一个阶段的学习总结,对马踏棋盘的算法思考用erlang实现。

代码比较悲剧,我选择了array,用了一些fun函数,从这么个例子就可以看出,自己还没掌握好erlang惯用法。 感觉数据结构没有选好,并且用了命令语言的一些编程思路,有些东西或许可以用列表解析来弄, 等再掌握多一些东西,再回头来体会一把!

-module(horse).

%% Exported Functions
-export([walkboard/0]).

%% API Functions
walkboard() -> 
  %% lists:foreach(fun(I) -> lists:foreach(fun(J) -> walkboard({I, J}) end, lists:seq(0,7)) end, lists:seq(0,7)).
  walkboard({2,3}).

walkboard({I,J}) ->
  {ARR, PATH, POSS} = init(),
  catch walk(0, setvalue({I, J}, 1, ARR), array:set(0, {I,J}, PATH), POSS).

walk(63, _, PATH, _) -> throw(PATH);
walk(MARK, ARR, PATH, POSS) ->
  {IP, JP} = array:get(MARK, PATH),
  WC = fun({I,J,_}) -> 
         walk(MARK+1, setvalue({I+IP,J+JP}, 1, ARR), array:set(MARK+1, {I+IP,J+JP}, PATH), POSS)
       end,
  lists:foreach(WC, filter(MARK, PATH, POSS, ARR)).

%%
%% Local Functions
%%
init() ->
  ARR = array:new(8, {default,array:new(8, {default,0})}),
  PATH = array:new(64),
  POSS = [{-2, 1}, {2, 1}, {1, 2}, {-1, 2}, {2, -1}, {-2, -1}, {-1, -2}, {1, -2}],
  {ARR, PATH, POSS}.

filter(MARK, PATH, POSS, ARR) ->
  {I, J} = array:get(MARK, PATH),
  Fun1 = fun({IP, JP}) ->
           {IXP, JXP} = {I+IP, J+JP},
           case valid({IXP, JXP}, ARR) of
             false -> {IP, JP, -1};
             true -> 
             %% 计算空点数
             CAL = fun({IP2, JP2}, Sum) -> 
                     case valid({IXP+IP2, JXP+JP2}, ARR) of
                       true -> 1 + Sum;
                       false -> Sum
                     end
                   end,
                   {IP, JP, lists:foldl(CAL, 0, POSS)}
           end
         end,
  %% 最后进行排序
  T = lists:map(Fun1, POSS),
  S = lists:filter(fun({_, _, Z}) -> Z == 0 end, T),
  LEN = length(S),
  if
    LEN > 1 -> [];
    LEN > 0 -> S;
    true -> SS = lists:filter(fun({_, _, Z}) -> Z >= 0 end, T),
        lists:sort(fun({_, _, Z1}, {_, _, Z2}) -> Z1 < Z2 end, SS)
  end.
  

valid({I,J}, ARR) ->
  I >= 0 andalso I<8 andalso J>=0 andalso J<8 andalso getvalue({I,J}, ARR) == 0.

getvalue({I,J}, ARR) ->
  array:get(J, array:get(I, ARR)).

setvalue({I,J}, VAL, ARR) ->
  array:set(I, array:set(J, VAL, array:get(I, ARR)), ARR).

Hello Erlang, Part 1

| Comments

练习重点

  1. erlang是单赋值的,就好像都经过java里边的final修饰过
  2. erlang没有内置的循环结构,这个和大多数语言是不一样的
  3. erlang是函数式语言,需要理解模式匹配编程方式
  4. erlang经常会遇到递归, 并且支持尾递归函数调用

练习1:数据库demo

作为学习erlang里边的模式匹配,熟悉语法。 编写一个数据库模块db.erl,它能够存储、检索、删除元素。我们需要实现的接口有:

db:new()                   %% Db.
db:destroy(Db)             %% ok.
db:write(Key, Element, Db) %% NewDb.
db:delete(Key, Db)         %% NewDb.
db:read(Key, Db)           %% {ok, Element} | {error, instance}.
db:match(Element, Db)      %% [Key1, ..., KeyN].

实现代码

-module(db).

%% Exported Functions
-export([new/0, write/3, read/2, match/2, delete/2, destroy/1]).

%% API Functions
new() -> [].
destroy(_) -> ok.
write(Key, Element, DB) -> [{Key,Element}|DB].
delete(Key, DB) -> delete_local(Key, DB, []).
read(Key, DB) ->
    case DB of
        [{Key, Element}|_] -> {oKey, Element};
        [_|ODB] -> read(Key, ODB);
        _ -> {error, instance}
    end.
match(Element, DB) -> match_local(Element, DB, []).

%% Local Functions
match_local(Element, DB, LIST) ->
    case DB of
        [{Key, Element}|ODB] -> match_local(Element, ODB, [Key|LIST]);
        [_|ODB] -> match_local(Element, ODB, LIST);
        _ -> LIST
    end.

delete_local(Key, DB, NDB) ->
    case DB of
        [{Key, _}|ODB] -> delete_local(Key, ODB, NDB);
        [H|ODB] -> delete_local(Key, ODB, [H|NDB]);
        _ -> NDB
    end.

当然,case语句同样可以用如下代码替代:其中第三行的Key因为没有使用就换成_, 不然会提示警告variable ‘Key’ is unused。

delete_local(Key, [{key, _}|ODB], NDB) -> delete_local(Key, ODB, NDB);
delete_local(Key, [H|ODB], NDB) -> delete_local(Key, ODB, [H|NDB]);
delete_local(_, _, NDB) -> NDB;

练习2:排序算法

下面练习一下快速排序和归并排序,再熟悉一下模式匹配和递归的写法。

-module(sort).
-export([quicksort/1, mergesort/1]).

%% 快速排序
quicksort([H|Tail]) ->
    lists:append([quicksort(lists:filter(fun(X) -> X < H end, Tail)), 
                  [H], 
                  quicksort(lists:filter(fun(X) -> X >= H end, Tail))]);
quicksort(L) -> L.

%% 归并排序
mergesort(A) ->
    case length(A) of
        0 -> [];
        1 -> A;
        LEN -> M = length(A) div 2,
               merge(mergesort(lists:sublist(A, 1, M)), 
                     mergesort(lists:sublist(A, M + 1, LEN - M)), [])
    end.
merge(A, [], L) -> lists:append([L, A]);
merge([], B, L) -> lists:append([L, B]);
merge([HA|TA], [HB|TB], L) -> 
    if
        HA > HB -> merge([HA|TA], TB, lists:append([L, [HB]]));
        true -> merge(TA, [HB|TB], lists:append([L, [HA]]))
    end.

马踏棋盘的算法思考

| Comments

马踏棋盘

将马随机放在国际象棋的8×8棋盘的某个方格中,马按走棋规则进行移动。 要求每个方格只进入一次,走遍棋盘上全部64个方格。

又是回溯?

这个做法和前面几个问题是差不多的(数独(sudoku)游戏),所以这里就不做太多解释了。 总体来说,就是可选的解空间是8个方向。回溯的代码就不多提了,需要说的是,这里简单的回溯 效率不好,需要跑很久才出结果。我们有什么方式可以优化一下!

贪心是否有效?

首先,我们可以对可供选择的方向进行过滤,对于它相连的8个方向所在的点, 在当前的局面下,假如存在两个点只有一条路可以到达,那么可以直接回溯, 因为无论走哪个方向都不能走完整个棋盘。假如存在一个点,它只有一条路可以到达, 那么下一步必须走这个方向。

但是,即使我们过滤了一些路径,效率还是没有非常大的提升。我们需要考虑一种贪心的思路: 在可选的方向中,优先选择出口最少的目标点。因为优先选择出口少的点, 就可以让出口少的点尽量少,使得最后剩下的点有比较多的入口,这样最终达到目的的概率就会大些。

虽然这个思路,我觉得不好直接证明,不过我修改了一些代码实现,的确效率得到非常大的提升。 就我那个机器,ruby代码,不到1s,64个点的情况就全部处理完了。

代码示例

def init
  @arr = Array.new(8)
  (0..7).each do |i| @arr[i] = Array.new(8, 0) end
  @path = Array.new(64) 
  @ok = false
  @poss = [[-2, 1], [2, 1], [1, 2], [-1, 2], [2, -1], [-2, -1], [-1, -2], [1, -2]]
end
# 判断[x,y]是否在棋盘内并未走过
def valid?(x,y)
  x>=0 && x<8 && y>=0 && y<8 && @arr[x][y]==0
end

# 判断当前点有哪些方向可以走
def filter(mark)
  posz, mustpos = {}, nil
  a, b = @path[mark]
  @poss.each do |pos|
    axp, bxp = a+pos[0], b+pos[1]
    if valid?(axp, bxp)
      sz = 0
      @poss.each do |ps|
        ap, bp = axp+ps[0], bxp+ps[1]
        sz+=1 if valid?(ap, bp) # 存在空点
      end
      if sz>0
        posz[pos] = sz
      else
        mustpos.nil? ? (mustpos = pos) : (return [])
      end
    end
  end
  # 对目标点的方向多寡进行排序
  mustpos.nil? ? posz.keys.sort {|a,b| posz[a]<=>posz[b]} : [mustpos]
end

def walk(mark)
  if mark==63
    @ok = true
    return
  end
  a, b = @path[mark]
  filter(mark).each do |pos|
    rp = [a+pos[0], b+pos[1]]
    @path[mark+1] = rp
    @arr[rp[0]][rp[1]] = 1
    walk(mark+1)
    @ok ? return : (@arr[rp[0]][rp[1]] = 0)
  end
end

(0..7).each do |i|
  (0..7).each do |j|
    init
    @path[0] = [i,j]
    @arr[i][j] = 1
    walk(0)
    if @ok
      @path.each_with_index do |ps, idx|
        @arr[ps[0]][ps[1]] = idx
      end
      @arr.each do |ar| p ar end
      puts
    else
      "no solution"
    end
  end
end