「動的計画法を使う問題をElixirで関数型っぽく解いてみる」のFibonacci3をガード節を使って書き直してみる

Elixir

Last updated at 2020-12-23Posted at 2020-12-22

この記事は Elixir その2 Advent Calendar 2020 23日目です。

はじめに

Elixir 楽しんでいますか
@masatam81 さんの動的計画法を使う問題をElixirで関数型っぽく解いてみる -- Mapも使ってみる(おまけ)のFibonacci3を書き直してみます
私は動的計画法とか言われてもよくわかっていません
けれどもElixirは読めるので手本があればなんとかなります

お手本

defmodule Fibonacci3 do
  defp create(dp, n) when n < 2 do
    Map.put(dp, n, n)
  end
  defp create(dp, n) do
    if not Map.has_key?(dp, n) do
      dp =
        if not Map.has_key?(dp, n-1) do
          create(dp, n-1)
        else
          dp
        end
      dp =
        if not Map.has_key?(dp, n-2) do
          create(dp, n-2)
        else
          dp
        end
      Map.put(dp, n, Map.get(dp, n-1) + Map.get(dp, n-2))
    else
      dp
    end
  end
  def fib(n) do
    dp = create(Map.new, n)
    Map.get(dp, n)
  end
end

Mapにキーがあるかどうかをガード節やパターンマッチで`create/2`関数をわければいいんじゃないだろうか

なにかいいのないかなー
これか
- Kernel.is_map_key/2

ガード節編

defmodule Fibonacci4 do
  defp create(dp, n) when n < 2 do
    Map.put(dp, n, n)
  end

  defp create(dp, n) when is_map_key(dp, n), do: dp

  defp create(dp, n) when is_map_key(dp, n - 1) and is_map_key(dp, n - 2) do
    Map.put(dp, n, Map.get(dp, n - 1) + Map.get(dp, n - 2))
  end

  defp create(dp, n) when is_map_key(dp, n - 1) do
    dp = create(dp, n - 2)
    Map.put(dp, n, Map.get(dp, n - 1) + Map.get(dp, n - 2))
  end

  defp create(dp, n) when is_map_key(dp, n - 2) do
    dp = create(dp, n - 1)
    Map.put(dp, n, Map.get(dp, n - 1) + Map.get(dp, n - 2))
  end

  defp create(dp, n) do
    dp = create(dp, n - 1)
    dp = create(dp, n - 2)
    Map.put(dp, n, Map.get(dp, n - 1) + Map.get(dp, n - 2))
  end

  def fib(n) do
    dp = create(Map.new(), n)
    Map.get(dp, n)
  end
end

パターンマッチ

defmodule Fibonacci5 do
  defp create(dp, n) when n < 2 do
    Map.put(dp, n, n)
  end

  defp create(dp, n) do
    n_minus_one = n - 1
    n_minus_two = n - 2

    case dp do
      %{^n => _} ->
        dp

      %{^n_minus_one => v1, ^n_minus_two => v2} ->
        Map.put(dp, n, v1 + v2)

      %{^n_minus_one => v1} ->
        dp = create(dp, n_minus_two)
        Map.put(dp, n, v1 + Map.get(dp, n_minus_two))

      %{^n_minus_two => v2} ->
        dp = create(dp, n_minus_one)
        Map.put(dp, n, Map.get(dp, n_minus_one) + v2)

      _ ->
        dp = create(dp, n_minus_one) |> create(n_minus_two)
        Map.put(dp, n, Map.get(dp, n - 1) + Map.get(dp, n - 2))
    end
  end

  def fib(n) do
    dp = create(Map.new(), n)
    Map.get(dp, n)
  end
end

case/2を使いました
のような書き方ができたら一番キレイに書ける気がしましたがこれはコンパイルエラーになりました

  defp create(%{^n => _} = dp, n), do: dp


iex> recompile

== Compilation error in file lib/fibonacci5.ex ==
** (CompileError) lib/fibonacci5.ex:6: undefined variable ^n. No variable "n" has been defined before the current pattern
    (stdlib 3.13) lists.erl:1354: :lists.mapfoldl/3
    (stdlib 3.13) lists.erl:1354: :lists.mapfoldl/3
** (exit) shutdown: 1
    (mix 1.11.2) lib/mix/tasks/compile.all.ex:76: Mix.Tasks.Compile.All.compile/4
    (mix 1.11.2) lib/mix/tasks/compile.all.ex:57: Mix.Tasks.Compile.All.with_logger_app/2
    (mix 1.11.2) lib/mix/tasks/compile.all.ex:35: Mix.Tasks.Compile.All.run/1
    (mix 1.11.2) lib/mix/task.ex:394: Mix.Task.run_task/3
    (mix 1.11.2) lib/mix/tasks/compile.ex:119: Mix.Tasks.Compile.run/1
    (mix 1.11.2) lib/mix/task.ex:394: Mix.Task.run_task/3
    (iex 1.11.2) lib/iex/helpers.ex:104: IEx.Helpers.recompile/1

(いいやり方ありましたらぜひ教えてください )

答えあわせ

あっていそう

iex> Fibonacci3.fib(50)                                                  
12586269025

iex> Fibonacci4.fib(50)
12586269025

iex> Fibonacci5.fib(50)
1258626902

iex> Fibonacci3.fib(51)
20365011074

iex> Fibonacci4.fib(51)
20365011074

iex> Fibonacci5.fib(51)
20365011074


iex> Fibonacci3.fib(52)
32951280099

iex> Fibonacci4.fib(52)
32951280099

iex> Fibonacci5.fib(52)
32951280099

iex> Fibonacci3.fib(100)                                                 
354224848179261915075

iex> Fibonacci4.fib(100)
354224848179261915075

iex> Fibonacci5.fib(100)
354224848179261915075

比較

いい勝負
@masatam81 さんのオリジナルが一番速い
単位はマイクロ秒です

iex> :timer.tc(Fibonacci3, :fib, [100]) |> elem(0)
61

iex> :timer.tc(Fibonacci4, :fib, [100]) |> elem(0)
71

iex> :timer.tc(Fibonacci5, :fib, [100]) |> elem(0)
65

iex> :timer.tc(Fibonacci3, :fib, [1000]) |> elem(0)
970

iex> :timer.tc(Fibonacci4, :fib, [1000]) |> elem(0)
1130

iex> :timer.tc(Fibonacci5, :fib, [1000]) |> elem(0)
979