更新: Elixir并不慢,是我的算法慢。我的算法甚至无法进行同类比较。关于Ruby和Go等效算法,请参阅Roman的回答。同样要感谢jos
我正在用多种语言解决Project Euler问题,只是想看看语言的效率和速度有多快。在习题#5中,我们被要求找出能被1到20的所有数整除的最小正数。
我用多种语言实现了这个解决方案。以下是统计数据:
- Go 1.4.2: 0.58s Ruby 2.2 MRI: 6.7sElixir 1.0.5(我的第一个算法):57sElixir 1.0.5(我的第一个算法与MIX_ENV=prod前缀):7.4秒
- Elixir 1.0.5 (Roman's Go等效算法):0.7s
- Elixir 1.0.5 (Roman's Ruby等效算法):1.8秒
为什么Elixir的性能这么慢?我尝试在所有语言中使用相同的优化。警告:我是FP和Elixir新手。
我能做些什么来提高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
我的第一个答案是关于实现您在Ruby中实现的相同算法。现在,这是你的算法在围棋中的Elixir版本:
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.73秒。这些算法是不同的,所以我相信Ruby在这里也可以发挥得更好。
我想,这里的一般规则是:如果你在Elixir中的代码有80%的性能来自Go代码或更好,那就可以了。在其他情况下,很可能你的Elixir代码中有算法错误。
Update about Ruby:
作为奖励,下面是Ruby中的Go等效算法:
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秒。
试试这个版本:
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秒。您的解决方案的主要问题是在每次迭代时将范围转换为列表。这是一个巨大的开销。此外,没有必要在这里创建"无限"流。在其他语言中没有这样做。
你的代码可能很好,但是数学让我很不舒服。有一种简单的递归解决方案可以很好地与这种长生不老的方法相匹配。它还展示了如何在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的时间
我喜欢这个解决方案,因为它很简单:
#!/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
对于Ruby,这可以用一行来解决:
#!/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)
Fred的解决方案很棒。这样效率更低(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