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

Мой первый ответ был о реализации того же алгоритма, который вы реализовали в Ruby. Теперь вот версия вашего алгоритма в 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 здесь тоже мог бы сыграть лучше.

Я думаю, здесь действует общее правило: если у вас есть код на Эликсире, который имеет производительность около 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 с.

Попробуйте эту версию:

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}

Не совсем справедливое сравнение с другими языками, поскольку оно не включает время на загрузку виртуальной машины и выполнение операций ввода-вывода.

Мне нравится это решение за его простоту:

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

Решение Фреда отличное. Это более неэффективно (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