Erlang圖案匹配性能

Erlang新款。我即將開始編寫一些代碼。我想到的解決方案可以通過兩種方式之一。我可以做一堆數學計算，或者我可以將它編碼爲模式匹配。當我說「模式匹配」時，我並不是指正則表達式或類似的東西 - 我指的是從句頭中的模式匹配。Erlang圖案匹配性能

表現通常不是一個問題，但在這個應用程序是。我不是問你哪種方法會更快 - 我相信你會說你不知道（取決於很多因素）。我所要求的是在子句頭中的Erlang模式匹配的一般性能。換句話說，在Prolog中，引擎被優化來完成這樣的事情，所有其他的事情都是平等的，所以「鼓勵」你設計一個解決方案，利用模式匹配和子句頭的統一。

Erlang是否也是如此，即Erlang是否爲子句頭中的模式匹配進行了優化，類似於Prolog？我並沒有在這裏提出這個問題，而是試着在Erlang中描述這個問題，並且編寫了一個玩具程序，對幾百萬次的子句頭進行模式匹配，並對幾百萬次的列表進行總結。但是如果這個系統能夠「幾百萬次」的話，系統就會崩潰。但設定爲不到幾百萬美元，結果會回來太快，讓我無法瞭解任何有關性能的信息。

感謝您的任何見解。

來源

2011-01-22 Ultranewb

張貼科茨。改寫爲一個關於爲什麼會崩潰的問題。 – EvilTeach 2011-01-22 12:57:56

該代碼是2個非常簡單的程序。第一個程序是序列子句（0） - > 0的10個子句元首;條款（1） - > 0; （最多10個）爲了測試我使用重複創建了200萬個0的列表，並且使用map來映射子句到它上面。第二個程序是簡單地使用重複創建200萬列表中的7個整數，然後使用映射將sum映射到它。我再次試圖測試用作編程技術的模式匹配的相對性能。我的問題是，是否鼓勵Erlang程序員在Prolog程序員中使用模式匹配（如果可行）。 – Ultranewb 2011-01-22 16:50:39

一般來說，函數式語言中的模式匹配比Prolog中的模式匹配快或快。與Prolog相比，我希望Erlang能以2倍的速度執行，速度更快或更慢。由於功能程序幾乎不是模式匹配，而是您優化的很多方面之一。

內部通常有一個模式匹配編譯器它將高級模式匹配變成一個更簡單的系列檢查，目標是最小化檢查次數。

確定，所述第一抓把柄：「任何在殼引入被解釋」。所以我們編譯模塊代替：

-module(z). 

-compile(export_all). 

%% This pattern is highly uninteresting because it only matches 
%% on a single value. Any decent system can do this quickly. 
cl(0) -> 0; 
cl(1) -> 0; 
cl(2) -> 0; 
cl(3) -> 0; 
cl(4) -> 0; 
cl(5) -> 0; 
cl(6) -> 0; 
cl(7) -> 0; 
cl(8) -> 0; 
cl(9) -> 0. 

mcl(L) -> 
    [cl(E) || E <- L].

這給了我們一個跑步者的例子。

cl2(a, 0) -> a0; 
cl2(a, 1) -> a1; 
cl2(a, 2) -> a2; 
cl2(b, 0) -> b0; 
cl2(b, 1) -> b1; 
cl2(b, 2) -> b2; 
cl2(c, 0) -> c0; 
cl2(c, 1) -> c0; 
cl2(c, 2) -> c0. 

mcl2(L) -> 
    [cl2(A, V) || {A, V} <- L].

跑步者的一個更有趣的例子。在這裏，我們可以在模式中利用跳過。如果(a, 0)在a上不匹配，我們知道我們可以直接跳到(b, 0)的情況，因爲否定匹配信息可以作爲系統中的信息傳播。模式匹配編譯器通常會進行此優化。

test1() -> 
    L1 = [X rem 10 || X <- lists:seq(1, 2000000)], 
    %% A Core 2 Duo 2.4Ghz P8600 eats this in 132984 microseconds without HiPE 
    %% c(z). 
    %% With HiPE it is 91195 or in 0.6857591890753775 of the time the non-HiPE variant use 
    %% c(z, [native, {hipe, [o3]}]). 
    timer:tc(z, mcl, [L1]).

您必須自己運行此示例，並評估您是否認爲它足夠快才能滿足您的用例。請注意，映射代碼也花了一些時間，並且需要花費很多時間以將數據從主存儲器通過CPU高速緩存拉到CPU。

test2() -> 
    random:seed(erlang:now()), 
    L2 = [{case random:uniform(3) of 
        1 -> a; 
        2 -> b; 
        3 -> c 
        end, V rem 3} || V <- lists:seq(1, 2000000)], 
    %% With HiPE this is 220937 
    %% Without HiPE this is 296980 
    timer:tc(z, mcl2, [L2]).

當然，這個例子比較慢，因爲我們需要在命中之前匹配更多的數據。但是這是一個更有趣的例子，因爲它給出了匹配編譯器實際速度的一些指示。

並行版本進行了嘗試，但都是因爲創造200萬個工作進程的開銷，在這種情況下慢10倍左右遠占主導地位的實際處理:)

來源

2011-01-22 20:05:59

它基本上是爲@（不是很）CRAP答案:-)已經說過，他的例子顯示。

序言沒有真正做模式匹配，這是單向的，它確實是統一這就像是一個雙向模式與邏輯變量匹配。優化模式匹配要容易得多，Erlang和Haskell等嚴重的函數式語言將相當多的工作放到優化模式匹配編譯器中。深度圖案尤其引人注目。

所以，是的，Erlang會比Prolog更快地進行模式匹配。

來源

2011-01-23 17:26:12 rvirding

Erlang圖案匹配性能

回答

相關問題