爲什麼Elixir在Ruby中最慢並且在解決Project Euler＃5方面走得很慢？

Question

更新：藥劑不慢，我的算法是。我的算法甚至不是蘋果來比較蘋果。有關Ruby和Go等效算法，請參閱下面的羅馬答案。還要感謝José，只需在MIX_ENV = prod的前面加上我的慢速算法即可。我已經更新了問題中的統計數據。

原始問題： 我正在研究多種語言的歐拉問題，只是爲了瞭解語言的多產和多快。在problem #5中，我們被要求找到能被1到20中的所有數字均勻劃分的最小正數。

我以多種語言實現瞭解決方案。這裏是統計：

1. 轉到1.4.2：0.58s
2. 紅寶石2.2 MRI：6.7s
3. 藥劑1.0.5（我的第一個算法）：57S
4. 藥劑1.0.5（我與MIX_ENV =督促前綴第一算法）：7.4S
5. 藥劑1.0.5（羅馬的Go相當於算法）：0.7秒
6. 藥劑1.0.5（羅馬的Ruby等效算法）：1.8秒

藥劑爲什麼如此緩慢？我嘗試在所有語言中使用相同的優化。警告：我是FP和Elixir的新手。

我能做些什麼來改善藥劑的性能嗎？如果您使用任何分析工具來找出更好的解決方案，可否請您將它們包含在回覆中？

在圍棋：

func problem005() int { 
    i := 20 
outer: 
    for { 
    for j := 20; j > 0; j-- { 
     if i%j != 0 { 
     i = i + 20 
     continue outer 
     } 
    } 
    return i 
    } 
    panic("Should have found a solution by now") 
} 

在Ruby：

def self.problem005 
    divisors = (1..20).to_a.reverse 

    number = 20 # we iterate over multiples of 20 

    until divisors.all? { |divisor| number % divisor == 0 } do 
    number += 20 
    end 

    return number 
end 

在藥劑：

def problem005 do 
    divisible_all? = fn num -> 
    Enum.all?((20..2), &(rem(num, &1) == 0)) 
    end 

    Stream.iterate(20, &(&1 + 20)) 
    |> Stream.filter(divisible_all?) 
    |> Enum.fetch! 0 
end 

Answer 1

我的第一個回答是關於實現您在Ruby中實現的相同算法。 現在，這裏是你的算法藥劑版本中去：

defmodule Euler do 
    @max_divider 20 
    def problem005 do 
    problem005(20, @max_divider) 
    end 

    defp problem005(number, divider) when divider > 1 do 
    if rem(number, divider) != 0 do 
     problem005(number+20, @max_divider) 
    else 
     problem005(number, divider-1) 
    end 
    end 
    defp problem005(number, _), do: number 
end 

這需要我的筆記本電腦約0.73s。這些算法是不同的，所以我相信Ruby在這裏也可以發揮更好的作用。

我想，這裏的一般規則是：如果你在Elixir中的代碼具有80％的Go碼或更好的性能，那沒關係。在其他情況下，您的Elixir代碼中很可能有算法錯誤。

更新關於Ruby：

作爲獎金，在這裏是用Ruby去等價算法：

def problem_005 
    divisor = max_divisor = 20 
    number = 20 # we iterate over multiples of 20 

    while divisor > 1 do 
    if number % divisor == 0 
     divisor -= 1 
    else 
     number += 20 
     divisor = max_divisor 
    end 
    end 

    number 
end 

它執行速度更快的4.5倍，所以我想這可能表明〜1.5，在你電腦。

Answer 2

試試這個版本：

defmodule Euler do 
    def problem005 do 
    problem005(20) 
    end 

    @divisors (20..2) |> Enum.to_list 
    defp problem005(number) do 
    if Enum.all?(@divisors, &(rem(number, &1) == 0)) do 
     number 
    else 
     problem005(number+20) 
    end 
    end 
end 

我的筆記本電腦需要約1.4秒。 解決方案的主要問題是在每次迭代時將範圍轉換爲列表。這是一個巨大的開銷。另外，這裏不需要創建「無限」流。你在其他語言中沒有這樣做。

Answer 3

你的代碼可能沒問題，但數學使我的牙齒受傷。有一個簡單的遞歸解決方案，可以很好地匹配靈丹妙藥的做法。 它還顯示瞭如何在elixir中進行遞歸，而不用擔心遞歸在其他語言中導致的性能問題 。

defmodule Euler_5 do 
@moduledoc """ 
Solve the smallest number divisible by 1..X using Greatest Common Divisor. 
""" 

    def smallest(1), do: 1 
    def smallest(2), do: 2 

    def smallest(n) when n > 2 do 
    next = smallest(n-1) 
    case rem(next, n) do 
     0 -> next 
     _ -> next * div(n,gcd(next,n)) 
    end 
    end 

    def gcd(1,_n), do: 1 

    def gcd(2,n) do 
    case rem(n,2) do 
     0 -> 2 
     _ -> 1 
    end 
    end 

    def gcd(m, n) do 
    mod = rem(m,n) 
    case mod do 
     0 -> n 
     _ -> gcd(n,mod) 
    end 
    end 

end 

對於它的價值，這需要我的電腦上8微秒

iex> :timer.tc(Euler_5, :smallest, [20]) 
{8, 232792560} 

不是一個真正的公平的比較成其他語言，因爲它不包括的時間來加載了VM，做I/O。

Answer 4

弗雷德的解決方案是偉大的。這更無用，（32微秒），但更清楚。也許隨着化學反應的進行，它可能會快幾個數量級。

defmodule Euler5 do 
    def smallest(n) when n > 0 do 
    Enum.reduce(1..n, &(lcm(&1, &2))) 
    end 
    def smallest(n), do: n 

    def lcm(x, y), do: div((x * y), gcd(x, y)) 

    def gcd(x, 0), do: x 
    def gcd(x, y), do: gcd(y, rem(x, y)) 
end 

Answer 5

我喜歡它的簡單此解決方案：

#!/usr/bin/env elixir 
defmodule Problem005 do 
    defp gcd(x, 0), do: x 
    defp gcd(x, y), do: gcd(y, rem(x, y)) 

    defp lcm(x, y) do 
    x * y/gcd(x, y) 
    end 

    def solve do 
    1..20 
    |> Enum.reduce(fn(x, acc) -> round(lcm(x, acc)) end) 
    end 
end 

IO.puts Problem005.solve 

這是非常快爲好。

./problem005.exs 0.34s user 0.17s system 101% cpu 0.504 total 

至於紅寶石，這可以在一個線路來解決：

#!/usr/bin/env ruby 
puts (1..20).reduce { |acc, x| acc.lcm(x) } 

（LCM - >http://ruby-doc.org/core-2.0.0/Integer.html#method-i-lcm）