performance - solutions - project euler problem 2

¿Por qué es Elixir más lento entre Ruby and Go en la resolución del Proyecto Euler#5?

Question

Actualización : Elixir no es lento, mi algoritmo era. Mis algoritmos ni siquiera eran comparación de manzanas con manzanas. Vea las respuestas de Roman a continuación para los algoritmos equivalentes de Ruby and Go. También gracias a José, mi algoritmo lento puede acelerarse significativamente simplemente con el prefijo MIX_ENV = prod. He actualizado las estadísticas en la pregunta.

Pregunta original: estoy trabajando en los problemas del Proyecto Euler en varios idiomas para ver qué tan productivos y rápidos son los idiomas. En el problema # 5 , se nos pide que encontremos el número positivo más pequeño que sea divisible por todos los números del 1 al 20.

Implementé la solución en múltiples idiomas. Aquí están las estadísticas:

1. Go 1.4.2: 0.58s
2. Ruby 2.2 MRI: 6.7s
3. Elixir 1.0.5 (mi primer algoritmo): 57s
4. Elixir 1.0.5 (mi primer algoritmo con MIX_ENV = prefijo prod): 7.4s
5. Elixir 1.0.5 (algoritmo equivalente de Roman''s Go): 0.7s
6. Elixir 1.0.5 (algoritmo equivalente de Ruby de Roman): 1.8s

¿Por qué el rendimiento de Elixir es tan lento? Intenté usar las mismas optimizaciones en todos los idiomas. Advertencia: soy un novato de FP y Elixir.

¿Hay algo que pueda hacer para mejorar el rendimiento en Elixir? Si utilizó alguna herramienta de creación de perfiles para encontrar una mejor solución, ¿podría incluirlas en la respuesta?

En 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")
}

En 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

En el 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

Answer 1

La solución de Fred es genial. Esto es más deficiente, (32 microsegundos) pero más claro. Tal vez con meomización, podría correr orden de magnitud más rápido.

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

Answer 2

Me gusta esta solución por su simplicidad:

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

Es muy rápido también.

./problem005.exs  0.34s user 0.17s system 101% cpu 0.504 total

En cuanto a Ruby , esto se puede resolver en una sola línea:

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

Answer 3

Mi primera respuesta fue sobre la implementación del mismo algoritmo que implementó en Ruby. Ahora, aquí hay una versión en Elixir de su algoritmo en 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

Toma alrededor de 0.73s en mi laptop. Estos algoritmos son diferentes, así que estoy seguro de que Ruby también podría jugar mejor aquí.

Supongo que, la regla general aquí: si tiene un código en Elixir que tiene un rendimiento de 80% del código Go o mejor, está bien. En otros casos, lo más probable es que tenga un error algorítmico en su código de Elixir.

Actualización sobre Ruby:

Como beneficio adicional, aquí está el algoritmo equivalente de Go en 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

Se realiza 4.5 veces más rápido, así que supongo que podría mostrar ~ 1.5 s en su computadora.

Answer 4

Prueba esta versión:

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

Se tarda unos 1,4 segundos en mi computadora portátil. El principal problema de su solución es la conversión de un rango a una lista en cada iteración. Es una gran sobrecarga. Además, no hay necesidad de crear un flujo "infinito" aquí. No hiciste algo así en otros idiomas.

Answer 5

Tu código puede estar bien, pero las matemáticas hacen que me duelen los dientes. Existe una solución recursiva simple que se ajusta muy bien a la forma en que el elixir hace las cosas. También muestra cómo puede hacer recursión en el elixir y no preocuparse por los problemas de rendimiento que causa la recursión en otros idiomas.

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

Por lo que vale, esto toma 8 microsecs en mi computadora

iex> :timer.tc(Euler_5, :smallest, [20])
{8, 232792560}

No es realmente una comparación justa con otros idiomas, ya que no incluye el tiempo para cargar la VM y hacer la E / S.