跳至內容

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 模組,實作陣列的其他性質。