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.