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

计算机科学 > 编程 > Erlang程式设计与问题解决

阅读过 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 模组，实作阵列的其他性质。