20

更新：Elixir 并不慢，我的算法是。我的算法甚至不是苹果对苹果的比较。有关 Ruby 和 Go 等效算法的信息，请参阅下面的 Roman 的答案。还要感谢 José，只需添加 MIX_ENV=prod 前缀就可以显着加快我的慢速算法。我已经更新了问题中的统计数据。

原始问题： 我正在研究多种语言的 Project Euler 问题，只是为了看看语言的效率和速度。在问题 #5中，我们被要求找到能被 1 到 20 的所有数字整除的最小正数。

我用多种语言实现了该解决方案。以下是统计数据：

  1. 去 1.4.2 : 0.58s
  2. Ruby 2.2 MRI : 6.7s
  3. Elixir 1.0.5（我的第一个算法）：57s
  4. Elixir 1.0.5（我的第一个带有 MIX_ENV=prod 前缀的算法）：7.4s
  5. Elixir 1.0.5（罗马围棋等效算法）：0.7s
  6. Elixir 1.0.5（Roman 的 Ruby 等效算法）：1.8s

为什么 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")
}

在红宝石中：

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
4

5 回答 5

12

我的第一个答案是关于实现您在 Ruby 中实现的相同算法。现在，这是您在 Go 中的算法的 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 代码很可能存在算法错误。

关于 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 秒。

于 2015-09-07T17:15:40.173 回答
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 秒。您的解决方案的主要问题是在每次迭代时将范围转换为列表。这是一个巨大的开销。此外，这里不需要创建“无限”流。你没有用其他语言做类似的事情。

于 2015-09-07T16:45:24.643 回答
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 的时间。

于 2015-09-08T16:28:53.550 回答
2

我喜欢这个解决方案的简单性：

#!/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 )

于 2017-09-12T01:33:16.043 回答
1

弗雷德的解决方案很棒。这更无效率（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
于 2016-08-13T17:16:38.390 回答