Go VS Elixir (1)フィボナッチ数列

最近仕事はもっぱら Go を使うことが多いのですが、 Elixir がここ最近気になっており学習をしています。 ということで、思いつきで性能比較をしてみました。

検証環境

• MacBook Pro (Retina 13-inch、Early 2015)
• プロセッサ 3.1 GHz Intel Core i7
• メモリ 16GB 1867 MHz DDR3
• Go 1.5.1
• Elixr 1.0.5

フィボナッチ数列での再帰処理

第一弾はみんな大好きフィボナッチ数列です。 Goは再帰が不得意ということは割といろんなところで言われています。 一方、Elixirは関数型言語だし得意な部類に入るのではないか。多分。 ということでどうなるかやってみました。

ナイーブ実装

Go

func fib(n int) int {
    if n < 2 {
        return n
    }
    return fib(n-2) + fib(n-1)
}

$ time go run fib.go 20
6765
go run fib.go 20  0.40s user 0.07s system 118% cpu 0.402 total

time go run fib.go 30
832040
go run fib.go 30  0.45s user 0.09s system 104% cpu 0.519 total

time go run fib.go 40
102334155
go run fib.go 40  1.15s user 0.07s system 103% cpu 1.185 total

Elixir

defmodule Fib do
  def fib 0 do 0 end
  def fib 1 do 1 end
  def fib(n) do fib(n - 1) + fib(n - 2) end
end

time elixir fib.exs 20 
6765
elixir fib.exs 20  0.42s user 0.21s system 100% cpu 0.618 total
time elixir fib.exs 30
832040
elixir fib.exs 30  0.51s user 0.19s system 97% cpu 0.723 total
time elixir fib.exs 40
102334155
elixir fib.exs 40  7.13s user 0.22s system 92% cpu 7.915 total

再帰が深くなると差が縮まると思いきや逆の結果に。 意外です。。

メモ化

Go

var cache map[int]int
func init() {
    cache = map[int]int{}
}

func fib(n int) int {
    if n <= 1 {
        return n
    }
    if cache[n] == 0 {
        cache[n] = fib(n-1) + fib(n-2)
    }
    return cache[n]
}

time go run fib.go 40
102334155
go run fib.go 40  0.41s user 0.08s system 110% cpu 0.443 total

Elixir

defmodule Fib do
  def fib 0 do 0 end
  def fib 1 do 1 end
  def fib(n) do
    case Agent.get(__MODULE__, &Map.get(&1, n)) do
      nil ->
        v = fib(n - 1) + fib(n - 2)
        Agent.update(__MODULE__, &Map.put(&1, n, v))
        v
      v -> v
    end
  end

  def start_link do
    Agent.start_link(fn -> Map.new end, name: __MODULE__)
  end
end
Fib.start_link

time elixir fib.exs 40
102334155
elixir fib.exs 40  0.46s user 0.20s system 94% cpu 0.692 total

Elixirの方がメモ化の恩恵を大きく受けました。

終わりに

elixir ではなく素の erlangだとまた結果は変わるのだろうか。 そのうちまた試してみます。