Почему Elixir является самым медленным среди Ruby и Go в решении Project Euler # 5?

Ответ 1

Мой первый ответ заключался в реализации того же алгоритма, который вы реализовали в Ruby. Теперь, вот версия в Elixir вашего алгоритма в Go:

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:

В качестве бонуса здесь приведен эквивалентный алгоритм Go в 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 с.

Ответ 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 секунды на моем ноутбуке. Основной проблемой вашего решения является преобразование диапазона в список на каждой итерации. Это огромные накладные расходы. Кроме того, здесь нет необходимости создавать "бесконечный" поток. Вы не делали что-то подобное на других языках.

Ответ 3

Ваш код может быть в порядке, но математика заставляет мои зубы болеть. Существует простое рекурсивное решение, которое прекрасно подходит к способу эликсира делать вещи. Он также показывает, как вы можете просто сделать рекурсию в эликсире и не беспокоиться о проблемы производительности, вызванные рекурсией на других языках.

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 и ввода/вывода.

Ответ 4

Мне нравится это решение для его простоты:

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

Ответ 5

Решение 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