performance - Project Euler #5 の解決で Elixir が Ruby と Go の中で最も遅いのはなぜですか?

Question

更新: Elixir は遅くはありません。私のアルゴリズムはそうでした。私のアルゴリズムは、リンゴとリンゴの比較でさえありませんでした。Ruby と Go の同等のアルゴリズムについては、以下の Roman の回答を参照してください。また、José のおかげで、MIX_ENV=prod というプレフィックスを付けるだけで、遅いアルゴリズムを大幅に高速化できます。質問の統計を更新しました。

元の質問: 言語の生産性と速度を確認するためだけに、複数の言語で Project Euler の問題に取り組んでいます。問題 5では、1 から 20 までのすべての数で割り切れる最小の正の数を見つけるように求められます。

ソリューションを複数の言語で実装しました。統計は次のとおりです。

1.4.2 に行く: 0.58 秒
Ruby 2.2 MRI : 6.7 秒
Elixir 1.0.5 (私の最初のアルゴリズム): 57 秒
Elixir 1.0.5 (MIX_ENV=prod プレフィックスを使用した最初のアルゴリズム): 7.4 秒
Elixir 1.0.5 (Roman's Go と同等のアルゴリズム) : 0.7 秒
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")
}

ルビーの場合:

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

score 12 · Accepted Answer

私の最初の答えは、あなたが 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 もここでうまく機能すると確信しています。

ここでの一般的なルールは、Go コードの 80% 以上のパフォーマンスを持つ Elixir のコードがある場合、それで問題ないと思います。それ以外の場合は、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 秒表示される可能性があると思います。

score 5 · Accepted Answer

このバージョンを試してください:

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秒かかります。ソリューションの主な問題は、反復ごとに範囲をリストに変換することです。それは莫大なオーバーヘッドです。また、ここで「無限」のストリームを作成する必要はありません。あなたは他の言語でそのようなことをしませんでした。

score 4 · Accepted Answer

あなたのコードは問題ないかもしれませんが、数学は私の歯を痛めます. 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}

VM をロードして I/O を実行する時間が含まれていないため、他の言語との比較は公平ではありません。

score 2 · Accepted Answer

シンプルさから、このソリューションが気に入っています。

#!/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に関しては、これは 1 行で解決できます。

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

score 1 · Accepted Answer

フレッドのソリューションは素晴らしいです。これは非効率的 (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

performance - Project Euler #5 の解決で Elixir が Ruby と Go の中で最も遅いのはなぜですか?

5 に答える 5

Related

Reference