Perché l'elisir è il più lento tra Ruby e Go nel risolvere Project Euler # 5?

Question

Aggiornamento: L'elisir non è lento, il mio algoritmo era. I miei algoritmi non erano nemmeno il confronto tra mele e mele. Vedi le risposte di Roman in basso per gli algoritmi equivalenti di Ruby and Go. Anche grazie a José, il mio algoritmo lento può essere velocizzato in modo significativo semplicemente prefissando MIX_ENV = prod. Ho aggiornato le statistiche nella domanda.

domanda originale: Sto lavorando a problemi di Project Euler in più lingue solo per vedere quanto sono produttive e quanto veloci sono le lingue. In problem #5, viene chiesto di trovare il numero positivo più piccolo che sia uniformemente divisibile per tutti i numeri da 1 a 20.

Ho implementato la soluzione in più lingue. Ecco le statistiche:

1. Go 1.4.2: 0.58s
2. Rubino 2.2 MRI: 6.7s
3. Elixir 1.0.5 (il mio primo algoritmo): 57s
4. Elixir 1.0.5 (il mio primo algoritmo con MIX_ENV = prefix prod): 7.4s
5. Elixir 1.0.5 (Go algoritmo equivalente di Roman): 0.7s
6. Elixir 1.0.5 (rubino algoritmo equivalente di Roman): 1.8s

Perché le prestazioni di Elixir sono così lente? Ho provato a utilizzare le stesse ottimizzazioni in tutte le lingue. Avvertenza: Sono un principiante di FP ed Elixir.

C'è qualcosa che posso fare per migliorare le prestazioni in elisir? Se hai utilizzato strumenti di profilazione per trovare una soluzione migliore, potresti includerli nella risposta?

In Vai:

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

In 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 

In 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 mia prima risposta riguardava l'implementazione dello stesso algoritmo implementato in Ruby. Ora, qui è una versione in Elixir del vostro algoritmo in 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 

Ci vuole circa 0.73s sul mio portatile. Questi algoritmi sono diversi, quindi sono sicuro che anche Ruby potrebbe giocare meglio qui.

Indovino, la regola generale qui: se si ha codice in Elixir con prestazioni pari all'80% dal codice Go o superiore, va bene. In altri casi molto probabilmente hai un errore algoritmico nel tuo codice Elixir.

Aggiornamento in merito a Ruby:

Come bonus, qui è andare algoritmo equivalente in 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 

Svolge a 4,5 volte più veloce, quindi credo che potrebbe mostrare ~ 1,5 s sul tuo computer.

Answer 2

Prova questa versione:

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 

Ci vogliono circa 1,4 secondi sul mio portatile. Il problema principale della soluzione è la conversione di un intervallo in un elenco a ogni iterazione. È un enorme sovraccarico. Inoltre, non è necessario creare stream "infinito" qui. Non hai fatto qualcosa del genere in altre lingue.

Answer 3

Il tuo codice può andare bene, ma i calcoli mi fanno male ai denti. Esiste una semplice soluzione ricorsiva che si adatta perfettamente al modo di fare elisir. Mostra anche come si può fare la ricorsione in elisir e non preoccuparsi di i problemi di prestazioni causati dalla ricorsione in altre lingue.

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 

Per quel che vale, questo richiede 8 microsecondi sul mio computer

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

Non proprio un equo confronto ad altre lingue in quanto non comprende il tempo per caricare la VM e fare il I/O.

Answer 4

La soluzione di Fred è eccezionale. Questo è più inefficiente, (32 microsecondi) ma più chiaro. Forse con la meomizzazione, potrebbe eseguire l'ordine di grandezza più velocemente.

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 5

mi piace questa soluzione per la sua semplicità:

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

E 'molto veloce pure.

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

Per quanto riguarda Rubino, questo può essere risolto in una sola riga:

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