かっこいいフィボナッチ数列(Elixir)

はじめに

• Twitterでかっこいいと私が感じたフィボナッチ数列のプログラムが書いてあったので写してみました
• Fibonacci sequence generated by an @elixirlang stream
• Elixirは、1.10.4-otp-23を使っています

フィボナッチ数列

f(0) = 0 \\
f(1) = 1 \\
f(n) = f(n -1) + f(n - 2)

プログラム

lib/fibonacci.ex

defmodule Fibonacci do
  def sequence, do: Stream.unfold({0, 1}, fn {a, b} -> {a, {b, a + b}} end)

  def at(n), do: sequence() |> Enum.take(n + 1) |> Enum.at(-1)
end

defmodule PureFibonacci do
  def at(0), do: 0

  def at(1), do: 1

  def at(n), do: at(n - 1) + at(n - 2)
end

• Fibonacciモジュールの方が、Twitterに書いてあった、私がかっこいいと感じたプログラムです
  • すこーし変えています(意味するところは同じはずです)
• PureFibonacciモジュールは素朴にフィボナッチ数列の計算を書いてみた例です

計測

$ iex -S mix

iex> :timer.tc(Fibonacci, :at, [40])    
{19, 102334155}

iex> :timer.tc(PureFibonacci, :at, [40])
{6503506, 102334155}

• :timer.tc/3は、引数に(モジュール、メソッド名のアトム、引数)を指定してコールすると結果を{時間, 値}の形で得られます
  • 時間の単位は、microsecondsであります
• PureFibonacci.at(40)は約6.5秒かかるのに対して、Fibonacci.at(40)は19μ秒で計算が終わっているのであります
  • PureFibonacciのほうが数式そのままで書いている内容はわかりやすいですが、時間はかかるという結果になりました
• Stream.unfold/2

Wrapping Up

• Stream.unfold/2 は、というかこれに限らずStreamは全般的に個人的にはあまりうまく使えていない気がするので理解を深めていきたいとおもいます
• Enjoy Elixir!