Erlang 執行速度好慢好慢嗎?

最近 erlang-questions@erlang.org 電子郵件論壇有一則討論,有人寫一段程式碼,發現用 Erlang 寫的版本比用 C# 寫的慢了十幾倍。

pythag(N) ->
  [ {A,B,C} ||
      A <- lists:seq(1,N),
      B <- lists:seq(1,N),
      C <- lists:seq(1,N),
      A+B+C =< N,
      A*A+B*B =:= C*C].

然後在回覆意見中出現了好些解決方案,有些用 Tail Recursion 加快局部計算速度,有些做問題領域分析、把判斷式改寫成另一種型式。最後由 Rechard O’Keefe ,一位和善的學院教師,回答了一個簡單的答案:

pythag(N) ->
  [ {A,B,C} ||
      A <- lists:seq(1,N),
      B <- lists:seq(1,N-A),
      C <- lists:seq(1,N-A-B),
      A+B+C =< N,
      A*A+B*B =:= C*C].

速度起碼增加一個級數,也就是減了約十倍的計算時間。

我們來看看,以下程式有一個 time_test/2 、 pythag/1 和 pythag1/1 。

-module(test).
-compile(export_all).

time_test(F, Args) ->
    io:format("Testing applying ~w to ~w...~n", [F, Args]),
    S = now(),
    R = erlang:apply(F, Args),
    E = now(),
    io:format("Result ~w with length ~w~n", [R,length(R)]),
    timer:now_diff(E, S).

pythag(N) ->
  [ {A,B,C} ||
      A <- lists:seq(1,N),
      B <- lists:seq(1,N),
      C <- lists:seq(1,N),
      A+B+C =< N,
      A*A+B*B =:= C*C].

pythag1(N) ->
  [ {A,B,C} ||
      A <- lists:seq(1,N),
      B <- lists:seq(1,N-A),
      C <- lists:seq(1,N-A-B),
      A+B+C =< N,
      A*A+B*B =:= C*C].

pythag/1 是浪費時間的版本, pythag1/1 是精簡效率的版本。在我的四核心電腦上跑的狀況如下:

> test:time_test(fun test:pythag/1, [300]).
Testing applying #Fun to [300]...
Result [{3,4,5},{4,3,5},{5,12,13},{6,8,10},{7,24,25},{8,6,10},{8,15,17},{9,12,15},{9,40,41},{10,24,26},{11,60,61},{12,5,13},{12,9,15},{12,16,20},{12,35,37},{13,84,85},{14,48,50},{15,8,17},{15,20,25},{15,36,39},{15,112,113},{16,12,20},{16,30,34},{16,63,65},{18,24,30},{18,80,82},{20,15,25},{20,21,29},{20,48,52},{20,99,101},{21,20,29},{21,28,35},{21,72,75},{22,120,122},{24,7,25},{24,10,26},{24,18,30},{24,32,40},{24,45,51},{24,70,74},{25,60,65},{27,36,45},{27,120,123},{28,21,35},{28,45,53},{28,96,100},{30,16,34},{30,40,50},{30,72,78},{32,24,40},{32,60,68},{32,126,130},{33,44,55},{33,56,65},{35,12,37},{35,84,91},{35,120,125},{36,15,39},{36,27,45},{36,48,60},{36,77,85},{36,105,111},{39,52,65},{39,80,89},{40,9,41},{40,30,50},{40,42,58},{40,75,85},{40,96,104},{42,40,58},{42,56,70},{44,33,55},{44,117,125},{45,24,51},{45,28,53},{45,60,75},{45,108,117},{48,14,50},{48,20,52},{48,36,60},{48,55,73},{48,64,80},{48,90,102},{50,120,130},{51,68,85},{52,39,65},{54,72,90},{55,48,73},{56,33,65},{56,42,70},{56,90,106},{56,105,119},{57,76,95},{60,11,61},{60,25,65},{60,32,68},{60,45,75},{60,63,87},{60,80,100},{60,91,109},{63,16,65},{63,60,87},{63,84,105},{64,48,80},{65,72,97},{66,88,110},{68,51,85},{69,92,115},{70,24,74},{72,21,75},{72,30,78},{72,54,90},{72,65,97},{72,96,120},{75,40,85},{75,100,125},{76,57,95},{77,36,85},{80,18,82},{80,39,89},{80,60,100},{80,84,116},{84,13,85},{84,35,91},{84,63,105},{84,80,116},{88,66,110},{90,48,102},{90,56,106},{91,60,109},{92,69,115},{96,28,100},{96,40,104},{96,72,120},{99,20,101},{100,75,125},{105,36,111},{105,56,119},{108,45,117},{112,15,113},{117,44,125},{120,22,122},{120,27,123},{120,35,125},{120,50,130},{126,32,130}] with length 146
5312000
> test:time_test(fun test:pythag1/1, [300]).
Testing applying #Fun to [300]...
Result [{3,4,5},{4,3,5},{5,12,13},{6,8,10},{7,24,25},{8,6,10},{8,15,17},{9,12,15},{9,40,41},{10,24,26},{11,60,61},{12,5,13},{12,9,15},{12,16,20},{12,35,37},{13,84,85},{14,48,50},{15,8,17},{15,20,25},{15,36,39},{15,112,113},{16,12,20},{16,30,34},{16,63,65},{18,24,30},{18,80,82},{20,15,25},{20,21,29},{20,48,52},{20,99,101},{21,20,29},{21,28,35},{21,72,75},{22,120,122},{24,7,25},{24,10,26},{24,18,30},{24,32,40},{24,45,51},{24,70,74},{25,60,65},{27,36,45},{27,120,123},{28,21,35},{28,45,53},{28,96,100},{30,16,34},{30,40,50},{30,72,78},{32,24,40},{32,60,68},{32,126,130},{33,44,55},{33,56,65},{35,12,37},{35,84,91},{35,120,125},{36,15,39},{36,27,45},{36,48,60},{36,77,85},{36,105,111},{39,52,65},{39,80,89},{40,9,41},{40,30,50},{40,42,58},{40,75,85},{40,96,104},{42,40,58},{42,56,70},{44,33,55},{44,117,125},{45,24,51},{45,28,53},{45,60,75},{45,108,117},{48,14,50},{48,20,52},{48,36,60},{48,55,73},{48,64,80},{48,90,102},{50,120,130},{51,68,85},{52,39,65},{54,72,90},{55,48,73},{56,33,65},{56,42,70},{56,90,106},{56,105,119},{57,76,95},{60,11,61},{60,25,65},{60,32,68},{60,45,75},{60,63,87},{60,80,100},{60,91,109},{63,16,65},{63,60,87},{63,84,105},{64,48,80},{65,72,97},{66,88,110},{68,51,85},{69,92,115},{70,24,74},{72,21,75},{72,30,78},{72,54,90},{72,65,97},{72,96,120},{75,40,85},{75,100,125},{76,57,95},{77,36,85},{80,18,82},{80,39,89},{80,60,100},{80,84,116},{84,13,85},{84,35,91},{84,63,105},{84,80,116},{88,66,110},{90,48,102},{90,56,106},{91,60,109},{92,69,115},{96,28,100},{96,40,104},{96,72,120},{99,20,101},{100,75,125},{105,36,111},{105,56,119},{108,45,117},{112,15,113},{117,44,125},{120,22,122},{120,27,123},{120,35,125},{120,50,130},{126,32,130}] with length 146
891000

運算結果相同,而速度,差的版本跑了 5 秒,快的版本跑了 0.9 秒。 O’Keefe 先生提供的解答真是簡潔、洞悉關鍵。

補充:後來 Erlang 的爸爸 Joe Armstrong 回應了 O’Keefe 的解答指出,可以把程式加強為:

pythag(N) ->
      Max = N div 2,
  [ {A,B,C} ||
      A <- lists:seq(1,N+1),
      B <- lists:seq(1,Max-A),
      C <- lists:seq(1,Max-A-B),
      A*A+B*B =:= C*C].

因為三角形的性質是任一邊都不會比三邊長的和的一半更長。這種解題風格跟 Joe 本人的思考模式有關係,他在 “Coders at Work" 一書中訪談紀錄提到他寫程式會比較走向特殊化的寫法,而不會老是寫一些一般化的程式 (意指在程式中留下一些未來的擴充空間的事情,譬如留一個沒有用到的變數) 。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Erlang, Fun。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s