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