search
LoginSignup
1
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

Elixir その2 Advent Calendar 2020 Day 23

posted at

updated at

Organization

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

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


はじめに

お手本

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関数をわければいいんじゃないだろうか

ガード節

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を使いました
  • :point_down::point_down_tone1::point_down_tone2::point_down_tone3::point_down_tone4::point_down_tone5: のような書き方ができたら一番キレイ:diamond_shape_with_a_dot_inside:に書ける気がしましたがこれはコンパイルエラーになりました
  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
  • (いいやり方ありましたらぜひ教えてください :bangbang::pray::pray_tone1::pray_tone2::pray_tone3::pray_tone4::pray_tone5:)

答えあわせ

  • あっていそう :rocket::rocket::rocket:
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 さんのオリジナルが一番速い :rocket:
  • 単位はマイクロ秒です
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

Wrapping Up :christmas_tree::santa::santa_tone1::santa_tone2::santa_tone3::santa_tone4::santa_tone5::christmas_tree:

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
1
Help us understand the problem. What are the problem?