Erlang程式设计与问题解决/搜寻

来自Wikibooks
跳到导航 跳到搜索


阅读过 Erlang 语言的语法之后,可以开始着手写一些程式,解决一些问题。本章我们要看看搜寻的问题如何处理。

线性搜寻[编辑]

Erlang 的基本资料结构,列表 ( list ) ,是线性结构。使用列表储存许多资料,最简便的方法是对此列表做线性搜寻。

首先,考虑要在一个列表中搜寻某个样式,要先思考搜寻程式的函数规格:输入有哪些,输出有哪些。

lin_search ( Pattern , List ) => Element | nil

如果找得到,就给出找到的项目。如果找不到,是用一个 nil 表示。

接着写成程式,程式如下:

lin_search(_, []) -> nil;
lin_search(Pattern, [Element|Rest]) ->
    case match(Pattern, Element) of
        no -> lin_search(Pattern, Rest);
        yes -> Element
    end.

将 Pattern 和 Element 匹配的这个子问题交给 match/2 函数,使 lin_search/2 这个函数很小,很容易顾到这个问题是否被正确处理。

而 match/2 规格是:

match ( Pattern , Element ) => yes | no

假设 match/2 设计成 Pattern 与 Element 相等,就做成一个基本线性搜寻。

match(Pattern, Element) when Pattern == Element -> yes;
match(_, _) -> no.

当然也可以随着问题的不同,将 match/2 写成别的比较方式。在此局部保留了算法的延伸可能性。

二元搜寻[编辑]

告知 Erlang 的 lists 模组有个内建函数 nth/2 可以取列表的第 N 个元素之后,你应该知道怎么做二元搜寻。

% match(Pattern, Element) => Element | great_than | less_than
match(Pattern, Element) ->
    if
        Pattern == Element -> Element;
        Pattern > Element -> great_than;
        Pattern < Element -> less_than
    end.

% bin_search(Pattern, List, StartPos, EndPos) => {N, Element} | nil
bin_search(Pattern, List, S, E) ->
    if
        E < S -> nil;
        true ->
            N = (S + E) div 2,
            Element = lists:nth(N, List),
            case match(Pattern, Element) of
                great_than -> bin_search(Pattern, List, N+1, E);
                less_than -> bin_search(Pattern, List, S, E-1);
                Element -> {N, Element}
            end
    end

虽然是二元搜寻程式,以上程式效能消耗的考量是在 lists:nth/2 的实作。列表不是阵列,基本上不像阵列有随机存取的效能。不过, Erlang 有个随机存取的模组称为 ets ( Erlang Term Service ) 可以做快速的资料管理。 Erlang 也有 array 模组,实作阵列的其他性质。