logo标签列表

为什么在解决欧拉计划第5题时，Elixir比Ruby和Go慢？

performanceelixirnumerical-computing
20

更新：Elixir不慢，我的算法才慢。我的算法甚至没有进行苹果对苹果的比较。请查看下面Roman关于Ruby和Go等效算法的回答。还要感谢José，我的慢算法可以通过仅加前缀MIX_ENV=prod显著加速。我已经更新了问题中的数据。

原问题： 我正在使用多种语言解决Project Euler问题，以了解各种语言的生产力和速度。在问题 #5中，我们被要求找到最小的正整数，它能被从1到20的所有数字整除。

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

  1. Go 1.4.2：0.58秒
  2. Ruby 2.2 MRI：6.7秒
  3. Elixir 1.0.5（我的第一个算法）：57秒
  4. Elixir 1.0.5（我的第一个算法加上MIX_ENV=prod前缀）：7.4秒
  5. Elixir 1.0.5（Roman的Go等效算法）：0.7秒
  6. Elixir 1.0.5（Roman的Ruby等效算法）：1.8秒

为什么Elixir的性能如此之慢？我尝试在所有语言中使用相同的优化。请注意，我是一个FP和Elixir新手。

有什么办法可以改善Elixir的性能吗？如果您使用任何分析工具来找到更好的解决方案，请在回复中包含它们。

在Go中：

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

在Elixir中：

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
1
我无法解释你的Elixir，但几乎肯定有更好的解决方法，例如尝试构造数字而不仅仅是扫描它。 - Rup
谢谢，Rup。我会尝试那个建议。然而，我的问题纯粹与三种不同语言的类似逻辑的性能有关。 - Abs
5
如果您正在对 Elixir 代码进行基准测试，请确保使用 MIX_ENV=prod 进行基准测试，这样 Elixir 将以最高效的方式编译您的项目。否则，您将得到次优的性能表现。 - José Valim
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代码的性能达到了Go代码的80％或更好，那就可以了。否则，在大多数情况下，你的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秒就可以展示出来。

感谢您再次回答！这在我的系统上需要约0.7秒。 - Abs
太好了！很高兴能帮助你 :-) - Roman Smirnov
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秒的时间。 你解决方案的主要问题是每次迭代都将范围转换为列表。这是一个巨大的开销。此外，在这里没有必要创建“无限”流。在其他语言中，你没有做过这样的事情。

谢谢，Roman！你的算法在我的系统上需要约1.8秒。最大的罪魁祸首确实是范围转换为列表。仅从范围创建列表将运行时间从57秒降至2.7秒。 - Abs
值得注意的是，将MIX_ENV设置为prod会显著加快范围到列表的转换速度（因为我们内联了这些内容），而且Elixir 1.1中的范围也会更快。 - José Valim
谢谢，José！我在我的运行速度极慢的算法中加入了MIX_ENV=prod前缀后，确实看到了显著的改善（从57.0秒降至7.4秒）。我已经在问题中更新了统计数据。 - Abs
4

你的代码可能没问题，但是其中的数学让我感到头疼。有一个简单的递归解决方案与Elixir的处理方式非常匹配。 它还展示了如何在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}

与其他语言的比较并不完全公平，因为它没有包括加载虚拟机和执行I/O的时间。

谢谢，弗雷德。8微秒真是令人印象深刻！我尽量不看你的解决方案，这样我就可以自己尝试GCD方法。在我完成自己的解决方案后，我会包含你的解决方案统计数据。 - Abs
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)

(lcm -> http://ruby-doc.org/core-2.0.0/Integer.html#method-i-lcm)

2
继续深入学习 Ruby，可以尝试以下代码：(1..20).inject(&:lcm) - joegiralt
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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接